Simple and Tight Device-Independent Security Proofs
Open accessThe DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654
On the Einstein Podolsky Rosen paradox
Bell, J. S. (1964) · Physics Physique Fizika · doi:10.1103/physicsphysiquefizika.1.195 · Cited by 12,252 · cited 1×
“nt protocols are made possible due to the phenomena of quantum non-locality and the so-called Bell inequalities (see [Sca13, BCP+14] for excellent reviews on the topic). In general, a Bell inequality [Bel64] can be thought of as a game2 played by the honest parties using the device they share. The game has a special “…”
Quantum cryptography based on Bell’s theorem
Ekert, A. K. (1991) · Physical Review Letters · doi:10.1103/physrevlett.67.661 · Cited by 10,777
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.05.025 · Cited by 8,299
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2020) · arXiv · doi:10.48550/arxiv.2003.06557 · Cited by 8,299
Proposed Experiment to Test Local Hidden-Variable Theories
Clauser, J. F., Horne, M. A., Shimony, A., & Holt, R. A. (1969) · Physical Review Letters · doi:10.1103/physrevlett.23.880 · Cited by 7,573 · cited 2×
“rity of a DIQKD protocol was proven in the asymptotic limit, i.e., when the device is used n → ∞ times, and under the i.i.d. assumption described above. Their protocol is based on the CHSH inequality [CHSH69]. To the best of our knowledge, they provide the best known rates under these assumptions. The simpler tasks of…”
Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres
Hensen, B., Bernien, H., Dréau, A. E., Reiserer, A., Kalb, N., Blok, M. S., Ruitenberg, J., Vermeulen, R. F. L., Schouten, R. N., Abellán, C., et al. (2015) · Nature · doi:10.1038/nature15759 · Cited by 2,852 · cited 2×
“As loophole-free Bell tests (a necessity for DI cryptography) are finally being realized [HBD + 15, SMSC + 15, GVW + 15], it becomes increasingly relevant to achieve the best possible dependence of the rate curves on the number of rounds n , even for very small values of n .”
Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V., & Wehner, S. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.419 · Cited by 2,688
Significant-Loophole-Free Test of Bell’s Theorem with Entangled Photons
Giustina, M., Versteegh, M. A. M., Wengerowsky, S., Handsteiner, J., Hochrainer, A., Phelan, K., Steinlechner, F., Kofler, J., Larsson, J.-Å., Abellán, C., et al. (2015) · Physical Review Letters · doi:10.1103/physrevlett.115.250401 · Cited by 1,529
Random numbers certified by Bell’s theorem
Pironio, S., Acín, A., Massar, S., de la Giroday, A. B., Matsukevich, D. N., Maunz, P., Olmschenk, S., Hayes, D., Luo, L., Manning, T. A., et al. (2010) · Nature · doi:10.1038/nature09008 · Cited by 1,420
Strong Loophole-Free Test of Local Realism
Shalm, L. K., Meyer-Scott, E., Christensen, B. G., Bierhorst, P., Wayne, M. A., Stevens, M. J., Gerrits, T., Glancy, S., Hamel, D. R., Allman, M. S., et al. (2015) · Physical Review Letters · doi:10.1103/physrevlett.115.250402 · Cited by 1,402
From Bell’s Theorem to Secure Quantum Key Distribution
Acín, A., Gisin, N., & Masanes, L. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.120405 · Cited by 709
Structure of States Which Satisfy Strong Subadditivity of Quantum Entropy with Equality
Hayden, P., Jozsa, R., Petz, D., & Winter, A. (2004) · Communications in Mathematical Physics · doi:10.1007/s00220-004-1049-z · Cited by 429
Free randomness can be amplified
Colbeck, R., & Renner, R. (2012) · Nature Physics · doi:10.1038/nphys2300 · Cited by 379 · cited 1×
“A limited list includes QKD [4,10,11], randomness expansion [8,12–15] and amplification [16,17], verified quantum computation [18,19], bit commitment [20] and weak string erasure [21].”
Self-citationA Fully Quantum Asymptotic Equipartition Property
Tomamichel, M., Colbeck, R., & Renner, R. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2032797 · Cited by 356
Self-citationUniversally Composable Privacy Amplification Against Quantum Adversaries
Renner, R., & König, R. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_22 · Cited by 337 · cited 1×
“Any other quantum-proof strong extractor, e.g., Trevisan’s extractor [DPVR12], can be used for this task and the analysis can be easily adapted.”
Self-citationRandomness versus Nonlocality and Entanglement
Acín, A., Massar, S., & Pironio, S. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.100402 · Cited by 324
Full randomness from arbitrarily deterministic events
Gallego, R., Masanes, L., De La Torre, G., Dhara, C., Aolita, L., & Acín, A. (2013) · Nature Communications · doi:10.1038/ncomms3654 · Cited by 186
Security of practical private randomness generation
Pironio, S., & Massar, S. (2013) · Physical Review A · doi:10.1103/physreva.87.012336 · Cited by 169 · cited 1×
“of the security parameters. The rate is to be compared to the optimal rate that was shown achievable for randomness expansion in the case of classical adversaries only in [PAM+10] (Figure 2; see also [PM13]). In the range of small constant γ > 0 we obtain essentially the same rate, but our result holds against quan…”
Trevisan's Extractor in the Presence of Quantum Side Information
De, A., Portmann, C., Vidick, T., & Renner, R. (2012) · SIAM Journal on Computing · doi:10.1137/100813683 · Cited by 161
Self-citationSecurity and composability of randomness expansion from Bell inequalities
Fehr, S., Gelles, R., & Schaffner, C. (2013) · Physical Review A · doi:10.1103/physreva.87.012335 · Cited by 104 · cited 1×
“setting, few works give explicit rates; to the best of our knowledge, the only quantitative results available are from [54] (see also [59, 32] for an analysis in the non-i.”
Certifiable quantum dice: or, true random number generation secure against quantum adversaries
Vazirani, U., & Vidick, T. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213984 · Cited by 80 · cited 4×
“We give explicit formulas for computing the constants c 1 and c 2 that appear in (1), as a function of the parameters of the protocol (such as the fraction of rounds used for testing and the threshold value based on which the decision to accept or reject is made).”
InfluentialSelf-citationUniversal security for randomness expansion from the spot-checking protocol
Miller, C. A., & Shi, Y. (2014) · arXiv · doi:10.48550/arxiv.1411.6608 · Cited by 80
Cited by
Advances in quantum cryptography
Pirandola, S., Andersen, U. L., Banchi, L., Berta, M., Bunandar, D., Colbeck, R., Englund, D., Gehring, T., Lupo, C., Ottaviani, C., et al. (2020) · Advances in Optics and Photonics · doi:10.1364/aop.361502 · Cited by 2,033
Scarani, V. (2019) · doi:10.1093/oso/9780198788416.001.0001 · Cited by 605
Security in quantum cryptography
Portmann, C., & Renner, R. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.025008 · Cited by 390
Self-citationSelf-testing of quantum systems: a review
Šupić, I., & Bowles, J. (2020) · Quantum · doi:10.22331/q-2020-09-30-337 · Cited by 365
A device-independent quantum key distribution system for distant users
Zhang, W., van Leent, T., Redeker, K., Garthoff, R., Schwonnek, R., Fertig, F., Eppelt, S., Rosenfeld, W., Scarani, V., Lim, C. C.-W., et al. (2022) · Nature · doi:10.1038/s41586-022-04891-y · Cited by 303
Metadata
- Authors
- Arnon-Friedman, R., Renner, R., & Vidick, T.
- Venue
- SIAM Journal on Computing
- Published
- 2019-01
- Volume
- 48
- Issue
- 1
- Pages
- 181-225
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2494499351
- Cited by
- 152
- References
- 23
- FWCI
- 9.67
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.