TY - JOUR
AU - May, Alexander
AU - Schneider, Carl Richard Theodor
PY - 2023/08/31
Y2 - 2023/09/25
TI - Dlog is Practically as Hard (or Easy) as DH – Solving Dlogs via DH Oracles on EC Standards
JF - IACR Transactions on Cryptographic Hardware and Embedded Systems
JA - TCHES
VL - 2023
IS - 4
SE - Articles
DO - 10.46586/tches.v2023.i4.146-166
UR - https://tches.iacr.org/index.php/TCHES/article/view/11161
SP - 146-166
AB - <p>Assume that we have a group <em>G</em> of known order <em>q</em>, in which we want to solve discrete logarithms (dlogs). In 1994, Maurer showed how to compute dlogs in <em>G</em> in poly time given a Diffie-Hellman (DH) oracle in <em>G</em>, and an auxiliary elliptic curve ˆÊ (F<sub><em>q</em></sub>) 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.<br>In this work, we explicitly construct smooth auxiliary curves for 13 commonly 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 ˆÊ(F<sub><em>q</em></sub>), whose order is 39-bit smooth, i.e., its largest factor is of bit-length at most 39 bits.<br>This in turn allows us to compute for all divisors of the order of ˆÊ(F<sub><em>q</em></sub>) exhaustively a codebook for all discrete logarithms. As a consequence, dlogs on ˆÊ(F<sub><em>q</em></sub>) can efficiently be computed in a matter of seconds. Our resulting codebook sizes for each auxiliary curve are less than 29 TByte individually, and fit on our hard disk.<br>We also construct auxiliary curves for NIST P-384 and NIST P-521 with a 65-bit and 110-bit smooth order.<br>Further, we provide an efficient implementation of Maurer’s reduction from the dlog computation in <em>G</em> with order <em>q</em> to the dlog computation on its auxiliary curve ˆÊ (F<sub><em>q</em></sub>). 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 Ê(F<sub><em>q</em></sub>), and less than 24,000 calls to a DH oracle in<em> G</em> (that we simulate), we can solve discrete logarithms on NIST P-256 in around 30 secs.<br>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 <em>G</em>, we provide a very concrete security guarantee that DH in <em>G</em> 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.</p>
ER -