Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Zero-Knowledge

Original Publication (in the same form): Proceedings of MYCrypt 2016

Date: received 6 Mar 2017, last revised 10 Jun 2017

Contact author: crepeau at cs mcgill ca

Available format(s): PDF | BibTeX Citation

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

Version: 20170610:164741 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]