Zero-Knowledge With Finite State Verifiers (Extended Abstract)
Cynthia Dwork, Larry Stockmeyer · 1990
We initiate an investigation of interactive proof systems (IPS'S) and zero knowledge interactive proof systems where the verifier is a %way probabilistic finite state automaton (2pfa). Among other results, we show: 1. There is a class of 2pfa verifiers and 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; 2. There is a language L such that L has an IPS with 2pfa verifiers but L has no zero knowledge IPS with 2pfa verifiers.