International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: How to Protect Yourself without Perfect Shredding

Authors:
Ran Canetti
Dror Eiger
Shafi Goldwasser
Dah-Yoh Lim
Download:
URL: http://eprint.iacr.org/2008/291
Search ePrint
Search Google
Abstract: 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.
BibTeX
@misc{eprint-2008-17968,
  title={How to Protect Yourself without Perfect Shredding},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / mobile adversary, proactive security, adaptive security, forward security, intrusion resilience, universal hashing, partial erasures, secure multiparty computation, randomness extractors},
  url={http://eprint.iacr.org/2008/291},
  note={This is the full version of the paper under the same title in ICALP 2008. dylim@mit.edu 14076 received 27 Jun 2008, last revised 16 Jul 2008},
  author={Ran Canetti and Dror Eiger and Shafi Goldwasser and Dah-Yoh Lim},
  year=2008
}