Random self-reducibility and zero knowledge interactive proofs of possession of information
Authors:
- Martin TompaMTMartin Tompa
- Heather WollHWHeather Woll
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 472-482
Abstract
The notion of a zero knowledge interactive proof that one party "knows" some secret information is explored. It is shown that any "random self-reducible" problem has a zero knowledge interactive proof of this sort. The zero knowledge interactive proofs for graph isomorphism, quadratic residuosity, and "knowledge" of discrete logarithms all follow as special cases. Based on these results, new zero knowledge interactive proofs are exhibited for "knowledge" of the factorization of an integer, nonmembership in cyclic subgroups of Zp*, and determining whether an element generates Zp*. None of these proofs relies on any unproven assumptions.Keywords
This publication has 9 references indexed in Scilit:
- On the cunning power of cheating verifiers: Some observations about zero knowledge proofs1987
- Recognizing primes in random polynomial time1987
- Zero knowledge proofs of identity1987
- Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond1986
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol design1986
- The knowledge complexity of interactive proof-systems1985
- Probabilistic Algorithms in Finite FieldsSIAM Journal on Computing, 1980
- On taking roots in finite fields1977
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970