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

Quantum Information and Computation

Encryption with weakly random keys using quantum ciphertext

Jan Bouda, Matej Pivoluska, Martin Plesch

Published May 1, 2012• 0 citations
Publisher

Abstract

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.

DOI
10.26421/qic12.5-6-2

Related papers

On the Key-Uncertainty of Quantum Ciphers and the Computational Security of One-way Quantum Transmission

Ivan Damgaard, Thomas B. Pedersen, Louis Salvail

We consider the scenario where Alice wants to send a secret (classical) $n$-bit message to Bob using a classical key, and where only one-way transmission from Alice to Bob is possible. In this case, quantum communication cannot help to obtain perfect secrecy with key length smaller then $n$. We study the question of whether there might still be fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the plaintext and applies an optimal measurement on the ciphertext, his Shannon uncertainty about the key used is almost maximal. This is in contrast to the classical case where the adversary always learns $n$ bits of information on the key in a known plaintext attack. We also show that there is a limit to how different the classical and quantum cases can be: the most probable key, given matching plain- and ciphertexts, has the same probability in both the quantum and the classical cases. We suggest an application of our results in the case where only a short secret key is available and the message is much longer.

arXiv:quant-ph/0407066•Jul 8, 2004•1 citation

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•38 citations

Towards Unconditional Uncloneable Encryption

Pierre Botteron, Anne Broadbent, Eric Culf +3 more

Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext, such that two quantum adversaries are limited in their capacity of being able to simultaneously decrypt, given the key and quantum side-information produced from the ciphertext. Since its initial proposal and scheme in the random oracle model by Broadbent and Lord [TQC 2020], uncloneable encryption has developed into an important primitive at the foundation of quantum uncloneability for cryptographic primitives. Despite sustained efforts, however, the question of unconditional uncloneable encryption (and in particular of the simplest case, called an uncloneable bit) has remained elusive. Here, we propose a candidate for the unconditional uncloneable bit problem, and provide strong evidence that the adversary's success probability in the related security game converges quadratically as 1 / 2 + 1 / ( 2 K ) , where K represents the number of keys and 1 / 2 is trivially achievable. We prove this bound's validity for K ranging from 2 to 7 and demonstrate the validity up to K = 17 using computations based on the NPA hierarchy. We furthemore provide compelling heuristic evidence towards the general case. In addition, we prove an asymptotic upper bound of 5 / 8 and give a numerical upper bound of ∼ 0.5980 , which to our knowledge is the best-known value in the unconditional model.

arXiv:2410.23064•Quantum•Jul 8, 2026•1 citation

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•103 citations

Secrecy without Perfect Randomness: Cryptography with (Bounded) Weak Sources

Michael Backes A, Aniket Kate, Sebastian Meiser +1 more

Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources. In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirani (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion dierential indistinguishability in order to reflect its structural similarity to dierential privacy. More concretely, we prove that indistinguishability with uniform randomness implies dierential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve dierential indistinguishability.

•Jan 1, 2013•0 citations

The uncloneable bit exists

Archishna Bhattacharyya, Anne Broadbent, Eric Culf

We establish quantum uncloneable encryption with unconditional security, preventing two non-communicating adversaries from simultaneously decrypting a single ciphertext $-$ even when both are given the key. Our construction achieves security that approaches the ideal limit at a rate that is exponentially small in the security parameter, without employing any assumptions. Our proof invokes unitary invariance of the shared entangled state and simplifies the adversarial strategies by enforcing this symmetry. Crucially, it then rules out the sender being highly correlated with two non-communicating adversaries at once by an approximation property that we develop, for such unitarily invariant states, which yields a near-optimal bound on the probability of cloning. Consequently, no coordinated strategy beats random guessing of the encrypted bit, establishing unconditional uncloneability. This reveals the existence of an uncloneable bit in Nature and delineates a fundamental, physically enforced cryptographic primitive unavailable in classical settings.

quant-pharXiv:2603.08916•Mar 11, 2026•0 citations
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.
We consider the scenario where Alice wants to send a secret (classical) nnn-bit message to Bob using a classical key, and where only one-way transmission from Alice to Bob is possible. In this case, quantum communication cannot help to obtain perfect secrecy with key length smaller then nnn. We study the question of whether there might still be fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the plaintext and applies an optimal measurement on the ciphertext, his Shannon uncertainty about the key used is almost maximal. This is in contrast to the classical case where the adversary always learns nnn bits of information on the key in a known plaintext attack. We also show that there is a limit to how different the classical and quantum cases can be: the most probable key, given matching plain- and ciphertexts, has the same probability in both the quantum and the classical cases. We suggest an application of our results in the case where only a short secret key is available and the message is much longer.
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.
Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext, such that two quantum adversaries are limited in their capacity of being able to simultaneously decrypt, given the key and quantum side-information produced from the ciphertext. Since its initial proposal and scheme in the random oracle model by Broadbent and Lord [TQC 2020], uncloneable encryption has developed into an important primitive at the foundation of quantum uncloneability for cryptographic primitives. Despite sustained efforts, however, the question of unconditional uncloneable encryption (and in particular of the simplest case, called an uncloneable bit) has remained elusive. Here, we propose a candidate for the unconditional uncloneable bit problem, and provide strong evidence that the adversary's success probability in the related security game converges quadratically as 1 / 2 + 1 / ( 2 K ) , where K represents the number of keys and 1 / 2 is trivially achievable. We prove this bound's validity for K ranging from 2 to 7 and demonstrate the validity up to K = 17 using computations based on the NPA hierarchy. We furthemore provide compelling heuristic evidence towards the general case. In addition, we prove an asymptotic upper bound of 5 / 8 and give a numerical upper bound of ∼ 0.5980 , which to our knowledge is the best-known value in the unconditional model.
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.
Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources. In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirani (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion dierential indistinguishability in order to reflect its structural similarity to dierential privacy. More concretely, we prove that indistinguishability with uniform randomness implies dierential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve dierential indistinguishability.
We establish quantum uncloneable encryption with unconditional security, preventing two non-communicating adversaries from simultaneously decrypting a single ciphertext −-− even when both are given the key. Our construction achieves security that approaches the ideal limit at a rate that is exponentially small in the security parameter, without employing any assumptions. Our proof invokes unitary invariance of the shared entangled state and simplifies the adversarial strategies by enforcing this symmetry. Crucially, it then rules out the sender being highly correlated with two non-communicating adversaries at once by an approximation property that we develop, for such unitarily invariant states, which yields a near-optimal bound on the probability of cloning. Consequently, no coordinated strategy beats random guessing of the encrypted bit, establishing unconditional uncloneability. This reveals the existence of an uncloneable bit in Nature and delineates a fundamental, physically enforced cryptographic primitive unavailable in classical settings.