Cryptology ePrint Archive: Report 2008/291

How to Protect Yourself without Perfect Shredding

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

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.

Category / Keywords: cryptographic protocols / mobile adversary, proactive security, adaptive security, forward security, intrusion resilience, universal hashing, partial erasures, secure multiparty computation, randomness extractors

Publication Info: This is the full version of the paper under the same title in ICALP 2008.

Date: received 27 Jun 2008, last revised 11 Sep 2008

Contact author: dylim at mit edu

Available format(s): PDF | BibTeX Citation

Note: The updated verion will be posted soon.

Version: 20080912:040814 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]