Reynald Lercier

A. Joux, R. Lercier, D. Naccache, and E. Thomé. Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms. In MatthewG. Parker, editor, Cryptography and Coding, volume 5921 of Lecture Notes in Computer Science, pages 351-367. Springer Berlin Heidelberg, December 2009. Twelfth IMA International Conference on Cryptography and Coding conference, Royal Agricultural College, Cirencester, UK.

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

[ bib | preprint | publication ] Back