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 non-adaptive 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 and also in , for a 516-bit p.
IMACC
2009
2026-06-08