Paper 2016/706

Memory Erasability Amplification

Jan Camenisch, Robert R. Enderlein, and Ueli Maurer


Erasable memory is an important resource for designing practical cryptographic protocols that are secure against adaptive attacks. Many practical memory devices such as solid state drives, hard disks, or file systems are not perfectly erasable because a deletion operation leaves traces of the deleted data in the system. A number of methods for constructing a large erasable memory from a small one, e.g., using encryption, have been proposed. Despite the importance of erasable memory in cryptography, no formal model has been proposed that allows one to formally analyse such memory constructions or cryptographic protocols relying on erasable memory. The contribution of this paper is three-fold. First, we provide a formal model of erasable memory. A memory device allows a user to store, retrieve, and delete data, and it is characterised by a leakage function defining the extent to which erased data is still accessible to an adversary. Second, we investigate how the erasability of such memories can be amplified. We provide a number of constructions of memories with strong erasability guarantees from memories with weaker guarantees. One of these constructions of perfectly erasable memories from imperfectly erasable ones can be considered as the prototypical application of Canetti et al.'s All-or-Nothing Transform (AoNT). Motivated by this construction, we propose some new and better AoNTs that are either perfectly or computationally secure. These AoNTs are of possible independent interest. Third, we show (in the constructive cryptography framework) how the construction of erasable memory and its use in cryptographic protocols (for example to achieve adaptive security) can naturally be composed to obtain provable security of the overall protocol.

Available format(s)
Publication info
Published elsewhere. Security and Cryptography for Networks Volume 9841 of the series Lecture Notes in Computer Science pp 104-125
composable securityall or nothing transforms
Contact author(s)
jca @ zurich ibm com
2016-08-29: last of 2 revisions
2016-07-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jan Camenisch and Robert R.  Enderlein and Ueli Maurer},
      title = {Memory Erasability Amplification},
      howpublished = {Cryptology ePrint Archive, Paper 2016/706},
      year = {2016},
      doi = {10.1007/978-3-319-44618-9_6},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.