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:2012.10452 · Nature

Experimental relativistic zero-knowledge proofs

Pouriya Alikhani, Nicolas Brunner, Claude Crépeau, Sébastien Designolle, Raphaël Houlmann, Weixu Shi, Nan Yang, Hugo Zbinden

Published Nov 3, 2021• 20 citations
arXivHTMLPDF
DOI
10.1038/s41586-021-03998-y

Related papers

Relativistic commitment and zero-knowledge proofs

André Chailloux

•Mar 1, 2018•0 citations

Quantum Zero-Knowledge Proof

Tao Shang

Springer eBooks•Oct 15, 2024•0 citations

General Properties of Quantum Zero-Knowledge Proofs

Hirotada Kobayashi

arXiv:0705.1129•Springer eBooks•Feb 25, 2008•35 citations

Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

Chen-Xun Weng, Mingyang Li, Nai-Rui Xu +6 more

Zero-knowledge proofs (ZKPs) are widely applied in digital economies, such as cryptocurrencies and smart contracts, for establishing trust and privacy between untrusted parties. Classical ZKPs rely on computational assumptions and are vulnerable to quantum attacks. While a recent advance suggests quantum-sound symmetric relativistic ZKPs for the graph three-coloring problem without computational assumptions, the high round complexity, which leads to unachievable runtime and overall randomness cost, renders them impractical for real-life deployment. To overcome this, we develop an efficient asymmetric relativistic ZKP protocol using relativistic bit commitments, and prove its quantum soundness by relating it to the nonlocal Clauser-Horne-Shimony-Holt (CHSH) game. Our protocol achieves a linear relationship between the round complexity and the number of edges, and thus significantly improves practical feasibility. In addition, we implement a proof-of-principle experiment which completes all interactive rounds in about 0.22 seconds and requires an overall randomness cost of 430.81 MB. Our work illustrates the powerful potential of integrating special relativity with quantum theory in trustless cryptography, paving the way for robust applications against quantum attacks in distrustful Internet environments. Zero-knowledge proofs can protect privacy online, but almost all current methods are vulnerable to quantum attacks. Here, the authors report an efficient relativistic protocol and experiment that resists quantum attacks and greatly reduces runtime, randomness cost and communication rounds.

arXiv:2501.18176•Nature Communications•May 26, 2026•0 citations

Quantum-Safe Identity Verification using Relativistic Zero-Knowledge Proof Systems

Yao Ma, Wen Yu Kon, Chu, Jefferson +3 more

Identity verification is the process of confirming an individual's claimed identity, which is essential in sectors like finance, healthcare, and online services to ensure security and prevent fraud. However, current password/PIN-based identity solutions are susceptible to phishing or skimming attacks, where malicious intermediaries attempt to steal credentials using fake identification portals. Alikhani et al. [Nature, 2021] began exploring identity verification through graph coloring-based relativistic zero-knowledge proofs (RZKPs), a key cryptographic primitive that enables a prover to demonstrate knowledge of secret credentials to a verifier without disclosing any information about the secret. Our work advances this field and addresses unresolved issues: From an engineering perspective, we relax further the relativistic constraints from 60m to 30m, and significantly enhance the stability and scalability of the experimental demonstration of the 2-prover graph coloring-based RZKP protocol for near-term use cases. At the same time, for long-term security against entangled malicious provers, we propose a modified protocol with comparable computation and communication costs, we establish an upper bound on the soundness parameter for this modified protocol. On the other hand, we extend the two-prover, two-verifier setup to a three-prover configuration, demonstrating the security of such relativistic protocols against entangled malicious provers.

arXiv:2507.14324•Jul 18, 2025•0 citations

On the Relativistic Zero Knowledge Quantum Proofs of Knowledge

Kaiyan Shi, Kaushik Chakraborty, Wen Yu Kon +3 more

We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(η) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).

arXiv:2409.03635•Sep 5, 2024•0 citations
Zero-knowledge proofs (ZKPs) are widely applied in digital economies, such as cryptocurrencies and smart contracts, for establishing trust and privacy between untrusted parties. Classical ZKPs rely on computational assumptions and are vulnerable to quantum attacks. While a recent advance suggests quantum-sound symmetric relativistic ZKPs for the graph three-coloring problem without computational assumptions, the high round complexity, which leads to unachievable runtime and overall randomness cost, renders them impractical for real-life deployment. To overcome this, we develop an efficient asymmetric relativistic ZKP protocol using relativistic bit commitments, and prove its quantum soundness by relating it to the nonlocal Clauser-Horne-Shimony-Holt (CHSH) game. Our protocol achieves a linear relationship between the round complexity and the number of edges, and thus significantly improves practical feasibility. In addition, we implement a proof-of-principle experiment which completes all interactive rounds in about 0.22 seconds and requires an overall randomness cost of 430.81 MB. Our work illustrates the powerful potential of integrating special relativity with quantum theory in trustless cryptography, paving the way for robust applications against quantum attacks in distrustful Internet environments. Zero-knowledge proofs can protect privacy online, but almost all current methods are vulnerable to quantum attacks. Here, the authors report an efficient relativistic protocol and experiment that resists quantum attacks and greatly reduces runtime, randomness cost and communication rounds.
Identity verification is the process of confirming an individual's claimed identity, which is essential in sectors like finance, healthcare, and online services to ensure security and prevent fraud. However, current password/PIN-based identity solutions are susceptible to phishing or skimming attacks, where malicious intermediaries attempt to steal credentials using fake identification portals. Alikhani et al. [Nature, 2021] began exploring identity verification through graph coloring-based relativistic zero-knowledge proofs (RZKPs), a key cryptographic primitive that enables a prover to demonstrate knowledge of secret credentials to a verifier without disclosing any information about the secret. Our work advances this field and addresses unresolved issues: From an engineering perspective, we relax further the relativistic constraints from 60m to 30m, and significantly enhance the stability and scalability of the experimental demonstration of the 2-prover graph coloring-based RZKP protocol for near-term use cases. At the same time, for long-term security against entangled malicious provers, we propose a modified protocol with comparable computation and communication costs, we establish an upper bound on the soundness parameter for this modified protocol. On the other hand, we extend the two-prover, two-verifier setup to a three-prover configuration, demonstrating the security of such relativistic protocols against entangled malicious provers.
We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(η) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).