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

Speak Much, Remember Little: Cryptography in the Bounded Storage Model, Revisited

Yevgeniy Dodis, Willy Quach, Daniel Wichs

Published Jan 1, 2023• 5 citations
Publisher
DOI
10.1007/978-3-031-30545-0_4

Related papers

Disappearing Cryptography in the Bounded Storage Model

Jiaxin Guan, Mark Zhandry

Lecture notes in computer science•Jan 1, 2021•9 citations

Bit Commitment in the Bounded Storage Model: Tight Bound and Simple Optimal Construction

Junji Shikata, Daisuke Yamanaka

Lecture notes in computer science•Jan 1, 2011•3 citations

Efficient Oblivious Transfer in the Bounded-Storage Model

Dowon Hong, Ku-Young Chang, Heuisu Ryu

Lecture notes in computer science•Jan 1, 2002•11 citations

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

The Quantum Complexity of Set Membership

Jaikumar Radhakrishnan, Sen, Pranab, Venkatesh, S.

We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x \in S?' can be answered. The goal is to use a small table and yet answer queries using few bitprobes. This problem was considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where lower and upper bounds were shown for this problem in the classical deterministic and randomized models. In this paper, we formulate this problem in the "quantum bitprobe model" and show tradeoff results between space and time.In this model, the storage scheme is classical but the query scheme is quantum.We show, roughly speaking, that similar lower bounds hold in the quantum model as in the classical model, which imply that the classical upper bounds are more or less tight even in the quantum case. Our lower bounds are proved using linear algebraic techniques.

arXiv:quant-ph/0007021•Jul 7, 2000•7 citations

Oblivious transfer in the bounded storage model

Yan Zong Ding

•Jan 1, 2001•0 citations
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.
We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x \in S?' can be answered. The goal is to use a small table and yet answer queries using few bitprobes. This problem was considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where lower and upper bounds were shown for this problem in the classical deterministic and randomized models. In this paper, we formulate this problem in the "quantum bitprobe model" and show tradeoff results between space and time.In this model, the storage scheme is classical but the query scheme is quantum.We show, roughly speaking, that similar lower bounds hold in the quantum model as in the classical model, which imply that the classical upper bounds are more or less tight even in the quantum case. Our lower bounds are proved using linear algebraic techniques.