Soundness in the Public-Key Model

The public-key model for interactive proofs has proved to be quite effective in improving protocol efficiency (see Canetti, Goldreich, Goldwasser, Micali, STOC 2001). We argue, however, that its soundness notion is more subtle and complex than in the classical model, and that it should be better understood to avoid designing erroneous protocols. Specifically, for the public-key model, we

• identify four meaningful notions of soundness;
• prove that, under minimal complexity assumptions, these four notions are distinct;
• identify the exact soundness notions satisfied by prior interactive protocols; and
• identify the round complexity of some of the new notions.

Adobe Acrobat (.pdf) File (the first page, added in 2012, contains a retraction of one of the results)