Arnold L. Rosenberg
Journal of the ACM
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.
Arnold L. Rosenberg
Journal of the ACM
Leonid Karlinsky, Joseph Shtok, et al.
CVPR 2019
Ran Iwamoto, Kyoko Ohara
ICLC 2023
Zhikun Yuen, Paula Branco, et al.
DSAA 2023