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

Cryptography in an Unbounded Computational Model

David Paul Woodruff, Marten van Dijk

Published Jan 1, 2002• 3 citations
Publisher
DOI
10.1007/3-540-46035-7_10

Related papers

On the Computational Hardness Needed for Quantum Cryptography

Zvika Brakerski, Ran Canetti, Luowen Qian

In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

arXiv:2209.04101•Leibniz international proceedings in informatics•Sep 9, 2022•56 citations

The Future of Cryptography

Princeton University Press eBooks•Oct 2, 2018•0 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

Theoretical Cryptography

Marcelo Sampaio de Alencar

River Publishers eBooks•Sep 30, 2026•0 citations

Theory of Cryptography

Salil Vadhan

•Jan 1, 2007•1 citation

Seedless extractors for device-independent quantum cryptography

Cameron Foreman, Lluís Masanes

Device-independent (DI) quantum cryptography aims at providing secure cryptography with minimal trust in, or characterisation of, the underlying quantum devices. A key step in DI protocols is randomness extraction (or privacy amplification), which typically requires a seed of additional bits with sufficient entropy and statistical independence from any bits generated during the protocol. In this work, we propose a method for extraction in DI protocols that does not require a seed and is secure against computationally unbounded quantum adversaries. The core idea is to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. We present a complete security proof in a model where the experiment uses memoryless measurement devices acting on an arbitrary joint (across all rounds) state. Our results mark a first step in this alternative, seedless, approach to extraction in DI protocols.

arXiv:2403.04713•Quantum•Mar 6, 2025•4 citations
In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.
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.
Device-independent (DI) quantum cryptography aims at providing secure cryptography with minimal trust in, or characterisation of, the underlying quantum devices. A key step in DI protocols is randomness extraction (or privacy amplification), which typically requires a seed of additional bits with sufficient entropy and statistical independence from any bits generated during the protocol. In this work, we propose a method for extraction in DI protocols that does not require a seed and is secure against computationally unbounded quantum adversaries. The core idea is to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. We present a complete security proof in a model where the experiment uses memoryless measurement devices acting on an arbitrary joint (across all rounds) state. Our results mark a first step in this alternative, seedless, approach to extraction in DI protocols.