Zero knowledge proofs of identity

ABSTRACT

In this paper we extend the notion of zero knowledge proofs of membership (which reveal one bit of information) to zero knowledge proofs of knowledge (which reveal no information whatsoever). After formally defining this notion, we show its relevance to identification schemes, in which parties prove their identity by demonstrating their knowledge rather than by proving the validity of assertions. We describe a novel scheme which is provably secure if factoring is difficult and whose practical implementations are about two orders of magnitude faster than RSA-based identification schemes. In the last part of the paper we consider the question of sequential versus parallel executions of zero knowledge protocols, define a new notion of “transferable information”, and prove that the parallel version of our identification scheme (which is not known to be zero knowledge) is secure since it reveals no transferable information.

References

1. 1.Brassard, G. a~nd C. Crepeau, "Nontransitive Transfer of Confidence: A Perfect Zero Knowledge Interactive Protocol for SAT and Beyond", Proceedings of FOCS 1986, pp. 187-195.
2. 2.Chaum, D., "Demonstratiiag That a Public Predicate Can Be Satisfied Without Revealing Any Information About How", Proceedings of CRYPTO 1986.
3. 3.Chor, B., S. Goldwasser, S. Micali and B. Awerbuch, "Verifiable Secret Sharing and Achieving Simukanei~y in the Presence of Faults", Proceedings of FOGS 1985, pp. 383-395.
4. 4.Fiat, A. and A. Shamir, "How To Prove Yourself: Practical Solutions to Identificgtion and Signature Problems", Proceedings of CRYPTO 1986.
5. 5.Galil, Z., S. Haber and M. Yung, "A Private interactive Test of a Boolean Predicate and Minimum- Knowledge Public Key Cryptosystems", Proceedings of FOGS 1985, pp. 360-371.
6. 6.Goldreieh, O., S. Micali and A. Wigderson, "Proofs That Yield Nothing But Their Validity and a Methodology of Cryptographic Protocol Design", Proceedings of FOGS 1986, pp. 174-187.
7. 7.Goldwasser, S., S. Micali and C. Rackoff, "Knowledge Complexity of Interactive Proof Systems", Proceedings of STOC 1985, pp. 291-304.
8. 8.Goldwasser, $., S. Micali a~d R. Rivest, "A P~radoxicaJ Solution to the Signature Problem", Proceedings of FOGS 1984, pp. 441-448.
9. 9.Goldwasser, S. and M. Sipser, "Arthur Merlin Games versus Interactive Proof Systems", Proceedings of STOC 1986, pp. 59-68.
10. 10.Halpern, J. and Y. Moses~ "Knowledge and Common Knowledge in a Distributed Environment", Proceedings of PODC 1984, pp. 50-61.
11. 11.Rosenschein, S., "Formal Theories of Knowledge in A I mad Robotics", New Generation Computing 3, 1985, pp. 345-357.

Index Terms

• General and reference

  • Document types

    • Computing standards, RFCs and guidelines

• Mathematics of computing

  • Discrete mathematics

• Social and professional topics

  • Professional topics

    • Computing industry

• Software and its engineering

• Theory of computation

  • Models of computation

    • Probabilistic computation