Access Restriction

Author Dwork, Cynthia ♦ Stockmeyer, Larry
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1992
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Arthur-Merlin games ♦ Complexity theory ♦ Finite state automata ♦ Interactive proof systems ♦ Probabilistic automata ♦ Zero knowledge
Abstract The zero knowledge properties of interactive proof systems (IPSs) 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 $\textit{L}$ such that $\textit{L}$ has an IPS with 2pfa verifiers but $\textit{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 $\textit{L}$ such that $\textit{L}$ has a zero knowledge IPS with respect to this class of verifiers, and $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 39
Issue Number 4
Page Count 30
Starting Page 829
Ending Page 858

Open content in new tab

   Open content in new tab
Source: ACM Digital Library