Analysis of the Xedni calculus attack

DOI10.1023/A:1008312401197MaRDI QIDQ1974057zbMATH OpenFDO

Authors Neal Koblitz, Joseph H. Silverman, Edlyn Teske, Michael J. Jacobson jun., Andreas Stein

Publication date 20 November 2000

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1008312401197

zbMATH Keywords

discrete logarithm problemelliptic curvesrankXedni calculus attack

Mathematics Subject Classification ID

Elliptic curves over global fields (11G05) Number-theoretic algorithms; complexity (11Y16) Computational aspects of algebraic curves (14Q05) Cryptography (94A60)

Review text

Elliptic curves defined over finite fields provide secure cryptosystems that are currently included in several industrial products. A crucial question hence concerns the security of the elliptic curve discrete logarithm problem (ECDLP). The Xedni attack on ECDLP involves lifting points and the curve from the considered finite field to \({\mathbb Q}\). If the lifted points are linearly dependant, then the ECDLP is solved. This article describes in details the Xedni attack, and provides valuable background (Hasse-Weil \(L\)-function, Taniyama conjecture, conjecture of Birch and Swinnerton-Dyer, heights). It is shown that this attack is asymptotically unlikely succesful. Moreover, even for small base finite fields, this attack fails very often (how often is made precise in the article), so that the Xedni calculus is impractical for the fields used in elliptic curve cryptography.

Recommendations

• Selected Areas in Cryptography
• Information and Communications Security
• On the Automatic Analysis of Recursive Security Protocols with XOR
• Fault attacks on XEX mode with application to certain authenticated encryption modes
• Analysis of differential attacks in ARX constructions
• Further Security Analysis of XTR
• Differential power analysis of XMSS and SPHINCS
• Improved Security Analysis of XEX and LRW Modes
• Soft analytical side-channel attacks

Cited in

(11)

• The Xedni calculus and the elliptic curve discrete logarithm problem
• Elliptic curve lifting problem and its applications
• The multi-base discrete logarithm problem: tight reductions and non-rewinding proofs for Schnorr identification and signatures
• Elliptic curve cryptography: the serpentine course of a paradigm shift
• Global duality, signature calculus and the discrete logarithm problem
• Lifting and Elliptic Curve Discrete Logarithms
• Computing Prime Factorization And Discrete Logarithms: From Index Calculus To Xedni Calculus
• Obstacles to the torsion-subgroup attack on the decision Diffie-Hellman Problem
• Algebraic curves and cryptography
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• Recent progress on the elliptic curve discrete logarithm problem

This page was built for publication: Analysis of the Xedni calculus attack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1974057)