Guojing Cong, David A. Bader
Journal of Parallel and Distributed Computing
The zero knowledge properties of interactive proof systems 1992 are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). The following results are proved: (1) There is a language L such that L has an IPS with 2pfa verifiers but L has no zero knowledge IPS with 2pfa verifiers. (2) Consider the class of 2pfa's that are sweeping and that halt in polynomial expected time. There is a language L such that L has a zero knowledge IPS with respect to this class of verifiers, and L cannot be recognized by any verifier in the class on its own. A new definition of zero knowledge is introduced. This definition captures a concept of “zero knowledge” for IPSs that are used for language recognition. © 1992, ACM. All rights reserved.
Guojing Cong, David A. Bader
Journal of Parallel and Distributed Computing
Benjamin N. Grosof
AAAI-SS 1993
Pavel Klavík, A. Cristiano I. Malossi, et al.
Philos. Trans. R. Soc. A
Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM