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.
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 extraction of randomness from weakly random seeds is a topic of central importance in cryptography. Weak sources of randomness can be considered to be either private or public, where public sources such as the NIST randomness beacon broadcast the random bits once they are generated. The problem of device-independent randomness extraction from weak public sources against no-signalling adversaries has remained open. In this paper, we show protocols for device-independent and one-sided device-independent amplification of randomness from weak public Santha Vazirani (SV) sources that use a finite number of devices and are secure against no-signaling adversaries. Specifically, under the assumption that the device behavior is as prescribed by quantum mechanics the protocols allow for amplification of public ε-SV sources for arbitrary initial ε∈[0,0.5). On the other hand, when only the assumption of no-signaling between the components of the device is made, the protocols allow for amplification of a limited set of weak public SV sources.
Quantum Bell nonlocality allows for the design of protocols that amplify the randomness of public and arbitrarily biased Santha-Vazirani sources, a classically impossible task. Information-theoretical security in these protocols is certified in a device-independent manner, i.e. solely from the observed nonlocal statistics and without any assumption about the inner-workings of the intervening devices. On the other hand, if one is willing to trust on a complete quantum-mechanical description of a protocol's devices, the elementary scheme in which a qubit is alternatively measured in a pair of mutually unbiased bases is, straightforwardly, a protocol for randomness amplification. In this work, we study the unexplored middle ground. We prove that full randomness amplification can be achieved without requiring entanglement or a complete characterization of the intervening quantum states and measurements. Based on the energy-bounded framework introduced in [Van Himbeeck et al., Quantum 1, 33 (2017)], our prepare-and-measure protocol is able to amplify the randomness of any public Santha-Vazirani source, requiring the smallest number of inputs and outcomes possible and being secure against quantum adversaries.
Device-independent (DI) quantum cryptography provides secure cryptography with minimal trust in, or characterisation of, the used quantum devices. An essential component of DI protocols is the use of randomness extractors for privacy amplification, but these typically require an initial seed of randomness that introduces a potential vulnerability. To solve this problem, the security of seedless extractors was proven in Quantum 9, 1654 (2025). The core idea was to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. However, the large fluctuations in the Bell inequality used required many rounds to precisely estimate the Bell violation, consuming substantial randomness and making the protocol very inefficient. In this work, we present a new proof technique based on a truncation method that allows the user to estimate the protocol parameters with an asymptotically vanishing fraction of rounds and, as a consequence, achieves the optimal rate of one key bit per singlet. Notably, we prove this result using seedless extractors that can be implemented efficiently.
Recently, the physically realistic protocol amplifying the randomness of Santha-Vazirani sources producing cryptographically secure random bits was proposed; however, for reasons of practical relevance, the crucial question remained open regarding whether this can be accomplished under the minimal conditions necessary for the task. Namely, is it possible to achieve randomness amplification using only two no-signaling components and in a situation where the violation of a Bell inequality only guarantees that some outcomes of the device for specific inputs exhibit randomness? Here, we solve this question and present a device-independent protocol for randomness amplification of Santha-Vazirani sources using a device consisting of two nonsignaling components. We show that the protocol can amplify any such source that is not fully deterministic into a fully random source while tolerating a constant noise rate and prove the composable security of the protocol against general no-signaling adversaries. Our main innovation is the proof that even the partial randomness certified by the two-party Bell test [a single input-output pair (u^{*}, x^{*}) for which the conditional probability P(x^{*}|u^{*}) is bounded away from 1 for all no-signaling strategies that optimally violate the Bell inequality] can be used for amplification. We introduce the methodology of a partial tomographic procedure on the empirical statistics obtained in the Bell test that ensures that the outputs constitute a linear min-entropy source of randomness. As a technical novelty that may be of independent interest, we prove that the Santha-Vazirani source satisfies an exponential concentration property given by a recently discovered generalized Chernoff bound.
The problem of device-independent randomness amplification against no-signaling adversaries has so far been studied under the assumption that the weak source of randomness is uncorrelated with the (quantum) devices used in the amplification procedure. In this paper, we relax this assumption, and reconsider the original protocol of Colbeck and Renner using a Santha-Vazirani (SV) source. To do so, we introduce an SV-like condition for devices, namely that any string of SV source bits remains weakly random conditioned upon any other bit string from the same SV source and the outputs obtained when this further string is input into the devices. Assuming this condition, we show that a quantum device using a singlet state to violate the chained Bell inequalities leads to full randomness in the asymptotic scenario of a large number of settings, for a restricted set of SV sources (with0≤ε<(2(1/12)−1)/(2(2(1/12)+1))≈0.0144). We also study a device-independent protocol that allows for correlations between the sequence of boxes used in the protocol and the SV source bits used to choose the particular box from whose output the randomness is obtained. Assuming the SV-like condition for devices, we show that the honest parties can achieve amplification of the weak source, for the parameter range0≤ε<0.0132, against a class of attacks given as a mixture of product box sequences, made of extremal no-signaling boxes, with additional symmetry conditions. Composable security proof against this class of attacks is provided.
Quantum random number is a particularly important physical resource both for quantum communication and quantum cryptography. Quantum randomness amplification, as a key technology in quantum random number generation, has a significant counterintuitive effect: one can amplify weak randomness to almost perfect randomness by quantum systems, which is impossible in classical cryptography. In this letter, we propose an explicit quantum randomness amplification scheme with two untrusted devices, from which we could extract one single perfect random bit from weak random bits. An explicit non-malleable two-source extractor is introduced to extract perfect randomness from two independent min-entropy sources, which are derived from a Bell test with two untrusted devices. The universally composable security of the proposed protocol is proved.