Magnifying computing gaps

In the field of information security, the best way of protecting the privacy of the participants is to keep silent. Consider two, not necessarily identical, powerful computers or computer-grids connected by a unidirectional communication link that should transfer a long stream of information in the presence of a listening adversary that is slightly weaker. We present schemes that enhance the computation strength gap between the powerful computers and the adversary. The gap between the amount of information decrypted by the adversary and the information decrypted by the receiver grows with time. Based on a new defined shortest vector problem, we also propose a simplified version scheme in which only the receivers are computationally powerful. The scheme is self-stabilizing in the sense that it can establish a security level without relying on (previously distributed private keys that are part of) the state. The iterative nested approach can be used for enhancing the security of the classical protocol of Ralph Merkle [19]. Several applications for sensor networks and for secure communication with survivors are suggested.

Authors

• Shlomi Dolev
• Ephraim Korach
• Ximing Li Key Laboratory of Symbolic Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science and Technology, Jilin University
• Yin Li
• Galit Uzan

Keywords

• Unidirectional encryption
• Combinatorial optimization problems