zbMATH — the first resource for mathematics

Oracle-assisted static Diffie-Hellman is easier than discrete logarithms. (English) Zbl 1234.94050
Parker, Matthew G. (ed.), Cryptography and coding. 12th IMA international conference, cryptography and coding 2009, Cirencester, UK, December 15–17, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10867-9/pbk). Lecture Notes in Computer Science 5921, 351-367 (2009).
Summary: 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 $${\mathbb F}_{2^{1025}}$$ and also in $${\mathbb F}_{p}$$, for a 516-bit $$p$$.
For the entire collection see [Zbl 1178.94006].

MSC:
 94A60 Cryptography
Keywords:
DLP; SHDP; FFS; NFS
Full Text: