Paper 2008/217

Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms

Antoine Joux, Reynald Lercier, David Naccache, and Emmanuel Thomé

Abstract

This paper extends Joux-Naccache-Thomé's $e$-th root algorithm to the static Diffie-Hellman problem ({\sc sdhp}). The new algorithm can be adapted to diverse finite fields by customizing it with an {\sc nfs}-like core or an {\sc ffs}-like core. In both cases, after a number of {\sc sdhp} oracle queries, the attacker builds-up the ability to solve new {\sc sdhp} instances {\sl unknown before the query phase}. While sub-exponential, the algorithm is still significantly faster than all currently known {\sc dlp} and {\sc sdhp} resolution methods. We explore the applicability of the technique to various cryptosystems. The attacks were implemented in ${\mathbb F}_{2^{1025}}$ and also in ${\mathbb F}_{p}$, for a $516$-bit $p$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
DLPSDHoracleNFSFFS
Contact author(s)
david @ naccache fr
History
2008-05-23: received
Short URL
https://ia.cr/2008/217
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/217,
      author = {Antoine Joux and Reynald Lercier and David Naccache and Emmanuel Thomé},
      title = {Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms},
      howpublished = {Cryptology ePrint Archive, Paper 2008/217},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/217}},
      url = {https://eprint.iacr.org/2008/217}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.