Experimental relativistic zero-knowledge proofs.
Journal
Nature
ISSN: 1476-4687
Titre abrégé: Nature
Pays: England
ID NLM: 0410462
Informations de publication
Date de publication:
11 2021
11 2021
Historique:
received:
15
01
2021
accepted:
06
09
2021
entrez:
4
11
2021
pubmed:
5
11
2021
medline:
5
11
2021
Statut:
ppublish
Résumé
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
Identifiants
pubmed: 34732869
doi: 10.1038/s41586-021-03998-y
pii: 10.1038/s41586-021-03998-y
doi:
Types de publication
Journal Article
Research Support, Non-U.S. Gov't
Langues
eng
Sous-ensembles de citation
IM
Pagination
47-50Commentaires et corrections
Type : CommentIn
Informations de copyright
© 2021. The Author(s), under exclusive licence to Springer Nature Limited.
Références
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).
doi: 10.1137/0218012
Rivest, R. L., Shamir, A. & Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978).
doi: 10.1145/359340.359342
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).
doi: 10.1145/116825.116852
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).
doi: 10.1038/nature23461
Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).
doi: 10.1038/s41586-019-1666-5
Kent, A. Unconditionally secure bit commitment. Phys. Rev. Lett. 83, 1447–1450 (1999).
doi: 10.1103/PhysRevLett.83.1447
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).
doi: 10.1016/j.dam.2006.07.015
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).
doi: 10.1103/PhysRevLett.117.140506
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).
doi: 10.1016/j.ffa.2014.06.001
Tassa, T. & Villar, J. L. On proper secrets, (t, k)-bases and linear codes. Des. Codes Cryptogr. 52, 129–154 (2009).
doi: 10.1007/s10623-009-9272-4
Lunghi, T. et al. Practical relativistic bit commitment. Phys. Rev. Lett. 115, 030502 (2015).
doi: 10.1103/PhysRevLett.115.030502
Bell, J. S. On the Einstein–Podolsky–Rosen paradox. Phys. Phys. Fiz. 1, 195–200 (1964).
Kempe, J., Kobayashi, H., Matsumoto, K., Toner, B. & Vidick, T. Entangled games are hard to approximate. SIAM J. Comput. 40, 848–877 (2011).
doi: 10.1137/090751293
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).
doi: 10.1145/2574871
Glaser, A., Barak, B. & Goldston, R. J. A zero-knowledge protocol for nuclear warhead verification. Nature 510, 497–502 (2014).
doi: 10.1038/nature13457
Group of Applied Physics. Google Maps https://goo.gl/maps/qhriiVPu8ktAqfZd9 (2020).