Paper 2017/229

Multi-Prover Interactive Proofs: Unsound Foundations

Claude Crépeau and Nan Yang

Abstract

Several Multi-Prover Interactive Proofs (MIPs) found in the literature contain proofs of soundness that are lacking. This was first observed by Crépeau, Salvail, Simard and Tapp who defined a notion of {Prover isolation} to partly address the issue. Furthermore, some existing Zero-Knowledge MIPs suffer from a catastrophic flaw: they outright allow the Provers to communicate via the Verifier. Consequently, their soundness claims are now seriously in doubt, if not plain wrong. This paper outlines the lack of isolation and numerous other issues found in the (ZK)MIP literature. A follow-up paper will resolve most of these issues in detail.

Note: Revised Section 3.3 after Justin Holmgren pointed out an awkward statement about soundness.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Proceedings of MYCrypt 2016
Keywords
Zero-Knowledge
Contact author(s)
crepeau @ cs mcgill ca
History
2017-06-10: revised
2017-03-08: received
See all versions
Short URL
https://ia.cr/2017/229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/229,
      author = {Claude Crépeau and Nan Yang},
      title = {Multi-Prover Interactive Proofs: Unsound Foundations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/229},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/229}},
      url = {https://eprint.iacr.org/2017/229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.