Unconditional Security Against Memory-Bounded Adversaries
Christian Cachin and Ueli Maurer
We propose a private-key cryptosystem and a protocol for key agreement by public discussion that are unconditionally secure based on the sole assumption that an adversary's memory capacity is limited, while no assumption about his computing power is made. The scenario assumes that a random bit string of length slightly larger than the adversary's memory capacity can be received by all parties. The random bit string can for instance be broadcast by a satellite or over an optical network, or exchanged over an insecure channel between the communicating parties. The proposed schemes require very high bandwidth but can nevertheless be practical.
Keywords: Unconditional Security, Provable Security, Private-Key Encryption, Public Key Agreement, Space Bounds, Privacy Amplification, Rényi Entropy, Information Theory.
BibTeX Citation
@inproceedings{CacMau97b,
author = {Christian Cachin and Ueli Maurer},
title = {Unconditional Security Against Memory-Bounded Adversaries},
editor = {Burton S. Kaliski Jr.},
booktitle = {Advances in Cryptology --- CRYPTO~'97},
pages = 292--306,
series = {Lecture Notes in Computer Science},
volume = 1294,
year = 1997,
month = 8,
publisher = {Springer-Verlag},
}