Technische Samenvatting: Experimentele Asymmetrische Relativistische Zero-Knowledge Bewijzen met Onvoorwaardelijke Beveiliging

Probleemstelling

Zero-knowledge bewijzen (ZKP's) zijn cruciaal voor het vestigen van vertrouwen en privacy in digitale economieën, zoals cryptovaluta en smart contracts. Klassieke ZKP-protocollen vertrouwen echter op computationele aannames (bijv. het bestaan van eenrichtingsfuncties), waardoor ze kwetsbaar zijn voor toekomstige quantumaanvallen. Hoewel quantum ZKP's een potentieel alternatief bieden, kampen ze met aanzienlijke implementatieproblemen, waaronder de no-cloning stelling die quantum rewinding bemoeilijkt, en de onmogelijkheid van onvoorwaardelijk beveiligde quantum bit commitment.

Relativistische RZKP's (RZKP's) zijn een oplossing door computationele aannames te vervangen door de principes van de speciale relativiteitstheorie (met name het no-signaling principe). Een recente doorbraak demonstreerde een symmetrische RZKP voor het grafische drie-kleurprobleem. Echter, dit symmetrische protocol lijdt onder prohibitieve inefficiënties wanneer men quantum soundness (beveiliging tegen provers die quantum verstrengeling delen) waarborgt. Om quantum soundness te bereiken, vereist het symmetrische protocol een rondecomplexiteit van $O(|E|^4)$ (waarbij $|E|$ het aantal randen is), wat leidt tot onhaalbare looptijden en enorme randomness-kosten voor grafen van realistische grootte.

Methodologie

De auteurs stellen een asymmetrisch relativistisch GMW ZKP protocol voor en implementeren dit experimenteel, ontworpen om de efficiëntiebeperkingen van eerdere symmetrische benaderingen te overwinnen terwijl onvoorwaardelijke beveiliging behouden blijft tegen quantum-gecorreleerde provers.

Protocolontwerp

Het protocol omvat twee ruimtelijk gescheiden prover-verifier paren ($P_1-V_1$ en $P_2-V_2$) en werkt over $m$ interactieve rondes om te bewijzen dat een graaf $G(V, E)$ drie-kleurbaar is zonder de kleuring te onthullen.

1. Preparatie: Provers $P_1$ en $P_2$ delen een willekeurige kleurpermutatie $\pi$ en een set willekeurige waarden $B = \{b_k\}$.
2. Query-fase: Verifier $V_1$ stuurt willekeurige queries $X = \{x_k\}$ naar $P_1$.
3. Commit-fase: $P_1$ berekent commitments $A = \{a_k\}$ waarbij $a_k = x_k \cdot y_k - b_k$ (waarbij $y_k$ de kleur is) en stuurt deze naar $V_1$.
4. Challenge-fase: Verifier $V_2$ selecteert een willekeurige rand $C = \{i, j\}$ en stuurt deze naar $P_2$.
5. Reveal-fase: $P_2$ onthult de kleuren $Y(C)$ en de bijbehorende waarden $B(C)$ aan $V_2$.
6. Check-fase: Verifiers controleren de relativistische restricties (het waarborgen van geen signalering tussen $P_1$ en $P_2 door de tijdsvertragingen$|t_1 - t_4| < \tau$ en $|t_2 - t_3| < \tau$ te verifiëren, waarbij $\tau = d/c$) en de logische consistentie (kleuren zijn verschillend en komen overeen met de commitments).

Theoretische Analyse

De auteurs pakken de uitdaging van quantum soundness aan. In tegen tegenstelling tot klassieke protocollen waar bit commitment sterk bindend is, garanderen relativistische bit commitments alleen "sum-binding". De auteurs demonstreren dat de kans dat kwaadwillende quantum provers succesvol frauderen op een ongeldige rand wordt begrensd door de quantumwaarde van een niet-lokale CHSH$_{Q(2)}$ game. Door de soundness error van het protocol te relateren aan deze game, leiden zij een strikte bovengrens af voor de quantum soundness error $\delta$.

Experimentele Implementatie

Het team heeft een proof-of-principle experiment uitgevoerd met behulp van:

• Hardware: Field-Programmable Gate Arrays (FPGA's) voor lage latentie verwerking en hoogprecisie GPS-tijdsynchronisatie servers (met atoomklokken) voor tijdsinstellingen.
• Setup: Twee prover-verifier paren gescheiden door 300 meter (wat overeenkomt met een tijdsverschil $\tau = 1000$ ns).
• Graaf: Een drie-kleurbare graaf met $|V| = 588$ vertices en $|E| = 1097$ edges.
• Executie: Het experiment voltooide alle vereiste interactieve rondes in ongeveer 0,22 seconden.

Belangrijkste Bijdragen

1. Efficiënt Asymmetrisch Protocol: De auteurs hebben een asymmetrisch relativistisch GMW ZKP protocol ontworend dat de rondecomplexiteit vermindert van $O(|E|^4)$ (in eerdere quantum-sound symmetrische protocollen) naar $O(|E|)$. Dit wordt bereikt door gebruik te maken van twee-prover relativistische bit commitments binnen het GMW-framework, waardoor bewijs en consistentiechecks simultaan in één enkele ronde kunnen plaatsvinden.
2. Quantum Soundness Bewijs: Zij leverden een rigoureus bewijs van quantum soundness door de cheat-kans van verstrengelde provers te relateren aan de niet-lokale CHSH$_{Q(2)}$ game, waarmee een bovengrens voor de soundness error werd vastgesteld zonder afhankelijk te zijn van computationele aannames.
3. Experimentele Realisatie: Zij hebben het protocol succesvol uitgevoerd over een scheiding van 300 meter, waarmee is aangetoond dat de vereiste runtime en randomness-kosten haalbaar zijn voor real-world deployment.

Resultaten

• Rondecomplexiteit: Het protocol vereist $m = 2k|E|$ rondes om een soundness error van $e^{-k}$ te bereiken. Voor de experimentele parameters ($|E|=1097, k=100$) resulteerde dit in ongeveer $2,2 \times 10^5$ rondes.
• Runtime: Het gehele experiment voltooide in 0,22 seconden. In contrast hiermee zou het vorige quantum-sound symmetrische protocol [23] ongeveer $6,72 \times 10^4$ jaar hebben vereist om hetzelfde beveiligingsniveau te bereiken met dezelfde graaf.
• Randomness Kosten: De totale randomness kosten voor het experiment waren 430,81 MB. Het symmetrische protocol [23] zou ongeveer $5,92 \times 10^9$ GB (5,92 exabytes) hebben vereist voor dezelfde taak.
• Beveiliging: De tijdsverschillen $|t_1 - t_4|$ en $|t_2 - t_3|$ werden consequent gemeten onder de 1000 ns drempel, waardoor aan de relativistische no-signaling restricties werd voldaan, zelfs rekening houdend met GPS-synchronisatiefouten.

Betekenis en Claims

Het artikel beweert dat dit werk de krachtige potentie illustreert van het integreren van de speciale relativiteitstheorie met quantumtheorie om vertrouwensloze cryptografische systemen te creëren die veilig zijn tegen quantumaanvallen zonder te vertrouwen op computationele hardheid aannames.

Belangrijke claims met betrekking tot de betekenis zijn onder meer:

• Praktische Haalbaarheid: De reductie in rondecomplexiteit van $O(|E|^4)$ naar $O(|E|)$ transformeert RZKPs van theoretische constructen naar praktisch inzetbare technologieën voor real-life scenario's met redelijk grote grafen.
• Onvoorwaardelijke Beveiliging: Het protocol biedt quantum soundness en zero-knowledge eigenschappen gebaseerd uitsluitend op het no-signaling principe, wat het robuust maakt tegen toekomstige quantum computing ontwikkelingen.
• Schaalbaarheidspotentieel: Hoewel het asymmetrische karakter een hogere computationele last legt op één prover-verifier paar ($V_1-P_1$), stellen de auteurs dat deze trade-off noodzakelijk is om haalbare rountimes te bereiken. Ze suggereren dat het protocol kan worden geïmplementeerd op alledaagse apparaten zoals smartphones.
• Toekomstige Toepassingen: De auteurs wijzen op potentiële toepassingen in privacygevoelige domeinen zoals blockchains, smart contracts, anonieme e-voting en online veilingen. Ze merken ook op dat er mogelijkheden zijn om dit framework uit te breiden naar Zero-Knowledge Proofs of Knowledge (ZKPoK) voor identiteitsverificatie.

De auteurs blijven bescheiden over de schaalbaarheidsuitdagingen en erkennen dat de praktische deployment in glasvezelnetwerken nog steeds hindernissen kent, zoals het verifiëren van de exacte posities van provers en het beheren van de computationele last, wat zij identificeren als openstaande problemen voor toekomstig onderzoek.