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

On the Impossibility of Extracting Classical Randomness Using a Quantum Computer

Yevgeniy Dodis, Renato Renner

Published Dec 1, 2006• 0 citations
OpenAlex

Abstract

Abstract. In this work we initiate the question of whether quantum computers can provide us with an almost perfect source of classical randomness, and more generally, suffice for classical cryptographic tasks, such as encryption. Indeed, it was observed [SV86,MP91,DOPS04] that classical computers are insufficient for either one of these tasks when all they have access to is a realistic imperfect source of randomness, such as the Santha-Vazirani source. We answer this question in the negative, even in the following very restrictive model. We generously assume that quantum computation is error-free, and all the errors come in the measurements. We further assume that all the measurement errors are not only small but also detectable: namely, all that can happen is that with a small probability p ⊥ ≤ δ the (perfectly performed) measurement will result in some distinguished symbol ⊥ (indicating an “erasure”). Specifically, we assume that if an element x was supposed to be observed with probability px, in reality it might be observed with probability p ′ x ∈ [(1−δ)px, px], for some small δ> 0 (so that p ⊥ = 1 − P

Related papers

On the impossibility of extracting classical randomness using a quantum computer

Yevgeniy Dodis, Renato Renner

In this work we initiate the question of whether quantum devices can provide us with an almost perfect source of classical randomness, and more generally, suffice for classical cryptographic tasks, such as encryption. Indeed, it is well known that classical computers are insufficient for either one of these tasks when all they have access to is a realistic imperfect source of randomness. On the other hand, quantum physics is inherently probabilistic which suggests that perhaps quantum computers can provide a reasonable way to overcome the above mentioned impossibility results. However, we show that this is not the case in a realistic setting where observations (measurements) are subject to noise.

arXiv:quant-ph/0612012•Dec 1, 2006•2 citations

On the (Im)possibility of Cryptography with Imperfect Randomness

Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran +1 more

We investigate the feasibility of a variety of cryptographic tasks with imperfect randomness. The kind of imperfect randomness we consider are entropy sources, such as those considered by Santha and Vazirani, Chor and Goldreich, and Zuckerman. We show the following: (1) certain cryptographic tasks like bit commitment, encryption, secret sharing, zero-knowledge, non-interactive zero-knowledge, and secure two-party computation for any non-trivial junction are impossible to realize if parties have access to entropy sources with slightly less-than-perfect entropy, i.e., sources with imperfect randomness. These results are unconditional and do not rely on any un-proven assumption. (2) On the other hand, based on stronger variants of standard assumptions, secure signature schemes are possible with imperfect entropy sources. As another positive result, we show (without any unproven assumption) that interactive proofs can be made sound with respect to imperfect entropy sources.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•110 citations

Quantum Error Correction

Phillip Kaye, Raymond Laflamme, Michele Mosca

A mathematical model of computation is an idealized abstraction. We design algorithms and perform analysis on the assumption that the mathematical operations we specify will be carried out exactly, and without error. Physical devices that implement an abstract model of computation are imperfect and of limited precision. For example, when a digital circuit is implemented on a physical circuit board, unwanted electrical noise in the environment may cause components to behave differently than expected, and may cause voltage levels (bit-values) to change. These sources of error must be controlled or compensated for, or else the resulting loss of efficiency may reduce the power of the information-processing device. If individual steps in a computation succeed with probability p, then a computation involving t sequential steps will have a success probability that decreases exponentially as pt. Although it may be impossible to eliminate the sources of errors, we can devise schemes to allow us to recover from errors using a reasonable amount of additional resources. Many classical digital computing devices use error-correcting codes to perform detection of and recovery from errors. The theory of error-correcting codes is itself a mathematical abstraction, but it is one that explicitly accounts for errors introduced by the imperfection and imprecision of realistic devices. This theory has proven extremely effective in allowing engineers to build computing devices that are resilient against errors. Quantum computers are more susceptible to errors than classical digital computers, because quantum mechanical systems are more delicate and more difficult to control. If large-scale quantum computers are to be possible, a theory of quantum error correction is needed. The discovery of quantum error correction has given researchers confidence that realistic large-scale quantum computing devices can be built despite the presence of errors. We begin by considering fundamental concepts for error correction in a classical setting. We will focus on three of these concepts: (a) the characterization of the error model, (b) the introduction of redundancy through encoding, and (c) an error recovery procedure. We will later see that these concepts generalize quite naturally for quantum error correction.

Oxford University Press eBooks•Nov 16, 2006•0 citations

Quantum to Classical Randomness Extractors

Mario Berta, Omar Fawzi, Stephanie Wehner

The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.

arXiv:1111.2026•IEEE Transactions on Information Theory•Jan 24, 2014•50 citations

Device-Independent Randomness Amplification and Privatization

Max Kessler, Rotem Arnon-Friedman

Secret and perfect randomness is an essential resource in cryptography. Yet, it is not even clear that such exists. It is well known that the tools of classical computer science do not allow us to create secret and perfect randomness from a single weak public source. Quantum physics, on the other hand, allows for such a process, even in the most paranoid cryptographic sense termed “device-independent quantum cryptography”. We propose and prove the security of a new device-independent protocol that takes any single public Santha-Vazirani source as input and creates a secret close to uniform string in the presence of a quantum adversary. Our work is the first to achieve randomness amplification with all the following properties: (1) amplification and “privatization” of a public Santha-Vazirani source with arbitrary bias (2) the use of a device with only two components (3) non-vanishing extraction rate and (4) maximal noise tolerance. In particular, this implies that our protocol is the first protocol that can possibly be implemented with reachable parameters. We achieve these by combining three new tools: a particular family of Bell inequalities, a proof technique to lower bound entropy in the device-independent setting, and a framework for quantum-proof multi-source extractors.

arXiv:1705.04148•IEEE Journal on Selected Areas in Information Theory•Jul 31, 2020•71 citations

Encryption with weakly random keys using quantum ciphertext

Jan Bouda, Matej Pivoluska, Martin Plesch

The lack of perfect randomness can cause significant problems in securing communication between two parties. McInnes and Pinkas \cite{McInnesPinkas-ImpossibilityofPrivate-1991} proved that unconditionally secure encryption is impossible when the key is sampled from a weak random source. The adversary can always gain some information about the plaintext, regardless of the cryptosystem design. Most notably, the adversary can obtain full information about the plaintext if he has access to just two bits of information about the source (irrespective on length of the key). In this paper we show that for every weak random source there is a cryptosystem with a classical plaintext, a classical key, and a quantum ciphertext that bounds the adversary's probability $p$ to guess correctly the plaintext strictly under the McInnes-Pinkas bound, except for a single case, where it coincides with the bound. In addition, regardless of the source of randomness, the adversary's probability $p$ is strictly smaller than $1$ as long as there is some uncertainty in the key (Shannon/min-entropy is non-zero). These results are another demonstration that quantum information processing can solve cryptographic tasks with strictly higher security than classical information processing.

arXiv:1109.1943•Quantum Information and Computation•May 1, 2012•0 citations
Abstract. In this work we initiate the question of whether quantum computers can provide us with an almost perfect source of classical randomness, and more generally, suffice for classical cryptographic tasks, such as encryption. Indeed, it was observed [SV86,MP91,DOPS04] that classical computers are insufficient for either one of these tasks when all they have access to is a realistic imperfect source of randomness, such as the Santha-Vazirani source. We answer this question in the negative, even in the following very restrictive model. We generously assume that quantum computation is error-free, and all the errors come in the measurements. We further assume that all the measurement errors are not only small but also detectable: namely, all that can happen is that with a small probability p ⊥ ≤ δ the (perfectly performed) measurement will result in some distinguished symbol ⊥ (indicating an “erasure”). Specifically, we assume that if an element x was supposed to be observed with probability px, in reality it might be observed with probability p ′ x ∈ [(1−δ)px, px], for some small δ> 0 (so that p ⊥ = 1 − P
In this work we initiate the question of whether quantum devices can provide us with an almost perfect source of classical randomness, and more generally, suffice for classical cryptographic tasks, such as encryption. Indeed, it is well known that classical computers are insufficient for either one of these tasks when all they have access to is a realistic imperfect source of randomness. On the other hand, quantum physics is inherently probabilistic which suggests that perhaps quantum computers can provide a reasonable way to overcome the above mentioned impossibility results. However, we show that this is not the case in a realistic setting where observations (measurements) are subject to noise.
We investigate the feasibility of a variety of cryptographic tasks with imperfect randomness. The kind of imperfect randomness we consider are entropy sources, such as those considered by Santha and Vazirani, Chor and Goldreich, and Zuckerman. We show the following: (1) certain cryptographic tasks like bit commitment, encryption, secret sharing, zero-knowledge, non-interactive zero-knowledge, and secure two-party computation for any non-trivial junction are impossible to realize if parties have access to entropy sources with slightly less-than-perfect entropy, i.e., sources with imperfect randomness. These results are unconditional and do not rely on any un-proven assumption. (2) On the other hand, based on stronger variants of standard assumptions, secure signature schemes are possible with imperfect entropy sources. As another positive result, we show (without any unproven assumption) that interactive proofs can be made sound with respect to imperfect entropy sources.
A mathematical model of computation is an idealized abstraction. We design algorithms and perform analysis on the assumption that the mathematical operations we specify will be carried out exactly, and without error. Physical devices that implement an abstract model of computation are imperfect and of limited precision. For example, when a digital circuit is implemented on a physical circuit board, unwanted electrical noise in the environment may cause components to behave differently than expected, and may cause voltage levels (bit-values) to change. These sources of error must be controlled or compensated for, or else the resulting loss of efficiency may reduce the power of the information-processing device. If individual steps in a computation succeed with probability p, then a computation involving t sequential steps will have a success probability that decreases exponentially as pt. Although it may be impossible to eliminate the sources of errors, we can devise schemes to allow us to recover from errors using a reasonable amount of additional resources. Many classical digital computing devices use error-correcting codes to perform detection of and recovery from errors. The theory of error-correcting codes is itself a mathematical abstraction, but it is one that explicitly accounts for errors introduced by the imperfection and imprecision of realistic devices. This theory has proven extremely effective in allowing engineers to build computing devices that are resilient against errors. Quantum computers are more susceptible to errors than classical digital computers, because quantum mechanical systems are more delicate and more difficult to control. If large-scale quantum computers are to be possible, a theory of quantum error correction is needed. The discovery of quantum error correction has given researchers confidence that realistic large-scale quantum computing devices can be built despite the presence of errors. We begin by considering fundamental concepts for error correction in a classical setting. We will focus on three of these concepts: (a) the characterization of the error model, (b) the introduction of redundancy through encoding, and (c) an error recovery procedure. We will later see that these concepts generalize quite naturally for quantum error correction.
The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.
Secret and perfect randomness is an essential resource in cryptography. Yet, it is not even clear that such exists. It is well known that the tools of classical computer science do not allow us to create secret and perfect randomness from a single weak public source. Quantum physics, on the other hand, allows for such a process, even in the most paranoid cryptographic sense termed “device-independent quantum cryptography”. We propose and prove the security of a new device-independent protocol that takes any single public Santha-Vazirani source as input and creates a secret close to uniform string in the presence of a quantum adversary. Our work is the first to achieve randomness amplification with all the following properties: (1) amplification and “privatization” of a public Santha-Vazirani source with arbitrary bias (2) the use of a device with only two components (3) non-vanishing extraction rate and (4) maximal noise tolerance. In particular, this implies that our protocol is the first protocol that can possibly be implemented with reachable parameters. We achieve these by combining three new tools: a particular family of Bell inequalities, a proof technique to lower bound entropy in the device-independent setting, and a framework for quantum-proof multi-source extractors.
The lack of perfect randomness can cause significant problems in securing communication between two parties. McInnes and Pinkas \cite{McInnesPinkas-ImpossibilityofPrivate-1991} proved that unconditionally secure encryption is impossible when the key is sampled from a weak random source. The adversary can always gain some information about the plaintext, regardless of the cryptosystem design. Most notably, the adversary can obtain full information about the plaintext if he has access to just two bits of information about the source (irrespective on length of the key). In this paper we show that for every weak random source there is a cryptosystem with a classical plaintext, a classical key, and a quantum ciphertext that bounds the adversary's probability ppp to guess correctly the plaintext strictly under the McInnes-Pinkas bound, except for a single case, where it coincides with the bound. In addition, regardless of the source of randomness, the adversary's probability ppp is strictly smaller than 111 as long as there is some uncertainty in the key (Shannon/min-entropy is non-zero). These results are another demonstration that quantum information processing can solve cryptographic tasks with strictly higher security than classical information processing.