Paper 2008/291

How to Protect Yourself without Perfect Shredding

Ran Canetti, Dror Eiger, Shafi Goldwasser, and Dah-Yoh Lim


Erasing old data and keys is an important tool in cryptographic protocol design. It is useful in many settings, including proactive security, adaptive security, forward security, and intrusion resilience. Protocols for all these settings typically assume the ability to perfectly erase information. Unfortunately, as amply demonstrated in the systems literature, perfect erasures are hard to implement in practice. We propose a model of partial erasures where erasure instructions leave almost all the data erased intact, thus giving the honest players only a limited capability for disposing of old data. Nonetheless, we provide a general compiler that transforms any secure protocol using perfect erasures into one that maintains the same security properties when only partial erasures are available. The key idea is a new redundant representation of secret data which can still be computed on, and yet is rendered useless when partially erased. We prove that any such a compiler must incur a cost in additional storage, and that our compiler is near optimal in terms of its storage overhead.

Note: The updated verion will be posted soon.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of the paper under the same title in ICALP 2008.
mobile adversaryproactive securityadaptive securityforward securityintrusion resilienceuniversal hashingpartial erasuressecure multiparty computationrandomness extractors
Contact author(s)
dylim @ mit edu
2008-09-12: last of 3 revisions
2008-07-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Dror Eiger and Shafi Goldwasser and Dah-Yoh Lim},
      title = {How to Protect Yourself without Perfect Shredding},
      howpublished = {Cryptology ePrint Archive, Paper 2008/291},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.