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.
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 study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new challenges such as potential entanglement in the side information, it is not a prior clear under what conditions do quantum multi-source extractors exist; the only previous work is [KK12], where the classical inner-product two-source extractors of [CG88] and [DEOR04] are shown to be quantum secure in the restricted Independent Adversary (IA) Model and entangled Bounded Storage (BS) Model. In this paper we propose a new model called General Entangled (GE) Adversary Model, which allows arbitrary entanglement in the side information and subsumes both the IA model and the BS model. We proceed to show how to construct GE-secure quantum multi-source extractors. To that end, we propose another model called One-sided Adversary (OA) Model, which is weaker than all the above models. Somewhat surprisingly, we establish equivalence between strong OA-security and strong GE-security. As a result, all classical multi-source extractors can either directly work, or be modified to work in the GE model at the cost of one extra random source. Thus, our constructions essentially match the best known constructions of classical multi-source extractors. We also apply our techniques to two important problems in cryptography and distributed computing --- privacy amplification and network extractor. We show that as long as the sources have certain amounts of conditional min-entropy in our GE model (even with entangled quantum side information), we can design very efficient privacy amplification protocols and network extractors.
Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.
A natural measure for the amount of quantum information that a physical system E holds about another system A = A1, .. . , Anis given by the min-entropy Hmin(A|E). In particular, the min-entropy measures the amount of entanglement between E and A, and is the relevant measure when analyzing a wide variety of problems ranging from randomness extraction in quantum cryptography, decoupling used in channel coding, to physical processes such as thermalization or the thermodynamic work cost (or gain) of erasing a quantum system. As such, it is a central question to determine the behavior of the minentropy after some process M. is applied to the system A. Here, we introduce a new generic tool relating the resulting min-entropy to the original one, and apply it to several settings of interest. A simple example of such a process is the one of sampling, where a subset S of the systems A1, ... , An is selected at random. Our tool allows us to quantify the entanglement that E has with the selected systems AS, i.e., Hmin(AS|ES) as a function of the original Hmin(A|E). We give two applications of this result. First, it directly provides the first local quantum-to-classical randomness extractors for use in quantum cryptography, as well as decoupling operations acting on only a small fraction AS of the input A. Moreover, it gives lower bounds on the dimension of k-out-of-n fully quantum random access encodings. Another natural example of such a process is a measurement in, e.g., BB84 bases commonly used in quantum cryptography. We establish the first entropic uncertainty relations with quantum side information that are nontrivial whenever E is not maximally entangled with A. As a consequence, we are able to prove optimality of quantum cryptographic schemes in the noisy-storage model. This model allows for the secure implementation of two-party cryptographic primitives under the assumption that the adversary cannot store quantum information perfectly. A special case is the bounded-quantum-storage model (BQSM), which assumes that the adversary's quantum memory device is noise free but limited in size. Ever since the inception of the BQSM, it has been a vexing open question to determine whether the security is possible as long as the adversary can only.
Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown.
How to generate provably true randomness with minimal assumptions? This question is important not only for the efficiency and the security of information processing, but also for understanding how extremely unpredictable events are possible in Nature. All current solutions require special structures in the initial source of randomness, or a certain independence relation among two or more sources. Both types of assumptions are impossible to test and difficult to guarantee in practice. Here we show how this fundamental limit can be circumvented by extractors that base security on the validity of physical laws and extract randomness from untrusted quantum devices. In conjunction with the recent work of Miller and Shi (arXiv:1402:0489), our physical randomness extractor uses just a single and general weak source, produces an arbitrarily long and near-uniform output, with a close-to-optimal error, secure against all-powerful quantum adversaries, and tolerating a constant level of implementation imprecision. The source necessarily needs to be unpredictable to the devices, but otherwise can even be known to the adversary. Our central technical contribution, the Equivalence Lemma, provides a general principle for proving composition security of untrusted-device protocols. It implies that unbounded randomness expansion can be achieved simply by cross-feeding any two expansion protocols. In particular, such an unbounded expansion can be made robust, which is known for the first time. Another significant implication is, it enables the secure randomness generation and key distribution using public randomness, such as that broadcast by NIST's Randomness Beacon. Our protocol also provides a method for refuting local hidden variable theories under a weak assumption on the available randomness for choosing the measurement settings.
It is a well-known fact in classical information theory that no deterministic procedure can extract close-to-ideal randomness from an arbitrary entropy source. On the other hand, if additional knowledge about the source is available -- e.g., that it is a sequence of independent Bernoulli trials -- then deterministic extractors do exist. For quantum entropy sources, where in addition to classical random variables we consider quantum side information, the use of extra knowledge about their structure was pioneered in a recent publication [C. Foreman and L. Masanes, Quantum 9, 1654 (2025)]. In that work, the authors provide deterministic extractors for device-independent randomness generation with memoryless devices achieving a sufficiently high CHSH score. In this work, we port their construction to the prepare-and-measure scenario. Specifically, we prove that the considered functions are also extractors for memoryless devices in settings with partial trust, either in the state preparation or in the measurement, as well as in a semi-device-independent setting under an overlap assumption on the prepared quantum states. Within this last setting, we simulate the resulting randomness generation protocol on a novel and experimentally relevant family of behaviors, observing positive key rates already for 7×103 rounds.