💻 computer science

Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

This paper presents an efficient, experimentally verified asymmetric relativistic zero-knowledge proof protocol that achieves unconditional security against quantum attacks by leveraging special relativity and quantum nonlocality, thereby overcoming the impractical round complexity of previous symmetric approaches.

Original authors: Chen-Xun Weng, Ming-Yang Li, Nai-Rui Xu, Yanglin Hu, Ian George, Jiawei Wu, Shengjun Wu, Hua-Lei Yin, Zeng-Bing Chen

Published 2026-06-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Chen-Xun Weng, Ming-Yang Li, Nai-Rui Xu, Yanglin Hu, Ian George, Jiawei Wu, Shengjun Wu, Hua-Lei Yin, Zeng-Bing Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Proving You Know a Secret Without Telling It

Imagine you have a secret map to a treasure, and you want to convince a skeptical guard that you actually have the map. You don't want to show him the map (because he might steal it), and you don't want to tell him where the treasure is. You just want to prove, "I know the way."

In the digital world, this is called a Zero-Knowledge Proof (ZKP). It's the magic trick that lets you prove you are who you say you are, or that you have enough money for a transaction, without revealing your password or your bank balance.

The Problem: The Quantum Monster

For decades, these digital magic tricks relied on math puzzles that were hard for humans to solve but easy for computers. However, scientists are building Quantum Computers that are like super-fast monsters. These monsters can solve those old math puzzles almost instantly, breaking the security of our current digital locks.

We need a new kind of lock that doesn't rely on math puzzles at all. We need a lock based on the laws of physics.

The Solution: The "Speed of Light" Lock

This paper introduces a new type of proof called a Relativistic Zero-Knowledge Proof. Instead of relying on hard math, it relies on the Speed of Light.

The Analogy: The Two-Headed Dragon
Imagine you have a dragon with two heads (let's call them Head A and Head B). You want to prove to a judge that the dragon is real, but you can't let the heads talk to each other.

The judge stands far away from Head A.
Another judge stands far away from Head B.
The distance is so great that even a beam of light (the fastest thing in the universe) cannot travel from Head A to Head B in the time it takes to answer a question.

Because Head A and Head B cannot communicate fast enough to coordinate a lie, they are forced to tell the truth. If they try to cheat, the laws of physics (specifically, that nothing travels faster than light) catch them.

What This Team Did

The researchers built a working version of this "Speed of Light" proof. Here is how they improved it:

The Old Way Was Too Slow: Previous attempts at this "two-headed dragon" proof were like trying to solve a giant maze by walking through every single path one by one. If the map (the graph) was big, it would take thousands of years to finish the proof. It was theoretically possible but practically useless.
The New Way is Fast: The team designed a smarter, asymmetric version. Think of it like having one head of the dragon do all the heavy lifting while the other head just keeps watch.
- The Result: They reduced the time needed from "thousands of years" to 0.22 seconds.
- The Cost: They used a bit more "randomness" (like shuffling a deck of cards more times), but the total amount of data used was still small enough to fit on a modern hard drive (about 430 MB).

The Experiment

To prove this works in the real world, they set up an experiment at Nanjing University:

They placed two computers (the "heads") in different buildings 300 meters apart.
They used high-speed lasers and GPS clocks to ensure the computers couldn't talk to each other faster than light.
They asked the computers to prove they knew how to color a complex map with only three colors (a classic math puzzle) without showing the colors.
The Outcome: The computers completed the entire proof in 0.22 seconds.

Why This Matters

The paper claims this is a major step forward because:

It's Quantum-Safe: Even if a quantum computer tries to break the code, it can't cheat because it can't break the laws of physics (the speed of light).
It's Practical: Unlike previous versions that were too slow to ever use, this one is fast enough for real-life use, like securing online banking or voting.
It's Unconditional: It doesn't rely on "we think this math is hard." It relies on "we know light has a speed limit."

Summary

The researchers took a theoretical idea—using the speed of light to stop liars—and built a working machine that does it in a fraction of a second. They solved the problem of it being too slow by making one side of the system do more work, which allowed the whole process to be incredibly fast and secure against future quantum computers.

Technical Summary: Experimental Asymmetric Relativistic Zero-Knowledge Proofs with Unconditional Security

Problem Statement

Zero-knowledge proofs (ZKPs) are critical for establishing trust and privacy in digital economies, such as cryptocurrencies and smart contracts. However, classical ZKP protocols rely on computational assumptions (e.g., the existence of one-way functions), rendering them vulnerable to future quantum attacks. While quantum ZKPs offer a potential alternative, they face significant implementation hurdles, including the no-cloning theorem which complicates quantum rewinding, and the impossibility of unconditionally secure quantum bit commitment.

Relativistic ZKPs (RZKPs) have emerged as a solution by replacing computational assumptions with the principles of special relativity (specifically the no-signaling principle). A recent breakthrough demonstrated a symmetric RZKP for the graph three-coloring problem. However, this symmetric protocol suffers from prohibitive inefficiencies when ensuring quantum soundness (security against provers sharing quantum entanglement). To achieve quantum soundness, the symmetric protocol requires a round complexity of $O(|E|^4)$ (where $|E|$ is the number of edges), leading to unachievable runtimes and massive randomness costs for graphs of realistic size.

Methodology

The authors propose and experimentally implement an asymmetric relativistic GMW ZKP protocol designed to overcome the efficiency limitations of previous symmetric approaches while maintaining unconditional security against quantum-correlated provers.

Protocol Design

The protocol involves two spatially separated prover-verifier pairs ( $P_1-V_1$ and $P_2-V_2$ ) and operates over $m$ interactive rounds to prove that a graph $G(V, E)$ is three-colorable without revealing the coloring.

Preparation: Provers $P_1$ and $P_2$ share a random color permutation $\pi$ and a set of random values $B = \{b_k\}$ .
Query Phase: Verifier $V_1$ sends random queries $X = \{x_k\}$ to $P_1$ .
Commit Phase: $P_1$ computes commitments $A = \{a_k\}$ where $a_k = x_k \cdot y_k - b_k$ (with $y_k$ being the color) and sends them to $V_1$ .
Challenge Phase: Verifier $V_2$ selects a random edge $C = \{i, j\}$ and sends it to $P_2$ .
Reveal Phase: $P_2$ reveals the colors $Y(C)$ and corresponding values $B(C)$ to $V_2$ .
Check Phase: Verifiers check relativistic constraints (ensuring no signaling between $P_1$ and $P_2$ by verifying time delays $|t_1 - t_4| < \tau$ and $|t_2 - t_3| < \tau$ , where $\tau = d/c$ ) and logical consistency (colors are distinct and match commitments).

Theoretical Analysis

The authors address the challenge of quantum soundness. Unlike classical protocols where bit commitment is strongly binding, relativistic bit commitments only guarantee "sum-binding." The authors demonstrate that the probability of malicious quantum provers successfully cheating on an invalid edge is upper-bounded by the quantum value of a nonlocal CHSH $_{Q(2)}$ game. By relating the protocol's soundness error to this game, they derive a rigorous upper bound for the quantum soundness error $\delta$ .

Experimental Implementation

The team implemented a proof-of-principle experiment using:

Hardware: Field-Programmable Gate Arrays (FPGAs) for low-latency processing and high-precision GPS time synchronization servers (with atomic clocks) for timing.
Setup: Two prover-verifier pairs separated by 300 meters (corresponding to a time separation $\tau = 1000$ ns).
Graph: A three-colorable graph with $|V| = 588$ vertices and $|E| = 1097$ edges.
Execution: The experiment completed all required interactive rounds in approximately 0.22 seconds.

Key Contributions

Efficient Asymmetric Protocol: The authors designed an asymmetric relativistic GMW ZKP that reduces the round complexity from $O(|E|^4)$ (in previous quantum-sound symmetric protocols) to $O(|E|)$ . This is achieved by utilizing two-prover relativistic bit commitments within the GMW framework, allowing proof and consistency checks to occur simultaneously in a single round.
Quantum Soundness Proof: They provided a rigorous proof of quantum soundness by relating the cheating probability of entangled provers to the nonlocal CHSH $_{Q(2)}$ game, establishing an upper bound on the soundness error without relying on computational assumptions.
Experimental Realization: They successfully executed the protocol over a 300-meter separation, demonstrating that the required runtime and randomness cost are feasible for real-world deployment.

Results

Round Complexity: The protocol requires $m = 2k|E|$ rounds to achieve a soundness error of $e^{-k}$ . For the experimental parameters ( $|E|=1097, k=100$ ), this resulted in approximately $2.2 \times 10^5$ rounds.
Runtime: The entire experiment completed in 0.22 seconds. In contrast, the previous quantum-sound symmetric protocol [23] would have required approximately $6.72 \times 10^4$ years to achieve the same security level with the same graph.
Randomness Cost: The overall randomness cost for the experiment was 430.81 MB. The symmetric protocol [23] would have required approximately $5.92 \times 10^9$ GB (5.92 exabytes) for the same task.
Security: The time differences $|t_1 - t_4|$ and $|t_2 - t_3|$ were consistently measured below the 1000 ns threshold, satisfying the relativistic no-signaling constraints even when accounting for GPS synchronization errors.

Significance and Claims

The paper claims that this work illustrates the powerful potential of integrating special relativity with quantum theory to create trustless cryptographic systems that are secure against quantum attacks without relying on computational hardness assumptions.

Key claims regarding significance include:

Practical Feasibility: The reduction in round complexity from $O(|E|^4)$ to $O(|E|)$ transforms RZKPs from theoretical constructs into practically deployable technologies for real-life scenarios involving reasonably sized graphs.
Unconditional Security: The protocol offers quantum soundness and zero-knowledge properties based solely on the no-signaling principle, making it robust against future quantum computing advances.
Scalability Potential: While the asymmetric nature places a higher computational load on one prover-verifier pair ( $V_1-P_1$ ), the authors argue that the trade-off is necessary to achieve feasible runtimes. They suggest the protocol could be implemented on everyday devices like smartphones.
Future Applications: The authors highlight potential applications in privacy-sensitive domains such as blockchains, smart contracts, anonymous e-voting, and online auctions. They also note the potential to extend this framework to Zero-Knowledge Proofs of Knowledge (ZKPoK) for identity verification.

The authors remain modest regarding scalability challenges, acknowledging that practical deployment in fiber-optical networks still faces hurdles such as verifying the precise positions of provers and managing computational loads, which they identify as open problems for future research.