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
F2^1025 and also in Fp, for a 516-bit p.
[ bib |