Cryptology ePrint Archive: Report 2008/217

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

Antoine Joux and Reynald Lercier and 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$.

Category / Keywords: public-key cryptography / DLP, SDH, oracle, NFS, FFS

Date: received 14 May 2008

Contact author: david at naccache fr

Available format(s): PDF | BibTeX Citation

Version: 20080523:071732 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]