Computationally convincing proofs of knowledge (Q4035674)

[For the entire collection see Zbl 0753.00019.] We give a more general definition of ``computationally convincing proof of knowledge'' capable of taking into account very nasty behaviour from the prover. We also prove that the constant-round arguments of [\textit{G. Brassard}, \textit{C. Crépeau} and \textit{M. Yung}, Theoret. Comput. Sci. 84, No. 1, 23-52 (1991; Zbl 0731.68032)] for NP-complete problems are proofs of knowledge according to our definition, which is much more difficult to prove than for the \(k\)-round protocols of [\textit{G. Brassard}, \textit{D. Chaum} and \textit{C. Crépeau}, J. Comput. Syst. Sci. 37, No. 2, 156-189 (1988; Zbl 0656.68109)]. Finally, we exhibit a protocol that forces us to question the full generality of our definition of ``computationally convincing'': it may be that a more general definition is needed still, and that we do not yet know precisely when we should be convinced that a protocol is convincing.