1999 | OriginalPaper | Chapter
Information Theoretically Secure Communication in the Limited Storage Space Model
Authors : Yonatan Aumann, Michael O. Rabin
Published in: Advances in Cryptology — CRYPTO’ 99
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We provide a simple secret-key two-party secure communication scheme, 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 our main results utilizes a novel combination of linear algebra and Kolmogorov complexity considerations.