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: ia.cr/2008/291 Discussion forum: Show discussion | Start new discussion