Welcome to the resource topic for 2023/539
Title:
Dlog is Practically as Hard (or Easy) as DH – Solving Dlogs via DH Oracles on EC Standards
Authors: Alexander May, Carl Richard Theodor Schneider
Abstract:Assume that we have a group G of known order q, in which we want to solve discrete logarithms (dlogs). In 1994, Maurer showed how to compute dlogs in G in poly time given a Diffie-Hellman (DH) oracle in G, and an auxiliary elliptic curve \hat E(\mathbb{F}_q) of smooth order. The problem of Maurer’s reduction of solving dlogs via DH oracles is that no efficient algorithm for constructing such a smooth auxiliary curve is known. Thus, the implications of Maurer’s approach to real-world applications remained widely unclear.
In this work, we explicitly construct smooth auxiliary curves for a dozen of mostly used, standardized elliptic curves of bit-sizes in the range [204,256], including e.g., NIST P-256, Curve25519, SM2 and GOST R34.10. For all these curves we construct a corresponding cyclic auxiliary curve \hat E(\mathbb{F}_q), whose order is 39-bit smooth, i.e., its largest factor is of bit-length at most 39 bits.
This in turn allows us to compute for all divisors of the order of \hat E(\mathbb{F}_q) exhaustively a codebook for all discrete logarithms. As a consequence, dlogs on \hat E(\mathbb{F}_q) can efficiently be computed in a matter of seconds.
Our resulting codebook sizes are less than 29 TByte, and fit on our hard disk.
We also construct auxiliary curves for NIST P-384 and NIST P-521 with a 65-bit and 110-bit smooth order.
Further, we provide an efficient implementation of Maurer’s reduction from the dlog computation in G with order q to the dlog computation on its auxiliary curve \hat E(\mathbb{F}_q). Let us provide a flavor of our results, e.g., when G is the NIST P-256 group, the results for other curves are similar. With the help of our codebook for the auxiliary curve \hat E(\mathbb{F}_q), and less than 24,000 calls to a DH oracle in G (that we simulate), we can solve discrete logarithms on NIST P-256 in around 30 secs.
From a security perspective, our results show that for current elliptic curve standards the difficulty of solving DH is practically tightly related to the difficulty of computing dlogs. Namely, unless dlogs are easy to compute on these curves G, we provide a very concrete security guarantee that DH in G must also be hard.
From a cryptanalytic perspective, our results show a way to efficiently solve discrete logarithms in the presence of a DH oracle. Thus, if practical implementations unintentionally provide a DH oracle, dlog computations actually become surprisingly easy.
ePrint: https://eprint.iacr.org/2023/539
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .