International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Antoine Joux
Emmanuel Thomé
Reynald Lercier
David Naccache
Download:
URL: http://eprint.iacr.org/2008/217
Search ePrint
Search Google
Abstract: This paper extends Joux-Naccache-Thom\'e'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$.
BibTeX
@misc{eprint-2008-17894,
  title={Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / DLP, SDH, oracle, NFS, FFS},
  url={http://eprint.iacr.org/2008/217},
  note={ david@naccache.fr 14013 received 14 May 2008},
  author={Antoine Joux and Emmanuel Thomé and Reynald Lercier and David Naccache},
  year=2008
}