### How to Protect Yourself without Perfect Shredding

Ran Canetti, Dror Eiger, 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.

Note: The updated verion will be posted soon.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of the paper under the same title in ICALP 2008.
Keywords
Contact author(s)
dylim @ mit edu
History
2008-09-12: last of 3 revisions
See all versions
Short URL
https://ia.cr/2008/291

CC BY

BibTeX

@misc{cryptoeprint:2008/291,
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{https://eprint.iacr.org/2008/291}},
url = {https://eprint.iacr.org/2008/291}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.