experimental relativistic zero knowledge proofs

Help | Advanced Search

Computer Science > Cryptography and Security

Title: experimental relativistic zero-knowledge proofs.

Abstract: Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable, for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank's security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all. In this work, we report the experimental realisation of such a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances ($\geqslant$400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain applications such as cryptocurrencies or smart contracts.

Submission history

Access paper:.

• Other Formats

References & Citations

• INSPIRE HEP
• Google Scholar
• Semantic Scholar

DBLP - CS Bibliography

Bibtex formatted citation.

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

• View all journals
• Explore content
• About the journal
• Publish with us
• Sign up for alerts
• Published: 03 November 2021

Experimental relativistic zero-knowledge proofs

• Pouriya Alikhani 1 ,
• Nicolas Brunner 2 ,
• Claude Crépeau   ORCID: orcid.org/0000-0002-9990-8005 1 ,
• Sébastien Designolle   ORCID: orcid.org/0000-0003-0303-3556 2 ,
• Raphaël Houlmann 2 ,
• Weixu Shi 2 , 3 ,
• Nan Yang 4 &
• Hugo Zbinden   ORCID: orcid.org/0000-0002-9237-1700 2  

Nature volume  599 ,  pages 47–50 ( 2021 ) Cite this article

10k Accesses

10 Citations

162 Altmetric

Metrics details

• Computer science
• Quantum physics

Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable; for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank’s security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all 1 . In this work, we report the experimental realization of such a zero-knowledge protocol involving two separated verifier–prover pairs 2 . Security is enforced via the physical principle of special relativity 3 , and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances (≥400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain applications such as cryptocurrencies or smart contracts 4 .

This is a preview of subscription content, access via your institution

Access options

Access Nature and 54 other Nature Portfolio journals

Get Nature+, our best-value online-access subscription

24,99 € / 30 days

cancel any time

Subscribe to this journal

Receive 51 print issues and online access

185,98 € per year

only 3,65 € per issue

Buy this article

• Purchase on SpringerLink
• Instant access to full article PDF

Prices may be subject to local taxes which are calculated during checkout

Similar content being viewed by others

Quantum-resistance in blockchain networks

Statistical detection of selfish mining in proof-of-work blockchain systems

Experimental quantum key distribution certified by Bell's theorem

Data availability.

All data supporting the findings of this article are available from the corresponding authors upon request.

Code availability

All code supporting the findings of this article are available from the corresponding authors upon request.

Goldwasser, S., Micali, S. & Rackoff, C. The knowledge complexity of interactive proof systems. In Proc. Seventeenth Annual ACM Symposium on Theory of Computing 291–304 (ACM, 1985).

Ben-Or, M., Goldwasser, S., Kilian, J. & Wigder-son, A. Multi-prover interactive proofs: how to remove intractability assumptions. In Proc. Twentieth Annual ACM Symposium on Theory of Computing 113–131 (ACM, 1988).

Kilian, J. Strong separation models of multi prover interactive proofs. In DIMACS Workshop on Cryptography (DIMACS, 1990).

Ben-Sasson, E., Bentov, I., Horesh, Y. & Riabzev, M. Scalable, transparent, and post-quantum secure computational integrity. Preprint at https://eprint.iacr.org/2018/046.pdf (2018).

Goldwasser, S., Micali, S. & Rackoff, C. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18 , 186–208 (1989).

Article   MathSciNet   Google Scholar  

Rivest, R. L., Shamir, A. & Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21 , 120–126 (1978).

Garey, M. R. & Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., 1979).

Goldreich, O., Micali, S. & Wigderson, A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38 , 690–728 (1991).

Fortnow, L. The complexity of perfect zero-knowledge. In Proc. Nineteenth Annual ACM Symposium on Theory of Computing 204–209 (ACM, 1987).

Ben Sasson, E. et al. Zerocash: decentralized anonymous payments from Bitcoin. In Proc. IEEE Symp. Security and Privacy 459–474 (IEEE, 2014).

Bernstein, D. J. & Lange, T. Post-quantum cryptography. Nature 549 , 188–194 (2017).

Article   ADS   CAS   Google Scholar  

Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574 , 505–510 (2019).

Kent, A. Unconditionally secure bit commitment. Phys. Rev. Lett. 83 , 1447–1450 (1999).

Article   ADS   MathSciNet   CAS   Google Scholar  

Crépeau, C., Massenet, A., Salvail, L., Stinchcombe, L. & Yang, N. Practical relativistic zero-knowledge for NP. In Proc. 1st Conf. Information-Theoretic Cryptography 4 , 1–18 (LIPiCS, 2020).

Mizuno, K. & Nishihara, S. Constructive generation of very hard 3-colorability instances. Discret. Appl. Math . 156 , 218–229 (2008).

Katz, J. & Lindell, Y. Introduction to Modern Cryptography 3rd edn (CRC, 2020).

Verbanis, E. et al. 24-hour relativistic bit commitment. Phys. Rev. Lett. 117 , 140506 (2016).

Article   ADS   Google Scholar  

Li, N., Li, C., Helleseth, T., Ding, C. & Tang, X. Optimal ternary cyclic codes with minimum distance four and five. Finite Fields their Appl . 30 , 100–120 (2014).

Tassa, T. & Villar, J. L. On proper secrets, ( t , k )-bases and linear codes. Des. Codes Cryptogr. 52 , 129–154 (2009).

Lunghi, T. et al. Practical relativistic bit commitment. Phys. Rev. Lett. 115 , 030502 (2015).

Bell, J. S. On the Einstein–Podolsky–Rosen paradox. Phys. Phys. Fiz . 1 , 195–200 (1964).

MathSciNet   Google Scholar  

Kempe, J., Kobayashi, H., Matsumoto, K., Toner, B. & Vidick, T. Entangled games are hard to approximate. SIAM J. Comput. 40 , 848–877 (2011).

Chailloux, A. & Leverrier, A. Relativistic (or 2-prover 1-round) zero-knowledge protocol for NP secure against quantum adversaries. In Advances in Cryptology – EUROCRYPT 2017 (eds. Coron, J. S. & Nielsen, J.) 369–396 (Springer, 2017).

Ji, Z. Binary constraint system games and locally commutative reductions. Preprint at https://arxiv.org/abs/1310.3794 (2013).

Groth, J. Non-interactive zero-knowledge arguments for voting. In Applied Cryptography and Network Security (eds. Ioannidis, J., Keromytis, A. & Yung, M.) 467–482 (Springer, 2005).

Micali, S. & Rabin, M. O. Cryptography miracles, secure auctions, matching problem verification. Commun. ACM 57 , 85–93 (2014).

Article   Google Scholar  

Glaser, A., Barak, B. & Goldston, R. J. A zero-knowledge protocol for nuclear warhead verification. Nature 510 , 497–502 (2014).

Group of Applied Physics. Google Maps https://goo.gl/maps/qhriiVPu8ktAqfZd9 (2020).

Download references

Acknowledgements

Financial supports by the Swiss National Science Foundation (starting grant DIAQ, NCCR-QSIT) and the European project OpenQKD are gratefully acknowledged by N.B., S.D., R.H., W.X. and H.Z. P.A., C.C. and N.Y. are grateful to Québec’s FRQNT and Canada’s NSERC for making this work financially possible.

Author information

Authors and affiliations.

School of Computer Science, McGill University, Montréal, Québec, Canada

Pouriya Alikhani & Claude Crépeau

Department of Applied Physics, University of Geneva, Genève, Switzerland

Nicolas Brunner, Sébastien Designolle, Raphaël Houlmann, Weixu Shi & Hugo Zbinden

Department of Electronic Science, National University of Defense Technology, Changsha, China

Department of Computer Science and Software Engineering, Concordia University, Montréal, Québec, Canada

You can also search for this author in PubMed   Google Scholar

Contributions

P.A. and C.C. generated the graph used. N.B. and H.Z. supervised the research. C.C. and N.Y. came up with the protocol and C.C. was the theoretical leader. S.D. ensured the link between theory and experiment. R.H. was responsible for the experimental implementation, with support by S.D. and H.Z. W.X. contributed at early stage of the project. S.D. and C.C. wrote the initial draft, with the other authors providing editorial comments.

Corresponding authors

Correspondence to Claude Crépeau or Sébastien Designolle .

Ethics declarations

Competing interests.

The authors declare no competing interests.

Additional information

Peer review information Nature thanks Thomas Vidick and the other, anonymous, reviewer(s) for their contribution to the peer review of this work. Peer reviewer reports are available.

Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Extended data figures and tables

Extended data fig. 1 illustration of a round of the protocol..

The colours are consistent with those of Fig. 1a and depict a typical round where the verifiers ask the same edge to the provers, here \(\{1,2\}\) , but where \(b\ne b\text{'}\) so that they check in the end that \({a}_{0}+a{\text{'}}_{0}\) ≢ \({a}_{1}+a{\text{'}}_{1}({\rm{m}}{\rm{o}}{\rm{d}}\,3)\) . In this example we have \({{\ell }}_{1}^{0}=2,{{\ell }}_{1}^{1}=1,{{\ell }}_{2}^{0}=0,{{\ell }}_{2}^{1}=1\) ; note that, despite the adjacency of the vertices 1 and 2, the equality \({{\ell }}_{1}^{1}={{\ell }}_{2}^{1}\) is legal as the labellings \({{\ell }}_{k}^{b}\) do not need to be colourings.

Extended Data Fig. 2 Illustration of the hardware used in our two implementations.

a , b , The GPS version ( a ) and the triggered version ( b ). The essential difference is the method used for synchronizing the verifiers’ questions. In a the connection is wireless as it uses communication with satellites at the expense of a higher imprecision thus further verifier–prover pairs. In b the connection is physical and oriented from the first to the second verifier; the former sends a trigger through the fibre and delays their action by the time needed for this signal to reach the latter. With a better accuracy this second method allows for shorter distances between the verifier–prover pairs, here 60 m but arguably improvable.

Supplementary information

.peer review file, rights and permissions.

Reprints and permissions

About this article

Cite this article.

Alikhani, P., Brunner, N., Crépeau, C. et al. Experimental relativistic zero-knowledge proofs. Nature 599 , 47–50 (2021). https://doi.org/10.1038/s41586-021-03998-y

Download citation

Received : 15 January 2021

Accepted : 06 September 2021

Published : 03 November 2021

Issue Date : 04 November 2021

DOI : https://doi.org/10.1038/s41586-021-03998-y

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

This article is cited by

Practical quantum tokens without quantum memories and experimental tests.

• Adrian Kent
• David Lowndes
• John Rarity

npj Quantum Information (2022)

Quick links

• Explore articles by subject
• Guide to authors
• Editorial policies

Sign up for the Nature Briefing: AI and Robotics newsletter — what matters in AI and robotics research, free to your inbox weekly.

Experimental relativistic zero-knowledge proofs

Affiliations.

• 1 School of Computer Science, McGill University, Montréal, Québec, Canada.
• 2 Department of Applied Physics, University of Geneva, Genève, Switzerland.
• 3 School of Computer Science, McGill University, Montréal, Québec, Canada. [email protected].
• 4 Department of Applied Physics, University of Geneva, Genève, Switzerland. [email protected].
• 5 Department of Electronic Science, National University of Defense Technology, Changsha, China.
• 6 Department of Computer Science and Software Engineering, Concordia University, Montréal, Québec, Canada.
• PMID: 34732869
• DOI: 10.1038/s41586-021-03998-y

Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable; for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank's security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all 1 . In this work, we report the experimental realization of such a zero-knowledge protocol involving two separated verifier-prover pairs 2 . Security is enforced via the physical principle of special relativity 3 , and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances (≥400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain applications such as cryptocurrencies or smart contracts 4 .

© 2021. The Author(s), under exclusive licence to Springer Nature Limited.

Publication types

• Research Support, Non-U.S. Gov't

Experimental relativistic zero-knowledge proofs

• Nature 599 (2021) 7883 , 47-50
• Published: Nov 3, 2021
• 2012.10452 [cs.CR]
• 10.1038/s41586-021-03998-y
• ADS Abstract Service

Citations per year

• 8 pages, 3 figures
• special relativity
• information theory
• information management
• computer: communications
• S. Goldwasser ,
• S. Micali ,
• M. Ben-Or ,
• J. Kilian ,
• A. Wigder-son
• Computing 113 (1988) 131
• E. Ben-Sasson ,
• I. Bentov ,
• Y. Horesh ,
• 10.1137/0218012
• 10.1145/359340.359342
• M.R. Garey ,
• D.S. Johnson
• 10.1145/116825.116852
• Computing 204 (1987) 209
• E. Ben Sasson

Post-quantum cryptography

• Illinois U., Chicago
• Eindhoven, Tech. U.
• Nature 549 (2017) 7671 , 188-194
• 10.1038/nature23461

Quantum supremacy using a programmable superconducting processor

• Google Inc.
• Google Inc. and
• Massachusetts U., Amherst
• Nature 574 (2019) 7779 , 505-510
• 10.1038/s41586-019-1666-5

Unconditionally secure bit commitment

• Cambridge U., DAMTP
• Phys.Rev.Lett. 83 (1999) 1447-1450
• quant-ph/9810068
• 10.1103/PhysRevLett.83.1447
• C. Crépeau ,
• A. Massenet ,
• L. Salvail ,
• L. Stinchcombe ,
• 10.1016/j.dam.2006.07.015
• 10.1103/PhysRevLett.117.140506
• 10.1016/j.ffa.2014.06.001
• 10.1007/s10623-009-9272-4
• 10.1103/PhysRevLett.115.030502

On the Einstein-Podolsky-Rosen paradox

• Wisconsin U., Madison
• Physics Physique Fizika 1 (1964) 195-200
• 10.1103/PhysicsPhysiqueFizika.1.195

Entangled Games Are Hard to Approximate

• Kempe Julia ,
• Kobayashi Hirotada ,
• Matsumoto Keiji ,
• Toner Ben ,
• Vidick Thomas
• SIAM J.Comput. 40 (2011) 3 , 848-877
• 10.1137/090751293
• A. Chailloux ,
• A. Leverrier