We uncover a new class of attacks that can potentially affect
any cryptographic protocol. The attack is performed by an adversary that at some point has access to the physical memory of a
participant, including all its previous states.
In order to protect protocols from such attacks, we introduce a cryptographic primitive that we call erasable memory. Using this primitive, it is possible to implement the essential cryptographic action of forgetting a secret. We show how to use a small erasable memory in order to transform a large non-erasable memory into a large and erasable
memory. In practice, this shows how to turn any type of storage device into a storage device that can selectively forget.
Moreover, the transformation can be performed using the minimal assumption of the existence of any one-way function, and can
be implemented using any block cipher, in which case it is quite efficient. We conclude by suggesting some concrete implementations
of small amounts of erasable memory.
Part of Giovanni’s work done while at Bellcore
Part of this work done while visiting UCSD
Part of this work done while at UCSD