Random self-reducibility and zero knowledge interactive proofs of possession of information
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 472-482
- https://doi.org/10.1109/sfcs.1987.49
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 proofsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Recognizing primes in random polynomial timePublished by Association for Computing Machinery (ACM) ,1987
- Zero knowledge proofs of identityPublished by Association for Computing Machinery (ACM) ,1987
- Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyondPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol designPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- The knowledge complexity of interactive proof-systemsPublished by Association for Computing Machinery (ACM) ,1985
- Probabilistic Algorithms in Finite FieldsSIAM Journal on Computing, 1980
- On taking roots in finite fieldsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970