On the complexity of the discrete logarithm and Diffie-Hellman problems. (English) Zbl 1052.94014
The discrete logarithm problem (DLP): given an element \(a\) in a cyclic group \(G=\langle g\rangle\) of order \(n\) find the unique integer \(x\), \(0\leq x \leq n-1\) such that \(a = g^x\), is widely believed to be a computationally hard problem. It was proposed as a one-way function for use in public-key cryptography in the foundational paper of W. Diffie and M. E. Hellman [IEEE Trans. Inf. Theory 22, 644–654 (1976; Zbl 0435.94018)].
In that paper Diffie and Hellman also give a key exchange method related to DLP: two users randomly choose integers \(a,b\in (1,n)\) and they exchange \(g^a,g^b\). Each of them is then able to compute the common value \(g^{ab}\). The computation of \(g^{ab}\) given only \(g^a,g^b\) is called the Diffie-Hellman problem (DHP). Of course if one can solve DLP one can also solve DHP.
A connected problem is the decision DHP (DDHP): given \(g^a,g^b,g^c\) decide if \(ab\equiv c \bmod n\). In general, DDHP is no harder than DHP and this is no harder than DLP. The object of the present paper is the study of some aspects of these relationships.
In Section 2 the authors give an overview of the state of the art of these three and other related problems. Section 3 deals with the computational complexity of these problems in generic cyclic groups. An algorithm is called generic if it works for arbitrary groups, in contrast to algorithms that make use of some particular presentation of the group elements, as is the case in the well-known index-calculus method, which provides an algorithm of subexponential complexity for the DLP in multiplicative groups of finite fields and in Jacobians of hyperelliptic curves of large genus.
Section 5 is the core of the paper. The authors first remember a previous result of D. Boneh and R. Venkatesan [Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, Proc. CRYPTO ‘96, Lect. Notes Comput. Sci. 1109, 129–142 (1996)] that shows that it is as hard to compute the \(O(\sqrt n)\) most significant bits of the DHP as it is to compute the whole function. They prove then that if the DDHP is supposed to be hard then computing the two most significant bits of the DHP is also hard.
The last section of the paper discusses the open question as to whether there exists a deterministic reduction of DDHP to the problem of computing the two most significant bits of DHP. A large list of references is also provided at the end of the paper.
In that paper Diffie and Hellman also give a key exchange method related to DLP: two users randomly choose integers \(a,b\in (1,n)\) and they exchange \(g^a,g^b\). Each of them is then able to compute the common value \(g^{ab}\). The computation of \(g^{ab}\) given only \(g^a,g^b\) is called the Diffie-Hellman problem (DHP). Of course if one can solve DLP one can also solve DHP.
A connected problem is the decision DHP (DDHP): given \(g^a,g^b,g^c\) decide if \(ab\equiv c \bmod n\). In general, DDHP is no harder than DHP and this is no harder than DLP. The object of the present paper is the study of some aspects of these relationships.
In Section 2 the authors give an overview of the state of the art of these three and other related problems. Section 3 deals with the computational complexity of these problems in generic cyclic groups. An algorithm is called generic if it works for arbitrary groups, in contrast to algorithms that make use of some particular presentation of the group elements, as is the case in the well-known index-calculus method, which provides an algorithm of subexponential complexity for the DLP in multiplicative groups of finite fields and in Jacobians of hyperelliptic curves of large genus.
Section 5 is the core of the paper. The authors first remember a previous result of D. Boneh and R. Venkatesan [Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, Proc. CRYPTO ‘96, Lect. Notes Comput. Sci. 1109, 129–142 (1996)] that shows that it is as hard to compute the \(O(\sqrt n)\) most significant bits of the DHP as it is to compute the whole function. They prove then that if the DDHP is supposed to be hard then computing the two most significant bits of the DHP is also hard.
The last section of the paper discusses the open question as to whether there exists a deterministic reduction of DDHP to the problem of computing the two most significant bits of DHP. A large list of references is also provided at the end of the paper.
Reviewer: Juan Tena Ayuso (Valladolid)
MSC:
| 94A60 | Cryptography |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 11Y16 | Number-theoretic algorithms; complexity |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68P25 | Data encryption (aspects in computer science) |
Citations:
Zbl 0435.94018Software:
OracleReferences:
| [1] | M. Ajtai, S. Ravi Kumar, D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, in: 33rd Annual ACM Symposium on Theory of Computing, 2001.; M. Ajtai, S. Ravi Kumar, D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, in: 33rd Annual ACM Symposium on Theory of Computing, 2001. · Zbl 1323.68561 |
| [2] | Biham, E.; Boneh, D.; Reingold, O., Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring, Inform. Process. Lett., 70, 83-87 (1997) · Zbl 1003.94521 |
| [3] | Blake, I. F.; Seroussi, G.; Smart, N. P., Elliptic Curves in Cryptography. Elliptic Curves in Cryptography, London Mathematical Society, Lecture Note Series, Vol. 265 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0937.94008 |
| [4] | D. Boneh, The decision Diffie-Hellman problem, ANTS III, in: J.P. Buhler (Ed.), Lecture Notes in Computer Science, Vol. 1423, Springer, Berlin, 1998, pp. 48-63.; D. Boneh, The decision Diffie-Hellman problem, ANTS III, in: J.P. Buhler (Ed.), Lecture Notes in Computer Science, Vol. 1423, Springer, Berlin, 1998, pp. 48-63. · Zbl 1067.94523 |
| [5] | Boneh, D.; Lipton, R. J., Algorithms for black-box fields and their application to cryptography, (Koblitz, N., Crypto ’96. Crypto ’96, Lecture Notes in Computer Science, Vol. 1109 (1996), Springer: Springer Berlin), 283-297 · Zbl 1329.94053 |
| [6] | Boneh, D.; Shparlinski, I. E., On the unpredictability of elliptic curve Diffie-Hellman scheme, (Kilian, J., Crypto ’01. Crypto ’01, Lecture Notes in Computer Science, Vol. 2139 (2001), Springer: Springer Berlin), 201-212 · Zbl 1002.94025 |
| [7] | Boneh, D.; Venkatesan, R., Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, (Koblitz, N., Crypto ’96. Crypto ’96, Lecture Notes in Computer Science, Vol. 1109 (1996), Springer: Springer Berlin), 129-142 · Zbl 1329.94054 |
| [8] | D. Boneh, R. Venkatesan, Rounding in lattices and its cryptographic applications, Proceedings of the SODA, 1997, pp. 675-681.; D. Boneh, R. Venkatesan, Rounding in lattices and its cryptographic applications, Proceedings of the SODA, 1997, pp. 675-681. · Zbl 1321.94045 |
| [9] | Buchmann, J.; Williams, H. C., A key-exchange system based on imaginary quadratic fields, J. Cryptology, 1, 107-118 (1988) · Zbl 0659.94004 |
| [10] | J. Buchmann, H.C. Williams, Quadratic fields and cryptography, Number Theory and Cryptology, London Mathematical Society Lecture Notes, Vol. 154, Cambridge University Press, Cambridge, 1990, pp. 9-26.; J. Buchmann, H.C. Williams, Quadratic fields and cryptography, Number Theory and Cryptology, London Mathematical Society Lecture Notes, Vol. 154, Cambridge University Press, Cambridge, 1990, pp. 9-26. · Zbl 0711.11038 |
| [11] | Canetti, R.; Friedlander, J.; Shparlinski, I., On certain exponential sums and the distribution of Diffie-Hellman triples, J. London Math. Soc., 59, 799-812 (1999) · Zbl 0935.11028 |
| [12] | Canetti, R.; Friedlander, J. B.; Konyagin, S.; Larsen, M.; Lieman, D.; Shparlinski, I. E., On the statistical properties of Diffie-Hellman distributions, Israel J. Math., 120, 23-46 (2000) · Zbl 0997.11066 |
| [13] | Cherepnev, M. A., On the connection between the discrete logarithms and the Diffie-Hellman problem, Discrete Math. Appl., 6, 341-349 (1996) · Zbl 0864.94015 |
| [14] | Diffie, W.; Hellman, M. E., New directions in cryptography, IEEE Trans. Inform. Theory, 22, 644-654 (1976) · Zbl 0435.94018 |
| [15] | Enge, A.; Gaudry, P., A general framework for subexponential discrete logarithm algorithms, Acta Arith., 202, 1, 83-103 (2002) · Zbl 1028.11079 |
| [16] | Fouquet, M.; Gaudry, P.; Harley, R., An extension of Satoh’s algorithm and its implementation, J. Ramanujan Math. Soc., 15, 281-318 (2000) · Zbl 1009.11048 |
| [17] | Frey, G.; Müller, M.; Rück, H. G., The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems, IEEE Trans. Inform. Theory, 45, 5, 717-1719 (1999) · Zbl 0957.94025 |
| [18] | Frey, G.; Rück, H.-G., A remark concerning \(m\)-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comput., 62, 865-874 (1994) · Zbl 0813.14045 |
| [19] | Friedlander, J. B.; Shparlinski, I. E., On the distribution of Diffie-Hellman triples with sparse exponents, SIAM J. Discrete Math., 14, 162-169 (2001) · Zbl 0973.11100 |
| [20] | Garefalakis, T., The generalized Weil pairing and the discrete logarithm problem on elliptic curves, (Rajsbaum, S., Fifth Latin American Symposium on Theoretical Informatics—LATIN 2002. Fifth Latin American Symposium on Theoretical Informatics—LATIN 2002, Lecture Notes in Computer Science, Vol. 2286 (2002), Cancun: Cancun Mexico), 118-130 · Zbl 1152.11332 |
| [21] | P. Gaudry, An algorithm for solving the discrete logarithm problem on hyperelliptic curves, Eurocrypto 2000, Lecture Notes in Computer Science, Vol. 1807, Springer, Berlin, 2000, pp. 19-34.; P. Gaudry, An algorithm for solving the discrete logarithm problem on hyperelliptic curves, Eurocrypto 2000, Lecture Notes in Computer Science, Vol. 1807, Springer, Berlin, 2000, pp. 19-34. · Zbl 1082.94517 |
| [22] | H. Handschuh, Y. Tsiounis, M. Young, Decision oracles are equivalent to matching oracles, Technical Report PK01-1999, Gemplus Corporation, 1999.; H. Handschuh, Y. Tsiounis, M. Young, Decision oracles are equivalent to matching oracles, Technical Report PK01-1999, Gemplus Corporation, 1999. · Zbl 0929.94014 |
| [23] | M. Isabel, G. Vasco, I.E. Shparlinski, On the security of Diffie-Hellman bits, Proceedings of the Workshop on Cryptology and Computational Number Theory, Birkhauser, Singapore, 2001, pp. 331-342.; M. Isabel, G. Vasco, I.E. Shparlinski, On the security of Diffie-Hellman bits, Proceedings of the Workshop on Cryptology and Computational Number Theory, Birkhauser, Singapore, 2001, pp. 331-342. · Zbl 0997.94548 |
| [24] | A. Joux, K. Nguyen, Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, eprint.iacr.org/2001/003.ps.gz; A. Joux, K. Nguyen, Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, eprint.iacr.org/2001/003.ps.gz · Zbl 1101.14309 |
| [25] | Kannan, R., Algorithmic geometry of numbers, Annu. Rev. Comput. Sci., 2, 231-267 (1987) |
| [26] | Koblitz, N., Algebraic aspects of cryptography, Algorithms and Computation in Mathematics, Vol. 3 (1998), Springer: Springer Berlin · Zbl 0890.94001 |
| [27] | Konyagin, S.; Lange, T.; Shparlinski, I. E., Linear complexity of the discrete logarithm, Des. Codes Cryptogr., 28, 135-146 (2003) · Zbl 1024.11078 |
| [28] | El Mahassni, E.; Shparlinski, I. E., Polynomial representations of the Diffie-Hellman mapping, Bull. Austral. Math. Soc., 63, 467-473 (2001) · Zbl 0974.11040 |
| [29] | U.M. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Crypto ’94, Lecture Notes in Computer Science, Vol. 839, Springer, Berlin, 1994, pp. 271-281.; U.M. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Crypto ’94, Lecture Notes in Computer Science, Vol. 839, Springer, Berlin, 1994, pp. 271-281. · Zbl 0939.94564 |
| [30] | U.M. Maurer, S. Wolf, On the complexity of breaking the Diffie-Hellman protocol, Technical Report 244, Inst. Theor. Comp. Sci., ETH, Zürich, 1996.; U.M. Maurer, S. Wolf, On the complexity of breaking the Diffie-Hellman protocol, Technical Report 244, Inst. Theor. Comp. Sci., ETH, Zürich, 1996. |
| [31] | Maurer, U. M.; Wolf, S., Diffie-Hellman oracles, (Koblitz, N., Crypto ’96. Crypto ’96, Lecture Notes in Computer Science, Vol. 1109 (1996), Springer: Springer Berlin), 268-282 · Zbl 1329.94072 |
| [32] | Maurer, U. M.; Wolf, S., Lower bounds on generic algorithms in groups, (Nyberg, K., Eurocrypt ’98. Eurocrypt ’98, Lecture Notes in Computer Science, Vol. 1403 (1998), Springer: Springer Berlin), 72-84 · Zbl 0919.94027 |
| [33] | U.M. Maurer, S. Wolf, Diffie-Hellman, Decision Diffie-Hellman and discrete logarithms, International Symposium on Information Theory, Ulm, June, 1998.; U.M. Maurer, S. Wolf, Diffie-Hellman, Decision Diffie-Hellman and discrete logarithms, International Symposium on Information Theory, Ulm, June, 1998. |
| [34] | Maurer, U. M.; Wolf, S., The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms, SIAM J. Comput., 28, 1689-1721 (1999) · Zbl 1053.94014 |
| [35] | Maurer, U. M.; Wolf, S., The Diffie-Hellman protocol, Des. Codes Cryptogr., 19, 147-171 (2000) · Zbl 0983.94037 |
| [36] | Menezes, A. J., Elliptic Curve Public Key Cryptosystems (1993), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0806.94011 |
| [37] | Menezes, A. J.; Okamoto, T.; Vanstone, S., Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory, 39, 1639-1646 (1993) · Zbl 0801.94011 |
| [38] | Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0849.68039 |
| [39] | Nechaev, V. I., Complexity of a deterministic algorithm for the discrete logarithm, Math. Notes, 55, 2, 165-172 (1994) · Zbl 0831.11065 |
| [40] | Okamoto, T.; Pointcheval, D., The gap problems: a new class of problems for the security of cryptographic schemes, (Kim, K., PKC 2001. PKC 2001, Lecture Notes in Computer Science, Vol. 1992 (2001), Springer: Springer Berlin), 104-118 · Zbl 0984.94509 |
| [41] | Paulus, S.; Rück, H.-G., Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comput., 68, 1233-1242 (1999) · Zbl 0923.11160 |
| [42] | Peralta, R., A simple and fast probabilistic algorithm for computing square roots modulo a prime number, IEEE Trans. Inform. Theory, 32, 846-847 (1986) · Zbl 0658.68043 |
| [43] | Pollard, J., Monte carlo methods for index computations (mod p), Math. Comput., 32, 918-924 (1978) · Zbl 0382.10001 |
| [44] | K. Rubin, A. Silverberg, Supersingular abelian varieties in cryptology, preprint, 2002.; K. Rubin, A. Silverberg, Supersingular abelian varieties in cryptology, preprint, 2002. · Zbl 1026.94540 |
| [45] | Satoh, T., The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc., 15, 247-270 (2000) · Zbl 1009.11051 |
| [46] | Scheidler, R., Cryptography in quadratic number fields, Des. Codes Cryptogr., 22, 239-264 (2001) · Zbl 0985.94034 |
| [47] | Schoof, R., Counting points on elliptic curves over finite fields, Journal Theorie des Nombres de Bordeaux, 7, 219-254 (1995) · Zbl 0852.11073 |
| [48] | Shoup, V., Lower bounds for discrete logarithms and related problems, (Fumy, W., Eurocrypt ’97. Eurocrypt ’97, Lecture Notes in Computer Science, Vol. 1233 (1997), Springer: Springer Berlin), 256-266 |
| [49] | Shparlinski, I. E., On the distribution of Diffie-Hellman pairs, Finite Fields Appl., 8, 131-141 (2002) · Zbl 1003.11059 |
| [50] | Shparlinski, I. E., Security of most significant bits of \(g^{x^2}\), Inform. Process. Lett., 8, 131-141 (2002) · Zbl 1043.94014 |
| [51] | E. Teske, Square-root algorithms for the discrete logarithm problem (a survey), Proceedings of the International Conference on Public-Key Cryptography and Computational Number Theory, Walter de Gruyter, Berlin, 2001, pp. 283-301.; E. Teske, Square-root algorithms for the discrete logarithm problem (a survey), Proceedings of the International Conference on Public-Key Cryptography and Computational Number Theory, Walter de Gruyter, Berlin, 2001, pp. 283-301. · Zbl 1001.11059 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
