Abstract
The Decision Diffie-Hellman assumption (ddh) is a gold mine. It enables one to construct efficient cryptographic systems with strong security properties. In this paper we survey the recent applications of DDH as well as known results regarding its security. We describe some open problems in this area.
Preview
Unable to display preview. Download preview PDF.
References
M. Beilare, S. Goldwasser, “New paradigms for digital signatures and message authentication based on non-interactive zero-knowledge proofs” Crypto '89, pp. 194–211.
M. Bellare, S. Micali, “Non-interactive oblivious transfer and applications”, Crypto '89, pp. 547–557.
D. Boneh, R. Lipton, “Black box fields and their application to cryptography”, Proc. of Crypto '96, pp. 283–297.
D. Boneh, R. Venkatesan, “Hardness of computing most significant bits in secret keys of Diffie-Hellman and related schemes”, Proc. of Crypto '96, pp. 129–142.
S. Brands, “An efficient off-line electronic cash system based on the representation problem”, CWI Technical report, CS-R9323, 1993.
R. Canetti, “Towards realizing random oracles: hash functions that hide all partial information”, Proc. Crypto '97, pp. 455–469.
R. Canetti, J. Friedlander, I. Shparlinski, “On certain exponential sums and the distribution of Diffie-Hellman triples”, Manuscript.
D. Chaum, H. van Antwerpen, “Undeniable signatures”, Proc. Crypto '89, pp. 212–216.
H. Cohen, “A course in computational number theory”, Springer-Verlag.
D. Coppersmith, “Finding a Small Root of a Bivariate Integer Equation; Factoring with high bits known”, Proc. Eurocrypt '96, 1996.
R. Cramer, V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack”, manuscript.
W. Diffie, M. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
D. Dolev, C. Dwork, M. Naor, “Non-malleable cryptography”, Proc. STOC' 91, pp. 542–552.
O. Goldreich, S. Goldwasser, S. Micali, “On the cryptographic applications of random functions”, Crypto' 84, pp. 276–288.
O. Goldreich, S. Goldwasser, S. Micali, “How to construct random functions”, J. ACM, Vol. 33, 1986, pp. 792–807.
O. Goldreich, L.A. Levin, “Hard core bits based on any one way function”, Proc. STOC '89.
S. Goldwasser, S. Micali, “Probabilistic encryption”, J. Computer and Syst. Sciences, Vol. 28, 1984, pp. 270–299.
J. Hastad, R. Impaglizzo, L. Levin, M. Luby, “Construction of pseudo random generators from one-way functions”, SIAM J. of Computing, to appear. Also see preliminary version in STOC 89.
A. Lenstra, H. Lenstra, L. Lovasz, “Factoring polynomial with rational coefficients”, Mathematiche Annalen, 261:515–534, 1982.
U. Maurer, “Towards proving the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms”, Proc. of Crypto '94, pp. 271–281.
U. Maurer, S. Wolf, “Diffie-Hellman oracles”, Proc. of Crypto '96, pp. 268–282.
M. Naor, O. Reingold, “Synthesizers and their application to the parallel construction of pseudo-random functions”, Proc. FOCS '95, pp. 170–181.
M. Naor, O. Reingold, “Number theoretic constructions of efficient pseudo random functions”, Proc. FOCS '97. pp. 458–467.
M. Naor, M. Yung, “Public key cryptosystems provable secure against chosen ciphertext attacks”, STOC '90, pp. 427–437
V. Nechaev, “Complexity of a determinate algorithm for the discrete logarithm”, Mathematical Notes, Vol. 55 (2), 1994, pp. 165–172.
C. Rackoff, D. Simon, “Non-interactive zero knowledge proof of knowledge and chosen ciphertext attack”, Crypto' 91, pp. 433–444.
C. Schnorr, “A hierarchy of polynomial time lattice basis reduction algorithms”, Theoretical Computer Science, Vol. 53, 1987, pp. 201–224.
J. Schwartz, “Fast probabilistic algorithms for verification of polynomial identities”, J. ACM, Vol. 27 (4), 1980, pp. 701–717.
V. Shoup, “Lower bounds for discrete logarithms and related problems”, Proc. Eurocrypt '97, pp. 256–266.
M. Stadler, “Publicly verifiable secret sharing”, Proc. Eurocrypt '96, pp. 190–199.
M. Steiner, G. Tsudik, M. Waidner, “Diffie-Hellman key distribution extended to group communication”, Proc. 3rd ACM Conference on Communications Security, 1996, pp. 31–37.
Y. Zheng, J. Seberry, “Practical approaches to attaining security against adaptively chosen ciphertext attacks”, Crypto '92, pp. 292–304.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boneh, D. (1998). The Decision Diffie-Hellman problem. In: Buhler, J.P. (eds) Algorithmic Number Theory. ANTS 1998. Lecture Notes in Computer Science, vol 1423. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054851
Download citation
DOI: https://doi.org/10.1007/BFb0054851
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64657-0
Online ISBN: 978-3-540-69113-6
eBook Packages: Springer Book Archive