Cryptography with Tamperable and Leaky Memory
Speaker: Yael Kalai, MSR New England
A large and growing body of research has sought to secure cryptographic systems against physical attacks.
Motivated by real-world physical attacks on memory, an important line of work was initiated by Akavia, Goldwasser, and
Vaikuntanathan [AGV09], where security is sought under the assumptions that (1) all memory is leaky, and
(2) leakage can be an arbitrary (efficient) shrinking function of the memory.
However, physical attacks on memory are not limited to leakage through side-channels, but can also include active *tampering* attacks through a variety of physical attacks, including heat and EM radiation. Nevertheless, protection against the analogous model for tampering -- where (1) all memory is tamperable, and (2) where the tampering can be an arbitrarily chosen (efficient) function applied to the memory -- has remained an elusive target, despite significant effort on tampering-related questions.
In this work, we tackle this question by considering a model where we assume that both these pairs of statements are true -- that all memory is both leaky and (arbitrarily) tamperable.
Furthermore, we assume that this leakage and tampering can happen repeatedly and continually (extending the model of [DHLW,BKKV10] in the context of leakage).
We construct an encryption scheme and a signature scheme that even after tampering periodically and leaking periodically, the adversary cannot sign a new message with respect to the original verification key, or break semantic security of the encryption scheme with respect to the original public key.
In both schemes we assume that memory can be updated in a randomized fashion between episodes of tampering and leakage.
The security of both schemes relies on the linear assumption over bilinear groups.
These results also improve previous results in the continual leakage regime without tampering [DHLW,BKKV10], improving the leakage rate from 1/2-\epsilon to 1-\epsilon.
Joint with Bhavana Kanukurthi and Amit Sahai