## Cryptography with Tamperable and Leaky Memory

**Yael Tauman Kalai, Bhavana Kanukurthi, and Amit Sahai**

*
Microsoft Research;
Boston University; and
University of California (UCLA)
*
**Abstract.**
A large and growing body of research has sought to secure cryptographic systems against
physical attacks. Motivated by a large variety of 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 arbitrarily chosen (efficient) 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* of 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 a signature scheme and
an encryption scheme that are provably secure against such attacks, assuming that memory can be updated in a randomized fashion between episodes of tampering and leakage. In both schemes we rely on the linear assumption over bilinear groups.

We also separately consider a model where only continual and repeated tampering
(but only bounded leakage) is allowed, and we are able to obtain positive results assuming
only that “self-destruct” is possible, without the need for memory updates.

Our results also improve previous results in the continual leakage regime without
tampering [DHLW, BKKV10]. Whereas previous schemes secure against continual leakage
(of arbitrary bounded functions of the secret key), could tolerate only
1/2-ε
leakage-rate between key updates under the linear assumption over bilinear groups,
our schemes can tolerate 1-ε leakage-rate between key updates, under the same assumption.