Abstract
A zero-knowledge interactive proof is a protocol by which Alice can convince a polynomially-bounded Bob of the truth of some theorem without giving him any hint as to how the proof might proceed. Under cryptographic assumptions, we give a general technique for achieving this goal for every problem in NP. This extends to a presumably larger class, which combines the powers of non-determinism and randomness. Our protocol is powerful enough to allow Alice to convince Bob of theorems for which she does not even have a proof: it is enough for Alice to convince herself probabilistically of a theorem, perhaps thanks to her knowledge of some trap-door information, in order for her to be able to convince Bob as well, without compromising the trap-door in any way.
Supported in part by SSERC grant A4107.
Supported in part by an NSERC postgraduate scholarship;
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adleman, L., “Reducibility, randomness and intractability”, Proceedings of the 9th Annual ACM Symposium on the Theory of Computing, 1977, pp. 151–163.
Babai, L., “Trading group theory for randomness”, Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, 1985, pp. 421–429.
Benaloh (Cohen), J. D., “Cryptographic capsules: a disjunctive primitive for interactive protocols”, these CRYPTO 86 Proceedings, Springer-Verlag, 1987.
Brassard, G. and C. Crépeau, “Non-transitive transfer of confidence: a perfect zero-knowledge interactive protocol for SAT and beyond”, Proceedings of the 27th Annual IEEE Symposium on the Foundations of Computer Science, 1986, pp. 188–195.
Chaum, D., “Demonstrating that a public predicate can be satisfied without revealing any information about how”, these CRYPTO 86 Proceedings, Springer-Verlag, 1987.
Cohen (Benaloh), J. D. and M. J. Fisher, “A robust and verifiable cryptographically secure election scheme”, Proceedings of the 26th Annual IEEE Symposium on the Foundations of Computer Science, 1985, pp. 372–382.
Crépeau, C., “A zero-knowledge Poker protocol that achieves confidentiality of the players’ strategy, or How to achieve an electronic Poker face”, these CRYPTO 86 Proceedings, Springer-Verlag, 1987.
Galil, Z., S. Haber and M. Yung, “A private interactive test of a Boolean predicate and minimum-knowledge public-key cryptosystems”, Proceedings of the 26th Annual IEEE Symposium on the Foundations of Computer Science, 1985, pp. 360–371.
Gill, J. “Computational complexity of probabilistic Turing machines”, SIAM Journal on Computing, vol. 6, no. 4, 1977, pp. 675–695.
Goldreich, O., S. Micali and A. Wigderson, “Proofs that yield nothing but their validity and a methodology of cryptographic protocol design”, Proceedings of the 27th Annual IEEE Symposium on the Foundations of Computer Science, 1986, pp. 174–187.
Goldwasser, S. and J. Kilian, “Almost all primes can be quickly certified”, Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, 1986, pp. 316–329.
Goldwasser, S. and S. Micali, “Probabilistic encryption”, Journal of Computer and System Sciences, vol. 28, no. 2, 1984, pp. 270–299.
Goldwasser, S., S. Micali and C. Rackoff, “The knowledge complexity of interactive proof-systems”, Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, 1985, pp. 291–304.
Peralta, R., “A simple and fast probabilistic algorithm for computing square roots modulo a prime number”, IEEE Transactions on Information Theory, to appear.
Pratt, V., “Every prime has a succinct certificate”, SIAM Journal on Computing, vol. 4, 1975, pp. 214–220.
Rabin, M. O., “Probabilistic algorithms”, in Algorithms and Their Complexity: Recent Results and New Directions, J.F. Traub (editor), Academic Press, New York, New York, 1976, pp. 21–39.
Rivest, R.L., A. Shamir and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystem”, Communications of the ACM, vol. 21, no. 2, 1978, pp. 120–126.
Solovay, R. and V. Strassen, “A fast Monte Carlo test for primality”, SIAM Journal on Computing, vol. 6, 1977, pp. 84–85.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brassard, G., Crepeau, C. (1987). Zero-Knowledge Simulation of Boolean Circuits. In: Odlyzko, A.M. (eds) Advances in Cryptology — CRYPTO’ 86. CRYPTO 1986. Lecture Notes in Computer Science, vol 263. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47721-7_16
Download citation
DOI: https://doi.org/10.1007/3-540-47721-7_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18047-0
Online ISBN: 978-3-540-47721-1
eBook Packages: Springer Book Archive