License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12109/
Go to the corresponding LIPIcs Volume Portal

Crépeau, Claude ; Massenet, Arnaud Y. ; Salvail, Louis ; Stinchcombe, Lucas Shigeru ; Yang, Nan

Practical Relativistic Zero-Knowledge for NP

pdf-format:
LIPIcs-ITC-2020-4.pdf (5 MB)

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
Collection: 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Issue Date: 2020
Date of publication: 04.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI