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.
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.
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.
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.
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.
The peculiar properties of quantum mechanics enable possibilities not allowed by classical physics. In particular, two parties can generate a random, secret key at a distance, even though an eavesdropper can do anything permitted by the laws of physics. Measuring the quantum properties of the signals generating the key, would ultimately change them, and thus reveal the eavesdropper’s presence. This exchange of a random, secret key is known as quantum cryptography.\n\nQuantum cryptography can be, and has been proven unconditionally secure using perfect devices. However, when quantum cryptography is implemented, one must use components available with current technology. These are usually imperfect. Although the security of quantum cryptography has been proven for components with certain imperfections, the question remains: can quantum cryptography be implemented in a provable, unconditionally secure way, using components available with current technology? This thesis contains both a theoretical, and an experimental contribution to the answer of this question. On the experimental side, components used in, and complete quantum cryptography systems have been carefully examined for security loopholes. In particular, it turned out that two commercial quantum cryptography systems contained loopholes, which would allow an eavesdropper to capture the full secret key, without exposing her presence. Furthermore, this detector control attack could be implemented with current technology. The attack is applicable against a variety of quantum cryptography implementations and protocols.\n\nThe theoretical contribution consists of security proofs for quantum cryptography in a very general setting. Precisely, the security is proven with arbitrary individual imperfections in the source and detectors. These proofs should make it possible to use a wide array of imperfect devices in implementations of quantum cryptography.\n\nFinally, a secure detection scheme is proposed, immune to the detector control attack and compatible with those security proofs. Therefore, if this scheme is implemented correctly, it offers provable security.
Measurements on entangled quantum systems necessarily yield outcomes that are intrinsically unpredictable if they violate a Bell inequality. This property can be used to generate certified randomness in a device-independent way, i.e., without making detailed assumptions about the internal working of the quantum devices used to generate the random numbers. Furthermore these numbers are also private; i.e., they appear random not only to the user but also to any adversary that might possess a perfect description of the devices. Since this process requires a small initial random seed to sample the behavior of the quantum devices and to extract uniform randomness from the raw outputs of the devices, one usually speaks of device-independent randomness expansion. The purpose of this paper is twofold. First, we point out that in most real, practical situations, where the concept of device independence is used as a protection against unintentional flaws or failures of the quantum apparatuses, it is sufficient to show that the generated string is random with respect to an adversary that holds only classical side information; i.e., proving randomness against quantum side information is not necessary. Furthermore, the initial random seed does not need to be private with respect to the adversary, provided that it is generated in a way that is independent from the measured systems. The devices, however, will generate cryptographically secure randomness that cannot be predicted by the adversary, and thus one can, given access to free public randomness, talk about private randomness generation. The theoretical tools to quantify the generated randomness according to these criteria were already introduced in S. Pironio et al. [Nature (London) 464, 1021 (2010)], but the final results were improperly formulated. The second aim of this paper is to correct this inaccurate formulation and therefore lay out a precise theoretical framework for practical device-independent randomness generation.
According to quantum theory, measurements generate random outcomes, in stark contrast with classical mechanics. This raises the question of whether there could exist an extension of the theory that removes this indeterminism, as suspected by Einstein, Podolsky and Rosen. Although this has been shown to be impossible, existing results do not imply that the current theory is maximally informative. Here we ask the more general question of whether any improved predictions can be achieved by any extension of quantum theory. Under the assumption that measurements can be chosen freely, we answer this question in the negative: no extension of quantum theory can give more information about the outcomes of future measurements than quantum theory itself. Our result has significance for the foundations of quantum mechanics, as well as applications to tasks that exploit the inherent randomness in quantum theory, such as quantum cryptography. Quantum-mechanical predictions are generally probabilistic. Here, assuming freely chosen measurements, it is shown that enhanced predictions are not possible and, thus, randomness is inherent in quantum theory: a result that has applications in fields such as quantum cryptography.