Experimental asymmetric relativistic zero-knowledge proofs with unconditional security
This work provides a practical, unconditionally secure ZKP protocol resistant to quantum attacks, addressing the high round complexity bottleneck of previous relativistic ZKPs.
The authors developed an efficient asymmetric relativistic zero-knowledge proof protocol that achieves quantum soundness without computational assumptions, reducing round complexity to linear in the number of edges. In a proof-of-principle experiment, the protocol completed all rounds in about 0.22 seconds with a randomness cost of 430.81 MB.
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.