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

Abstract : 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.
Document type :
Conference papers
Matthew G. Parker. Twelfth IMA International Conference on Cryptography and Coding, Dec 2009, Cirencester, United Kingdom. Springer Berlin / Heidelberg, 5921, pp.351-367, 2009, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/28420214666n3715/fulltext.pdf〉. 〈10.1007/978-3-642-10868-6_21〉
Liste complète des métadonnées

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00337753
Contributor : Emmanuel Thomé <>
Submitted on : Tuesday, November 17, 2009 - 10:52:01 PM
Last modification on : Tuesday, June 19, 2018 - 11:12:06 AM
Document(s) archivé(s) le : Saturday, November 26, 2016 - 2:33:55 PM

File

DLForgeV3.pdf
Files produced by the author(s)

Identifiers

Citation

Antoine Joux, Reynald Lercier, David Naccache, Emmanuel Thomé. Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms. Matthew G. Parker. Twelfth IMA International Conference on Cryptography and Coding, Dec 2009, Cirencester, United Kingdom. Springer Berlin / Heidelberg, 5921, pp.351-367, 2009, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/28420214666n3715/fulltext.pdf〉. 〈10.1007/978-3-642-10868-6_21〉. 〈inria-00337753v2〉

Share

Metrics

Record views

636

Files downloads

154