Paper 2019/1454
Practical Relativistic Zero-Knowledge for NP
Claude Crépeau, Arnaud Massenet, Louis Salvail, 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.
Note: Submitted to ITC 2020.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Quantum CryptographyZero-Knowledge ProofsMulti-prover Ingteractive proofsRelativistic Zero-Knowledge
- Contact author(s)
- claude crepeau @ mcgill ca
- History
- 2019-12-18: received
- Short URL
- https://ia.cr/2019/1454
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1454,
author = {Claude Crépeau and Arnaud Massenet and Louis Salvail and Lucas Stinchcombe and Nan Yang},
title = {Practical Relativistic Zero-Knowledge for {NP}},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/1454},
year = {2019},
url = {https://eprint.iacr.org/2019/1454}
}
