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

arXiv:2506.17020

Accumulation of Device-Independent Quantum Randomness against Time-Ordered No-Signalling Adversaries

Ramanathan, Ravishankar, Liu, Yuan, Wu, Yutian

Published Jun 20, 2025• 0 citations
arXivHTMLPDF

Abstract

The question of security of practical device-independent protocols against no-signalling adversaries, the ultimate form of cryptographic security, has remained open. A key ingredient is to identify how the entropy in the raw outputs of a Bell test accumulates over $n$ sequential runs (termed time-ordered no-signalling) against a no-signalling adversary. Previous numerical and analytical investigations for small $n$ ($\leq 5$) had suggested that the min-entropy might not accumulate linearly in contrast to the case of quantum adversaries. Here we point out that despite the findings for small $n$, the min-entropy does in fact accumulate linearly for large $n$. We illustrate the difference in randomness accumulation against quantum and no-signalling adversaries with the paradigmatic example of the Chained Bell test for which we analytically derive the min-entropy. Finally, we illustrate the power of the no-signalling adversary by providing a class of attacks that allow an eavesdropper to perfectly guess the outputs of one player in general bipartite Pseudotelepathy games.

DOI
10.48550/arxiv.2506.17020

Related papers

Generalised entropy accumulation

Tony Metger, Omar Fawzi, David Sutter +1 more

The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system Aiand updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs $A_{1},\ldots,\ A_{n}$ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition.Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•35 citations

Simple and Tight Device-Independent Security Proofs

Rotem Arnon-Friedman, Renato Renner, Thomas Vidick

Device-independent security is the gold standard for quantum cryptography: not only is security based entirely on the laws of quantum mechanics, but it holds irrespective of any a priori assumptions on the quantum devices used in a protocol, making it particularly applicable in a quantum-wary environment. While the existence of device-independent protocols for tasks such as randomness expansion and quantum key distribution has recently been established, the underlying proofs of security remain very challenging, yield rather poor key rates, and demand very high quality quantum devices, thus making them all but impossible to implement in practice. We introduce a technique for the analysis of device-independent cryptographic protocols. We provide a flexible protocol and give a security proof that provides quantitative bounds that are asymptotically tight, even in the presence of general quantum adversaries. At a high level our approach amounts to establishing a reduction to the scenario in which the untrusted device operates in an identical and independent way in each round of the protocol. This is achieved by leveraging the sequential nature of the protocol and makes use of a newly developed tool, the “entropy accumulation theorem” of Dupuis, Fawzi, and Renner [ Entropy Accumulation, preprint, 2016]. As concrete applications we give simple and modular security proofs for device-independent quantum key distribution and randomness expansion protocols based on the CHSH inequality. For both tasks, we establish essentially optimal asymptotic key rates and noise tolerance. In view of recent experimental progress, which has culminated in loophole-free Bell tests, it is likely that these protocols can be practically implemented in the near future.

arXiv:1607.01797•SIAM Journal on Computing•Jan 1, 2019•155 citations

Free will in device-independent cryptography

James E. Pope

Device-independent cryptography provides security in various tasks whilst removing an assumption that cryptographers previously thought of as crucial -- complete trust in the machinations of their experimental apparatus. The theory of Bell inequalities as a proof of indeterminism within nature allows for secure device-independent schemes requiring neither trust in the cryptographers' devices nor reliance on the completeness of quantum mechanics. However, the extreme paranoia attributable to the relaxed assumptions within device independence requires an explicit consideration of the previously assumed ability of the experimenters to freely make random choices. This thesis addresses the so-called `free will loophole', presenting Bell tests and associated cryptographic protocols robust against adversarial manipulation of the random number generators with which measurements in a Bell test are selected. We present several quantitative measures for this experimental free will, otherwise known as measurement dependence. We discuss how an eavesdropper maliciously preprogramming the experimenters' untrusted devices can falsely simulate the violation of a Bell inequality. We also bound the amount of Bell violation achievable within a certain degree of measurement dependence. This analysis extends to device-independent randomness expansion, bounding the guessing probability and estimating the amount of privacy amplification required to distil private randomness. The protocol is secure against either arbitrary no-signalling or quantum adversaries. We also consider device-independent key distribution, studying adversarial models that exploit the free will loophole. Finally, we examine a model correlated between the random number generators and Bell devices across multiple runs of a Bell test. This enables an explicit exposition of the optimal cheating strategy and how the correlations manifest themselves within this strategy. We prove that there remain Bell violations for a sufficiently high, yet non-maximal degree of measurement dependence which cannot be simulated by a classical attack, regardless of how many runs of the experiment those choices are correlated over.

•Jan 1, 2014•0 citations

Seedless extractors for device-independent quantum cryptography

Cameron Foreman, Lluís Masanes

Device-independent (DI) quantum cryptography aims at providing secure cryptography with minimal trust in, or characterisation of, the underlying quantum devices. A key step in DI protocols is randomness extraction (or privacy amplification), which typically requires a seed of additional bits with sufficient entropy and statistical independence from any bits generated during the protocol. In this work, we propose a method for extraction in DI protocols that does not require a seed and is secure against computationally unbounded quantum adversaries. The core idea is to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. We present a complete security proof in a model where the experiment uses memoryless measurement devices acting on an arbitrary joint (across all rounds) state. Our results mark a first step in this alternative, seedless, approach to extraction in DI protocols.

arXiv:2403.04713•Quantum•Mar 6, 2025•1 citation

Practical device-independent quantum cryptography via entropy accumulation

Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi +2 more

Device-independent cryptography goes beyond conventional quantum cryptography by providing security that holds independently of the quality of the underlying physical devices. Device-independent protocols are based on the quantum phenomena of non-locality and the violation of Bell inequalities. This high level of security could so far only be established under conditions which are not achievable experimentally. Here we present a property of entropy, termed "entropy accumulation", which asserts that the total amount of entropy of a large system is the sum of its parts. We use this property to prove the security of cryptographic protocols, including device-independent quantum key distribution, while achieving essentially optimal parameters. Recent experimental progress, which enabled loophole-free Bell tests, suggests that the achieved parameters are technologically accessible. Our work hence provides the theoretical groundwork for experimental demonstrations of device-independent cryptography.

Nature Communications•Jan 25, 2018•270 citations

Quantifying the randomness of copies of noisy Popescu-Rohrlich correlations

Boris Bourdoncle, Stefano Pironio, Antonio Acín

In a no-signaling world, the outputs of a nonlocal box cannot be completely predetermined, a feature that is exploited in many quantum information protocols exploiting nonlocality, such as device-independent randomness generation and quantum key distribution. This relation between nonlocality and randomness can be formally quantified through the min-entropy, a measure of the unpredictability of the outputs that holds conditioned on the knowledge of any adversary that is limited only by the no-signaling principle. This quantity can easily be computed for the noisy Popescu-Rohrlich (PR) box, the paradigmatic example of nonlocality. In this paper, we consider the min-entropy associated to several copies of noisy PR boxes. In the case where $n$ noisy PR boxes are implemented using $n$ noncommunicating pairs of devices, it is known that each PR box behaves as an independent biased coin: the min-entropy per PR box is constant with the number of copies. We show that this does not hold in more general scenarios where several noisy PR boxes are implemented from a single pair of devices, either used sequentially $n$ times or producing $n$ outcome bits in a single run. In this case, the min-entropy per PR box is smaller than the min-entropy of a single PR box, and it decreases as the number of copies increases.

arXiv:1807.04674•Physical Review A•Oct 25, 2018•2 citations
The question of security of practical device-independent protocols against no-signalling adversaries, the ultimate form of cryptographic security, has remained open. A key ingredient is to identify how the entropy in the raw outputs of a Bell test accumulates over nnn sequential runs (termed time-ordered no-signalling) against a no-signalling adversary. Previous numerical and analytical investigations for small nnn (≤5\leq 5≤5) had suggested that the min-entropy might not accumulate linearly in contrast to the case of quantum adversaries. Here we point out that despite the findings for small nnn, the min-entropy does in fact accumulate linearly for large nnn. We illustrate the difference in randomness accumulation against quantum and no-signalling adversaries with the paradigmatic example of the Chained Bell test for which we analytically derive the min-entropy. Finally, we illustrate the power of the no-signalling adversary by providing a class of attacks that allow an eavesdropper to perfectly guess the outputs of one player in general bipartite Pseudotelepathy games.
The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system Aiand updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs A1,…, AnA_{1},\ldots,\ A_{n}A1​,…, An​ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition.Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.
Device-independent security is the gold standard for quantum cryptography: not only is security based entirely on the laws of quantum mechanics, but it holds irrespective of any a priori assumptions on the quantum devices used in a protocol, making it particularly applicable in a quantum-wary environment. While the existence of device-independent protocols for tasks such as randomness expansion and quantum key distribution has recently been established, the underlying proofs of security remain very challenging, yield rather poor key rates, and demand very high quality quantum devices, thus making them all but impossible to implement in practice. We introduce a technique for the analysis of device-independent cryptographic protocols. We provide a flexible protocol and give a security proof that provides quantitative bounds that are asymptotically tight, even in the presence of general quantum adversaries. At a high level our approach amounts to establishing a reduction to the scenario in which the untrusted device operates in an identical and independent way in each round of the protocol. This is achieved by leveraging the sequential nature of the protocol and makes use of a newly developed tool, the “entropy accumulation theorem” of Dupuis, Fawzi, and Renner [ Entropy Accumulation, preprint, 2016]. As concrete applications we give simple and modular security proofs for device-independent quantum key distribution and randomness expansion protocols based on the CHSH inequality. For both tasks, we establish essentially optimal asymptotic key rates and noise tolerance. In view of recent experimental progress, which has culminated in loophole-free Bell tests, it is likely that these protocols can be practically implemented in the near future.
Device-independent cryptography provides security in various tasks whilst removing an assumption that cryptographers previously thought of as crucial -- complete trust in the machinations of their experimental apparatus. The theory of Bell inequalities as a proof of indeterminism within nature allows for secure device-independent schemes requiring neither trust in the cryptographers' devices nor reliance on the completeness of quantum mechanics. However, the extreme paranoia attributable to the relaxed assumptions within device independence requires an explicit consideration of the previously assumed ability of the experimenters to freely make random choices. This thesis addresses the so-called `free will loophole', presenting Bell tests and associated cryptographic protocols robust against adversarial manipulation of the random number generators with which measurements in a Bell test are selected. We present several quantitative measures for this experimental free will, otherwise known as measurement dependence. We discuss how an eavesdropper maliciously preprogramming the experimenters' untrusted devices can falsely simulate the violation of a Bell inequality. We also bound the amount of Bell violation achievable within a certain degree of measurement dependence. This analysis extends to device-independent randomness expansion, bounding the guessing probability and estimating the amount of privacy amplification required to distil private randomness. The protocol is secure against either arbitrary no-signalling or quantum adversaries. We also consider device-independent key distribution, studying adversarial models that exploit the free will loophole. Finally, we examine a model correlated between the random number generators and Bell devices across multiple runs of a Bell test. This enables an explicit exposition of the optimal cheating strategy and how the correlations manifest themselves within this strategy. We prove that there remain Bell violations for a sufficiently high, yet non-maximal degree of measurement dependence which cannot be simulated by a classical attack, regardless of how many runs of the experiment those choices are correlated over.
Device-independent (DI) quantum cryptography aims at providing secure cryptography with minimal trust in, or characterisation of, the underlying quantum devices. A key step in DI protocols is randomness extraction (or privacy amplification), which typically requires a seed of additional bits with sufficient entropy and statistical independence from any bits generated during the protocol. In this work, we propose a method for extraction in DI protocols that does not require a seed and is secure against computationally unbounded quantum adversaries. The core idea is to use the Bell violation of the raw data, rather than its min-entropy, as the extractor promise. We present a complete security proof in a model where the experiment uses memoryless measurement devices acting on an arbitrary joint (across all rounds) state. Our results mark a first step in this alternative, seedless, approach to extraction in DI protocols.
Device-independent cryptography goes beyond conventional quantum cryptography by providing security that holds independently of the quality of the underlying physical devices. Device-independent protocols are based on the quantum phenomena of non-locality and the violation of Bell inequalities. This high level of security could so far only be established under conditions which are not achievable experimentally. Here we present a property of entropy, termed "entropy accumulation", which asserts that the total amount of entropy of a large system is the sum of its parts. We use this property to prove the security of cryptographic protocols, including device-independent quantum key distribution, while achieving essentially optimal parameters. Recent experimental progress, which enabled loophole-free Bell tests, suggests that the achieved parameters are technologically accessible. Our work hence provides the theoretical groundwork for experimental demonstrations of device-independent cryptography.
In a no-signaling world, the outputs of a nonlocal box cannot be completely predetermined, a feature that is exploited in many quantum information protocols exploiting nonlocality, such as device-independent randomness generation and quantum key distribution. This relation between nonlocality and randomness can be formally quantified through the min-entropy, a measure of the unpredictability of the outputs that holds conditioned on the knowledge of any adversary that is limited only by the no-signaling principle. This quantity can easily be computed for the noisy Popescu-Rohrlich (PR) box, the paradigmatic example of nonlocality. In this paper, we consider the min-entropy associated to several copies of noisy PR boxes. In the case where nnn noisy PR boxes are implemented using nnn noncommunicating pairs of devices, it is known that each PR box behaves as an independent biased coin: the min-entropy per PR box is constant with the number of copies. We show that this does not hold in more general scenarios where several noisy PR boxes are implemented from a single pair of devices, either used sequentially nnn times or producing nnn outcome bits in a single run. In this case, the min-entropy per PR box is smaller than the min-entropy of a single PR box, and it decreases as the number of copies increases.