Cryptology ePrint Archive: Report 2019/1454

Practical Relativistic Zero-Knowledge for NP

Claude Crépeau and Arnaud Massenet and Louis Salvail and Lucas Stinchcombe and Nan Yang

Abstract: In this work we consider the following problem: in a Multi-Prover environment, how close can we get to prove the validity of an NP statement in 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 them to reply two trits each. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very minimal equipment.

Category / Keywords: cryptographic protocols / Quantum Cryptography, Zero-Knowledge Proofs, Multi-prover Ingteractive proofs, Relativistic Zero-Knowledge

Date: received 16 Dec 2019

Contact author: claude crepeau at mcgill ca

Available format(s): PDF | BibTeX Citation

Note: Submitted to ITC 2020.

Version: 20191218:194955 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]