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

Security against memory-bounded adversaries

Christian Cachin

Published Jan 20, 2003• 1 citation
Publisher

Abstract

Information-theoretic security can based on an assumption about the adversary's memory size.
DOI
10.1109/itnw.1999.814349

Related papers

Unconditional security against memory-bounded adversaries

Christian Cachin, Ueli M. Maurer

Lecture notes in computer science•Jan 1, 1997•170 citations

Powerful Primitives in the Bounded Quantum Storage Model

Barhoush, Mohammed, Louis Salvail

The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide information-theoretic secure constructions in this model for the following powerful primitives: (1) CCA1-secure symmetric key encryption, message authentication codes, and one-time programs. These schemes require no quantum memory for the honest user, while they can be made secure against adversaries with arbitrarily large memories by increasing the transmission length sufficiently. (2) CCA1-secure asymmetric key encryption, encryption tokens, signatures, signature tokens, and program broadcast. These schemes are secure against adversaries with roughly $e^{\sqrt{m}}$ quantum memory where $m$ is the quantum memory required for the honest user. All of the constructions additionally satisfy disappearing security, essentially preventing an adversary from storing and using a transmission later on.

arXiv:2302.05724•Leibniz international proceedings in informatics•Feb 11, 2023•11 citations

Information Theoretic Security Based on Bounded Observability

Jun Muramatsu, Kazuyuki Yoshimura, Peter Davis

Lecture notes in computer science•Jan 1, 2010•18 citations

Information Theoretic One-Time Programs from Geometrically Local $\text{QNC}_0$ Adversaries

Lev Stambler

We show how to construct simulation secure one-time memories, and thus one-time programs, without computational assumptions in the presence of constraints on quantum hardware. Specifically, we build one-time memories from random linear codes and quantum random access codes (QRACs) when constrained to non-adaptive, constant depth, and $D$-dimensional geometrically-local quantum circuit for some constant $D$. We place no restrictions on the adversary's classical computational power, number of qubits it can use, or the coherence time of its qubits. Notably, our construction can still be secure even in the presence of fault tolerant quantum computation as long as the input qubits are encoded in a non-fault tolerant manner (e.g. encoded as high energy states in non-ideal hardware). Unfortunately though, our construction requires decoding random linear codes and thus does not run in polynomial time. We leave open the question of whether one can construct a polynomial time information theoretically secure one-time memory from geometrically local quantum circuits. Of potentially independent interest, we develop a progress bound for information leakage via collision entropy (Renyi entropy of order $2$) along with a few key technical lemmas for a "mutual information" for collision entropies. We also develop new bounds on how much information a specific $2 \mapsto 1$ QRAC can leak about its input, which may be of independent interest as well.

arXiv:2503.22016•Mar 27, 2025•5 citations

Information Theoretic Security

Lecture notes in computer science•Jan 1, 2009•142 citations

Cryptography In the Bounded Quantum-Storage Model.

Ivan Damgård, Serge Fehr, Louis Salvail +1 more

We initiate the study of two-party cryptographic primitives \nwith unconditional security, assuming that the adversary’s \nquantum memory is of bounded size. We show that oblivious \ntransfer and bit commitment can be implemented in this \nmodel using protocols where honest parties need no quantum \nmemory, whereas an adversarial player needs quantum \nmemory of size at least n/2 in order to break the protocol, \nwhere n is the number of qubits transmitted. This is \nin sharp contrast to the classical bounded-memory model, \nwhere we can only tolerate adversaries with memory of size \nquadratic in honest players’ memory size. Our protocols \nare efficient, non-interactive and can be implemented using \ntoday’s technology. On the technical side, a new entropic \nuncertainty relation involving min-entropy is established.

•Jan 1, 2005•0 citations
The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide information-theoretic secure constructions in this model for the following powerful primitives: (1) CCA1-secure symmetric key encryption, message authentication codes, and one-time programs. These schemes require no quantum memory for the honest user, while they can be made secure against adversaries with arbitrarily large memories by increasing the transmission length sufficiently. (2) CCA1-secure asymmetric key encryption, encryption tokens, signatures, signature tokens, and program broadcast. These schemes are secure against adversaries with roughly eme^{\sqrt{m}}em​ quantum memory where mmm is the quantum memory required for the honest user. All of the constructions additionally satisfy disappearing security, essentially preventing an adversary from storing and using a transmission later on.
Information Theoretic One-Time Programs from Geometrically Local QNC0\text{QNC}_0QNC0​ Adversaries
We show how to construct simulation secure one-time memories, and thus one-time programs, without computational assumptions in the presence of constraints on quantum hardware. Specifically, we build one-time memories from random linear codes and quantum random access codes (QRACs) when constrained to non-adaptive, constant depth, and DDD-dimensional geometrically-local quantum circuit for some constant DDD. We place no restrictions on the adversary's classical computational power, number of qubits it can use, or the coherence time of its qubits. Notably, our construction can still be secure even in the presence of fault tolerant quantum computation as long as the input qubits are encoded in a non-fault tolerant manner (e.g. encoded as high energy states in non-ideal hardware). Unfortunately though, our construction requires decoding random linear codes and thus does not run in polynomial time. We leave open the question of whether one can construct a polynomial time information theoretically secure one-time memory from geometrically local quantum circuits. Of potentially independent interest, we develop a progress bound for information leakage via collision entropy (Renyi entropy of order 222) along with a few key technical lemmas for a "mutual information" for collision entropies. We also develop new bounds on how much information a specific 2↦12 \mapsto 12↦1 QRAC can leak about its input, which may be of independent interest as well.
We initiate the study of two-party cryptographic primitives \nwith unconditional security, assuming that the adversary’s \nquantum memory is of bounded size. We show that oblivious \ntransfer and bit commitment can be implemented in this \nmodel using protocols where honest parties need no quantum \nmemory, whereas an adversarial player needs quantum \nmemory of size at least n/2 in order to break the protocol, \nwhere n is the number of qubits transmitted. This is \nin sharp contrast to the classical bounded-memory model, \nwhere we can only tolerate adversaries with memory of size \nquadratic in honest players’ memory size. Our protocols \nare efficient, non-interactive and can be implemented using \ntoday’s technology. On the technical side, a new entropic \nuncertainty relation involving min-entropy is established.