Multi-Prover Interactive Proofs: Unsound Foundations

Claude Crépeau; Nan Yang

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: 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},
      url = {https://eprint.iacr.org/2017/229}
}