2026-07-22T11:58:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12109 2024-03-06T10:49:32Z ddc:004 open_access

Practical Relativistic Zero-Knowledge for NP Crépeau, Claude Massenet, Arnaud Y. Salvail, Louis Stinchcombe, Lucas Shigeru Yang, Nan Multi-Prover Interactive Proofs Relativistic Commitments 3-COLorability Quantum Entanglement Non-Locality In a Multi-Prover environment, how little spatial separation is sufficient to assert the validity of an NP statement in Perfect Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers and only require exchanging one edge and two bits with two trits per prover. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very basic communication gear. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Claude Crépeau and Arnaud Y. Massenet and Louis Salvail and Lucas Shigeru Stinchcombe and Nan Yang 2020 Is Part Of LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2020.4 urn:nbn:de:0030-drops-121091 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.4 eng https://creativecommons.org/licenses/by/3.0/legalcode