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

IEEE Transactions on Information Theory

Everlasting security in the bounded storage model

Yonatan Aumann, Yan Zong Ding, Michael O. Rabin

Published Jun 1, 2002• 139 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2002.1003845

Related papers

Provable everlasting security in the bounded storage model

Michael O. Rabin, Yan Zong Ding

Traditional modern cryptography relies on unproven complexity assumptions that certain problems, such as integer factorization, are computationally hard, and the adversary is bounded in computing power. However, advances in algorithms and computing technology may render current cryptosystems insecure, and lead to the decryption of past secret messages. On the other hand, Shannon's pessimistic negative result essentially implies that if the adversary is all-powerful and has complete access to the communication line, then efficient practical solutions for information-theoretic security do not exist. This thesis is a study of cryptography in the bounded storage model, where provable everlasting security can be achieved efficiently without any complexity assumption. It first presents an efficient scheme for encryption and authentication that is provably secure against strong adaptive attacks, by an adversary who is computationally unbounded and only storage-bounded. A major new result is that the shared secret key employed by the sender and the receiver can be re-used to send an exponential number of messages. Our encryption scheme further enjoys the surprising property that even if the secret key is captured by the adversary after the transmission of the ciphertext, the secrecy of the message is assured. The above is joint work with Michael Rabin. Oblivious transfer is a cryptographic protocol that can serve as a basic primitive for all of cryptography. This thesis presents an implementation of oblivious transfer in the bounded storage model, which is again provably secure without complexity assumption.

•Jan 1, 2001•7 citations

Perfect Secrecy in the Bounded Storage Model

Divyanshu Bhardwaj, Hamid R. Sadjadpour

In this paper, we propose a new provably secure cryptosystem for two party communication that provides security in the face of new technological breakthroughs. Most of the practical cryptosystems in use today can be breached in the future with new sophisticated methods. This jeopardizes the security of older but highly confidential messages. Our protocol is based on the bounded storage model first introduced in [1]. The protocol is secure as long as there is bound on the storage, however large it may be. We also suggest methods to extend the protocol to unbounded storage models where access to adversary is limited. Our protocol is a substantial improvement over previously known protocols and uses short key and optimal number of public random bits size of which is independent of message length. The smaller and constant length of key and public random string makes the scheme more practical. The protocol generates key using elements of the additive group$\mathbb{Z}_{\mathrm{n}}$. Our protocol is very generalized and the protocol in [1] is a special case of our protocol. Our protocol is a step forward in making provably secure cryptosystems practical. An important open problem raised in [2] was designing an algorithm with short key and size of public random string$O(\mathcal{B})$where$\mathcal{B}$bounds the storage of adversary. Our protocol satisfies the conditions and is easy to implement.

Globecom•Dec 1, 2021•0 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

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 < 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 jKj about which the adversary has essentially no information, thus at rst glance apparently contradicting Shannon's bound on the key size of a perfect cipher.

ACM Symposium on Theory of Computing (STOC)•May 19, 2002•53 citations

On the Semantic Security in the General Bounded Storage Model: A New Proof

Mohammad Moltafet, Hamid R. Sadjadpour, Zouheir Rezki

In the bounded storage model introduced by Maurer, the adversary is computationally unbounded and has a bounded storage capacity. In this model, perfect secrecy is guaranteed by using a publicly available random string whose length is larger than the adversary storage capacity. The protocol proposed by Maurer is simple, from the perspective of implementation, and efficient, from the perspective of the initial secret key size and random string length. However, he provided the proof of the security for the case where the adversary can access a constant fraction of the random string and store onlyoriginal bitsof the random string. In this paper, we provide a new proof of the security of the protocol proposed by Maurer for the general bounded storage model, i.e., the adversary can access all bits of the random string, and store the output of any Boolean function on the string. We reaffirm that the protocol isabsolutely semantically securein the general bounded storage model.

arXiv:2403.18935•IEEE Transactions on Information Forensics and Security•Jan 1, 2024•2 citations

Information-theoretic security

Imre Csiszár, János Körner

Contemporary techniques of data security are primarily based on computational complexity, typically on the infeasibility of inverting certain functions using currently available mathematical techniques and computing power. Among the various protocols based on such ideas, those approved by the cryptography community appear secure enough, but mathematical and technological progress may render them insecure in the future. Indeed, past experience suggests that this is likely to happen. Information-theoretic secrecy offers provable security even against an adversary with unlimited computing power. This chapter provides a glimpse into the substantial progress that has been made towards clarifying the theoretical possibilities in this direction. Practical applications are reasonably expected within a much shorter time than capacity-achieving coding techniques have followed Shannon's discovery of the noisy channel coding theorem. Two kinds of problems will be addressed: secure transmission over insecure channels and secret key generation taking advantage of public communication. After introducing necessary concepts and tools in Section 17.1, these problems will be treated in Sections 17.2 and 17.3. Let us emphasize that the mathematical models and techniques will be similar to those in previous chapters. These models, however, are now studied from a non-cooperative aspect: a major goal is to keep (at least) one party ignorant of (at least part of) the information exchanged.

Cambridge University Press eBooks•Jun 30, 2011•10 citations
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.
Traditional modern cryptography relies on unproven complexity assumptions that certain problems, such as integer factorization, are computationally hard, and the adversary is bounded in computing power. However, advances in algorithms and computing technology may render current cryptosystems insecure, and lead to the decryption of past secret messages. On the other hand, Shannon's pessimistic negative result essentially implies that if the adversary is all-powerful and has complete access to the communication line, then efficient practical solutions for information-theoretic security do not exist. This thesis is a study of cryptography in the bounded storage model, where provable everlasting security can be achieved efficiently without any complexity assumption. It first presents an efficient scheme for encryption and authentication that is provably secure against strong adaptive attacks, by an adversary who is computationally unbounded and only storage-bounded. A major new result is that the shared secret key employed by the sender and the receiver can be re-used to send an exponential number of messages. Our encryption scheme further enjoys the surprising property that even if the secret key is captured by the adversary after the transmission of the ciphertext, the secrecy of the message is assured. The above is joint work with Michael Rabin. Oblivious transfer is a cryptographic protocol that can serve as a basic primitive for all of cryptography. This thesis presents an implementation of oblivious transfer in the bounded storage model, which is again provably secure without complexity assumption.
In this paper, we propose a new provably secure cryptosystem for two party communication that provides security in the face of new technological breakthroughs. Most of the practical cryptosystems in use today can be breached in the future with new sophisticated methods. This jeopardizes the security of older but highly confidential messages. Our protocol is based on the bounded storage model first introduced in [1]. The protocol is secure as long as there is bound on the storage, however large it may be. We also suggest methods to extend the protocol to unbounded storage models where access to adversary is limited. Our protocol is a substantial improvement over previously known protocols and uses short key and optimal number of public random bits size of which is independent of message length. The smaller and constant length of key and public random string makes the scheme more practical. The protocol generates key using elements of the additive groupZn\mathbb{Z}_{\mathrm{n}}Zn​. Our protocol is very generalized and the protocol in [1] is a special case of our protocol. Our protocol is a step forward in making provably secure cryptosystems practical. An important open problem raised in [2] was designing an algorithm with short key and size of public random stringO(B)O(\mathcal{B})O(B)whereB\mathcal{B}Bbounds the storage of adversary. Our protocol satisfies the conditions and is easy to implement.
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
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 < 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 jKj about which the adversary has essentially no information, thus at rst glance apparently contradicting Shannon's bound on the key size of a perfect cipher.
In the bounded storage model introduced by Maurer, the adversary is computationally unbounded and has a bounded storage capacity. In this model, perfect secrecy is guaranteed by using a publicly available random string whose length is larger than the adversary storage capacity. The protocol proposed by Maurer is simple, from the perspective of implementation, and efficient, from the perspective of the initial secret key size and random string length. However, he provided the proof of the security for the case where the adversary can access a constant fraction of the random string and store onlyoriginal bitsof the random string. In this paper, we provide a new proof of the security of the protocol proposed by Maurer for the general bounded storage model, i.e., the adversary can access all bits of the random string, and store the output of any Boolean function on the string. We reaffirm that the protocol isabsolutely semantically securein the general bounded storage model.
Contemporary techniques of data security are primarily based on computational complexity, typically on the infeasibility of inverting certain functions using currently available mathematical techniques and computing power. Among the various protocols based on such ideas, those approved by the cryptography community appear secure enough, but mathematical and technological progress may render them insecure in the future. Indeed, past experience suggests that this is likely to happen. Information-theoretic secrecy offers provable security even against an adversary with unlimited computing power. This chapter provides a glimpse into the substantial progress that has been made towards clarifying the theoretical possibilities in this direction. Practical applications are reasonably expected within a much shorter time than capacity-achieving coding techniques have followed Shannon's discovery of the noisy channel coding theorem. Two kinds of problems will be addressed: secure transmission over insecure channels and secret key generation taking advantage of public communication. After introducing necessary concepts and tools in Section 17.1, these problems will be treated in Sections 17.2 and 17.3. Let us emphasize that the mathematical models and techniques will be similar to those in previous chapters. These models, however, are now studied from a non-cooperative aspect: a major goal is to keep (at least) one party ignorant of (at least part of) the information exchanged.