Abstract
Brassard and Crépeau [BCr] introduced a simple technique for producing zero-knowledge proof systems based on blobs. As is to be expected, their implementation rests on an unproven cryptographic assumption, specifically, that it is easy to generate numbers that are difficult to factor. In this paper we present an implementation of blobs based on a different cryptographic assumption, specifically, that it is easy to generate primes p over which it is difficult to compute discrete logarithms. If, in addition, we can produce a generator for Z * p , this implementation then has the advantage that it leads to proof systems which are perfect zeroknowledge, rather than only almost perfect zero-knowledge.
The relationship between factoring and finding discrete logarithms is not well understood, although Bach [Bac1] is an important contribution. Given our current state of number theoretic knowlege, there is no reason to prefer the cryptographic assumption required by one of these implementations over that required by the other. In any event, we introduce the notion of a product blob, whose favorable properties depend only on at least one of these assumptions holding.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. Adleman and M. Huang. Recognizing primes in random polynomial time. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, pages 462–469, 1987.
L. Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, pages 421–429, 1985.
E. Bach. Discrete logarithms and factoring. Technical Report 84/186, Computer Science Division, University of California, June 1984.
E.Bach. How to generate factored random numbers. SIAM Journal on Computing, 17(2): 179–193, April 1988.
M. Ben-Or, S. Goldwasser, and A. Widgerson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 1–10, 1988.
M.Blum and S.Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13:850–864, 1984.
R.Boppana, J.Håstad, and S.Zachos. Does CoNP have short interactive proofs? Information Processing Letters, 25:127–132, 1987.
J.Boyar. Inferring sequences produced by pseudo-random number generators. Journal of the ACM, 36:129–141, 1989.
G. Brassard and D. Chaum. Personal communication, 1987.
G.Brassard, D.Chaum, and C.Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer System Science, 37:156–189, 1988.
G. Brassard and C. Crépeau. Nontransitive transfer of confidence: a perfect zero-knowledge interactive protocol for Sat and beyond. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science, pages 188–195, 1986.
E.Brickell and A.Odlyzko. Cryptanalysis: A survey of recent results. Proceedings of the IEEE, 76:578–593, 1988.
D. Chaum. Demonstrating that a public predicate can be satisfied without revealing any information about how. In Crypto 86, pages 195–199, 1986.
D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 11–19, 1988.
D. Chaum, I. Damgård, and J. van de Graaf. Multiparty computations ensuring privacy of each party's input and correctness of the result. In Crypto 87, pages 87–119, 1987.
D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of a discrete logarithm and some generalizations. In Euro Crypt 87, pages 127–141, 1987.
L. Fortnow. The complexity of perfect zero-knowledge. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, pages 204–209, 1987.
M. R.Garey and D. S.Johnson. Computers and Intractability, A Guide to the Theory ofNP-Completeness. Freeman, San Francisco, 1979.
O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th IEEE Symposium on the Foundations of Computer Science, pages 174–187, 1986.
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, pages 291–304, 1985.
S.Goldwasser, S.Micali, and C.Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal on Computing, 18:186–208, 1989.
G. E.Hardy and E. M.Wright. An Introduction to the Theory of Numbers, fifth edition. Oxford University Press, Oxford, 1979.
S.Pohlig and M. E.Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory, 24:106–110, 1978.
A. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science, pages 80–91, 1982.
Author information
Authors and Affiliations
Additional information
The first author was supported in part by NSA Grant MDA 904-84-H-00171. The second author was supported in part by NSF Grant DCR-8602562.
Rights and permissions
About this article
Cite this article
Boyar, J.F., Kurtz, S.A. & Krentel, M.W. A discrete logarithm implementation of perfect zero-knowledge blobs. J. Cryptology 2, 63–76 (1990). https://doi.org/10.1007/BF00204448
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00204448