Paper 2023/539
Dlog is Practically as Hard (or Easy) as DH – Solving Dlogs via DH Oracles on EC Standards
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 DiffieHellman (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 realworld applications remained widely unclear. In this work, we explicitly construct smooth auxiliary curves for $13$ commonly used, standardized elliptic curves of bitsizes in the range $[204,256]$, including e.g., NIST P256, 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 bitlength 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 for each auxiliary curve are less than 29 TByte individually, and fit on our hard disk. We also construct auxiliary curves for NIST P384 and NIST P521 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 P256 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 P256 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in TCHES 2023
 DOI
 10.46586/tches.v2023.i4.146166
 Keywords
 Discrete LogarithmElliptic CurveDiffieHellmanOraclesImplementation
 Contact author(s)

alex may @ rub de
carl schneider @ rub de  History
 20230912: last of 2 revisions
 20230414: received
 See all versions
 Short URL
 https://ia.cr/2023/539
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/539, author = {Alexander May and Carl Richard Theodor Schneider}, title = {Dlog is Practically as Hard (or Easy) as {DH} – Solving Dlogs via {DH} Oracles on {EC} Standards}, howpublished = {Cryptology ePrint Archive, Paper 2023/539}, year = {2023}, doi = {10.46586/tches.v2023.i4.146166}, note = {\url{https://eprint.iacr.org/2023/539}}, url = {https://eprint.iacr.org/2023/539} }