Finite State Verifiers II: Zero Knowledge

Abstract

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.