Erasers and erasures: Pinch’s unfortunate ‘uncertainty principle’

Cai Qing-Yu

We show that information in quantum memory can be erased and recovered perfectly if it is necessary. The fact that the final states of environment are completely determined by the initial states of the system allows an erasure operation to be realized by a swap operation between the system and an ancilla. Therefore, the erased information can be recovered. When there is an irreversible process, e.g. an irreversible operation or a decoherence process, in the erasure process, the information would be erased perpetually. We present that quantum erasure will also give heat dissipation in the environment. A classical limit of quantum erasure is given to coincide with Landauer's erasure principle.

Jacob J. Collings, Jean-François S. Van Huele

Shafi Goldwasser, Ran Canetti, Dah-Yoh Lim

This thesis is a study of erasures in cryptographic protocols. Erasing old data and keys is an important capability of honest parties in cryptographic protocols. It is useful in many settings, including proactive security in the presence of a mobile adversary, adaptive security in the presence of an adaptive adversary, forward security, and intrusion resilience. Some of these settings, such as achieving proactive security, is provably impossible without some form of erasures. Other settings, such as designing protocols that are secure against adaptive adversaries, are much simpler to achieve when erasures are allowed. Protocols for all these contexts 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 imperfect or partial erasures where erasure instructions are only partially effective and leave almost all the data intact, thus giving the honest parties only a limited capability to dispose old data. Nonetheless, we show how to design protocols for all of the above settings (including proactive security, adaptive security, forward security, and intrusion resilience) for which this weak form of erasures suffices. We do not have to invent entirely new protocols, but rather show how to automatically modify protocols relying on perfect erasures into ones for which partial erasures suffices. Stated most generally, we provide a compiler that transforms any protocol relying on perfect erasures for security into one with the same functionality that remains secure even if the erasures are only partial. 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 compiler must incur a cost in additional storage, and that our compiler is near optimal in terms of its storage overhead. We also give computationally more efficient compilers for a number of special cases: (1) when all the computations on secrets can be done in constant parallel time (NC0); (2) for a class of proactive secret sharing protocols where we leave the protocol intact except for changing the representation of the shares of the secret and the instructions that modify the shares (to correspondingly modify the new representation instead). (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)

Khaled Abdel-Ghaffar, Jos H. Weber

Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, we introduce parity-check matrices yielding parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. This allows for the separation of erasures from errors to facilitate decoding. The parity-check matrices typically have redundant rows. We give several constructions of such matrices and prove general bounds on their minimum sizes.

Pei Dang, Guan-Tie Deng, Tao Qian