Information Security and Cryptography Research Group

Unconditional Security Against Memory-Bounded Adversaries

Christian Cachin and Ueli Maurer

Advances in Cryptology — CRYPTO '97, Lecture Notes in Computer Science, Springer-Verlag, vol. 1294, pp. 292–306, Aug 1997.

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

    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},

Files and Links