Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2020.4
URN: urn:nbn:de:0030-drops-121091
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12109/
Crépeau, Claude ; Massenet, Arnaud Y. ; Salvail, Louis ; Stinchcombe, Lucas Shigeru ; Yang, Nan
Practical Relativistic Zero-Knowledge for NP
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{crpeau_et_al:LIPIcs:2020:12109,
author = {Claude Cr{\'e}peau and Arnaud Y. Massenet and Louis Salvail and Lucas Shigeru Stinchcombe and Nan Yang},
title = {{Practical Relativistic Zero-Knowledge for NP}},
booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)},
pages = {4:1--4:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-151-1},
ISSN = {1868-8969},
year = {2020},
volume = {163},
editor = {Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12109},
URN = {urn:nbn:de:0030-drops-121091},
doi = {10.4230/LIPIcs.ITC.2020.4},
annote = {Keywords: Multi-Prover Interactive Proofs, Relativistic Commitments, 3-COLorability, Quantum Entanglement, Non-Locality}
}
| Keywords: | Multi-Prover Interactive Proofs, Relativistic Commitments, 3-COLorability, Quantum Entanglement, Non-Locality | |
| Seminar: | 1st Conference on Information-Theoretic Cryptography (ITC 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 04.06.2020 |
