Zero-knowledge with log-space verifiers
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Interactive proof systems are considered in which the best set of possible verifiers is restricted to the class of probabilistic log-space automata. A. Condon (1988) introduced this model and showed that if the protocols are allowed to run for arbitrarily many rounds, exponential-time languages can be proved to a log-space verifier. To better approximate the usual notion of interactive proof systems, a number of researchers have considered a more realistic, further restricted model in which protocols are polynomially bounded, both in the number of rounds of communication and in the number of computational steps allowed to the verifier. A notion of language-recognition zero-knowledge is defined for this model, and it is shown that anything provable in this model can be proved in language-recognition zero-knowledge.Keywords
This publication has 4 references indexed in Scilit:
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication ComplexitySIAM Journal on Computing, 1988
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- The complexity of perfect zero-knowledgePublished by Association for Computing Machinery (ACM) ,1987
- Private coins versus public coins in interactive proof systemsPublished by Association for Computing Machinery (ACM) ,1986