Soundness in the Public-Key Model
by Silvio Micali
and Leonid Reyzin
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.
This work appears in Advances in Cryptology -- Crypto 2001, Joe Kilian,
editor, Lecture Notes in Computer Science 2139, Springer-Verlag, 2001.