zbMATH — the first resource for mathematics

Information theoretically secure communication in the limited storage space model. (English) Zbl 0940.94007
Wiener, Michael (ed.), Advances in cryptology - CRYPTO ’99. 19th annual international cryptology conference Santa Barbara, CA, USA, August 15-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1666, 65-79 (1999).
Summary: The authors provide a simple secret-key two-party secure communication scheme [see also U. M. Maurer, J. Cryptology 5, 53-66 (1992; Zbl 0746.94013)], which is provably information-theoretically secure in the limited-storage-space model. The limited-storage-space model postulates an eavesdropper who can execute arbitrarily complex computations, and is only limited in the total amount of storage space (not computation space) available to him. The bound on the storage space can be arbitrarily large (e.g. terabytes), as long as it is fixed. Given this bound, the protocol guarantees that the probability of the eavesdropper of gaining any information on the message is exponentially small. The proof of the main results utilizes a novel combination of linear algebra and Kolmogorov complexity considerations.
For the entire collection see [Zbl 0921.00042].

94A60 Cryptography
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)