Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Information Theoretically Secure Communication in the Limited Storage Space Model

Yonatan Aumann, Michael O. Rabin

Published Jan 1, 1999• 72 citations
Publisher
DOI
10.1007/3-540-48405-1_5

Related papers

A Practical and Secure Communication Protocol in the Bounded Storage Model

Erkay Savaş, Berk Sunar

Lecture notes in computer science•Jan 1, 2005•4 citations

Information theoretically secure communication in the limited storage space model

Yonatan Aumann, Michael O. Rabin

Abstract. 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. 1

•Jan 1, 1999•0 citations

Tight security proofs for the bounded-storage model

Stefan Dziembowski, Ueli M. Maurer

(MATH) In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s$xi;t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n»|K| about which the adversary has essentially no information, thus at first glance apparently contradicting Shannon's bound on the key size of a perfect cipher.All previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key K had in fact to be longer than the derived one-time pad, or t had to be extremely large (tρns), or the adversary was assumed to be able to store only actual bits of R rather than arbitrary s bits of information about R, or the adversary could obtain a non-negligible amount of information about X.In this paper we prove the first non-restricted security result in the bounded-storage model, exploiting the full potential of the model: K is short, X is very long (e.g. gigabytes), t needs to be only moderately larger than s, and the security proof is optimally strong. In fact, we prove that s/t can be arbitrarily close to 1 and hence the storage bound is essentially optimal.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2002•8 citations

Secure Communication in Minimal Connectivity Models

Matthew Franklin, Rebecca N. Wright

Journal of Cryptology•Jan 1, 2000•128 citations

Everlasting security in the bounded storage model

Yonatan Aumann, Yan Zong Ding, Michael O. Rabin

We address the problem of the-security of cryptographic protocols in face of future advances in computing technology and algorithmic research. The problem stems from the fact may be deemed that computations which at a given point in time may be deemed infeasible, can, in the course of years or decades, be made possible with improved hardware and/or breakthroughs in code-breaking algorithms. In such cases, the security of historical , but nonetheless highly confidential data may be in jeopardy. We present a scheme for efficient secure two-party communication with provable everlasting security. The security is guaranteed in face of any future technological advances, given the current state of of the art. Furthermore, the security of the messages is also guaranteed even if the secret encryption/decryption key is revealed in the future, The scheme is based on the bounded storage model and provides information-theoretic security in this model. The bounded storage model postulates an adversary who is computationally unbounded, and is only bounded in the amount of storage (not computation space) available to store the output of his computation. The bound on the storage can be arbitrarily large (e.g., 100 Tbytes), as long as it is fixed. Given this storage bound, our protocols guarantee that even a computationally all powerful adversary gains no information about a message (except with a probability that is exponentially small in the security parameter k). The bound on storage space need only hold at the time of the message transmission. Thereafter, no additional storage space or, computational power can help the adversary in deciphering the message. We present two protocols. The first protocol, which elaborates on the autoregressive (AR) protocol of Aumann and Rabin (see Advances in Cryptology-Crypto '99, p. 65-79, 1999), employs a short secret key whose size is independent of the length of the message, but uses many public random bits. The second protocol uses an optimal number of public random bits, but employs a longer secret key. Our proof of security utilizes a novel linear algebraic technique.

IEEE Transactions on Information Theory•Jun 1, 2002•139 citations

Secure communication in minimal connectivity models

Matthew Franklin, Rebecca N. Wright

Lecture notes in computer science•Jan 1, 1998•41 citations
Abstract. 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. 1
(MATH) In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s$xi;t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n»|K| about which the adversary has essentially no information, thus at first glance apparently contradicting Shannon's bound on the key size of a perfect cipher.All previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key K had in fact to be longer than the derived one-time pad, or t had to be extremely large (tρns), or the adversary was assumed to be able to store only actual bits of R rather than arbitrary s bits of information about R, or the adversary could obtain a non-negligible amount of information about X.In this paper we prove the first non-restricted security result in the bounded-storage model, exploiting the full potential of the model: K is short, X is very long (e.g. gigabytes), t needs to be only moderately larger than s, and the security proof is optimally strong. In fact, we prove that s/t can be arbitrarily close to 1 and hence the storage bound is essentially optimal.
We address the problem of the-security of cryptographic protocols in face of future advances in computing technology and algorithmic research. The problem stems from the fact may be deemed that computations which at a given point in time may be deemed infeasible, can, in the course of years or decades, be made possible with improved hardware and/or breakthroughs in code-breaking algorithms. In such cases, the security of historical , but nonetheless highly confidential data may be in jeopardy. We present a scheme for efficient secure two-party communication with provable everlasting security. The security is guaranteed in face of any future technological advances, given the current state of of the art. Furthermore, the security of the messages is also guaranteed even if the secret encryption/decryption key is revealed in the future, The scheme is based on the bounded storage model and provides information-theoretic security in this model. The bounded storage model postulates an adversary who is computationally unbounded, and is only bounded in the amount of storage (not computation space) available to store the output of his computation. The bound on the storage can be arbitrarily large (e.g., 100 Tbytes), as long as it is fixed. Given this storage bound, our protocols guarantee that even a computationally all powerful adversary gains no information about a message (except with a probability that is exponentially small in the security parameter k). The bound on storage space need only hold at the time of the message transmission. Thereafter, no additional storage space or, computational power can help the adversary in deciphering the message. We present two protocols. The first protocol, which elaborates on the autoregressive (AR) protocol of Aumann and Rabin (see Advances in Cryptology-Crypto '99, p. 65-79, 1999), employs a short secret key whose size is independent of the length of the message, but uses many public random bits. The second protocol uses an optimal number of public random bits, but employs a longer secret key. Our proof of security utilizes a novel linear algebraic technique.