Soundness in the Public-Key Model

The public-key model for interactive proofs has proved to be quite effective in improving protocol efficiency [CGGM00]. 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; andidentify the round complexity of some of the new notions.