Zero-knowledge with log-space verifiers
Author:
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 25-35
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-knowledge1987
- Private coins versus public coins in interactive proof systems1986