Paper 2005/286

Concurrent Zero Knowledge without Complexity Assumptions

Daniele Micciancio, Shien Jin Ong, Amit Sahai, and Salil Vadhan

Abstract

We provide unconditional constructions of concurrent statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (coNP forms of the) Shortest Vector Problem and Closest Vector Problem in lattices. For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an NP witness) and have \tilde{O}(log n) rounds, which is known to be essentially optimal for black-box simulation. To our best of knowledge, these are the first constructions of concurrent zero-knowledge protocols in the asynchronous model (without timing assumptions) that do not require complexity assumptions (such as the existence of one-way functions).

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero knowledge
Contact author(s)
shienjin @ eecs harvard edu
History
2005-08-26: revised
2005-08-25: received
See all versions
Short URL
https://ia.cr/2005/286
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/286,
      author = {Daniele Micciancio and Shien Jin Ong and Amit Sahai and Salil Vadhan},
      title = {Concurrent Zero Knowledge without Complexity Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2005/286},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/286}},
      url = {https://eprint.iacr.org/2005/286}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.