Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem

被引：59
作者：
Gaudry, Pierrick [1 ,2 ]
机构：
[1] Ecole Polytech, LIX, F-91128 Palaiseau, France
[2] LORIA, F-54506 Vandoeuvre Les Nancy, France
来源：
JOURNAL OF SYMBOLIC COMPUTATION | 2009年 / 44卷 / 12期
关键词：
Discrete logarithm problem; Elliptic curve; Index calculus; Weil descent; WEIL DESCENT; HYPERELLIPTIC CURVES; XEDNI CALCULUS; ALGORITHM; ATTACK;
D O I：
10.1016/j.jsc.2008.08.005
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties of small dimension. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve an elliptic curve discrete logarithm problem defined over F-q3 in heuristic asymptotic running time (O) over tilde (q(4/3)); and an elliptic problem over F-q4 or a genus 2 problem over F-q2 in heuristic asymptotic running time (O) over tilde (q(3/2)). (c) 2008 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1690 / 1702
页数：13
相关论文
共 33 条
  • [21] Quantum algorithm for solving hyperelliptic curve discrete logarithm problem
    Yan Huang
    Zhaofeng Su
    Fangguo Zhang
    Yong Ding
    Rong Cheng
    Quantum Information Processing, 2020, 19
  • [22] Improvement of digital signature variants based on elliptic curve with message recovery and its discrete logarithm problem
    Shao, ZH
    COMPUTER STANDARDS & INTERFACES, 2004, 27 (01) : 61 - 69
  • [23] The generalized Weil pairing and the discrete logarithm problem on elliptic curves
    Garefalakis, T
    THEORETICAL COMPUTER SCIENCE, 2004, 321 (01) : 59 - 72
  • [24] On the discrete logarithm problem for prime-field elliptic curves
    Amadori, Alessandro
    Pintore, Federico
    Sala, Massimiliano
    FINITE FIELDS AND THEIR APPLICATIONS, 2018, 51 : 168 - 182
  • [25] Symmetrized Summation Polynomials: Using Small Order Torsion Points to Speed Up Elliptic Curve Index Calculus
    Faugere, Jean-Charles
    Huot, Louise
    Joux, Antoine
    Renault, Guenael
    Vitse, Vanessa
    ADVANCES IN CRYPTOLOGY - EUROCRYPT 2014, 2014, 8441 : 40 - 57
  • [26] Cryptanalysis and improvement of the Tzeng-Hwang authenticated encryption scheme based on elliptic curve discrete logarithm problem
    Hsu, CL
    APPLIED MATHEMATICS AND COMPUTATION, 2005, 167 (02) : 882 - 890
  • [27] Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs
    Wenger, Erich
    Wolfger, Paul
    JOURNAL OF CRYPTOGRAPHIC ENGINEERING, 2016, 6 (04) : 287 - 297
  • [28] A knapsack public-key cryptosystem based on elliptic curve discrete logarithm
    Su, PC
    Lu, EH
    Chang, HKC
    APPLIED MATHEMATICS AND COMPUTATION, 2005, 168 (01) : 40 - 46
  • [29] An application of XTR for the discrete logarithm problem on Barreto-Naehrig curve
    Kono, Yuki
    Nogami, Yasuyuki
    2014 SECOND INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING (CANDAR), 2014, : 519 - 524
  • [30] Towards the Equivalence of Diffie-Hellman Problem and Discrete Logarithm Problem for Important Elliptic Curves Used in Practice
    Kushwaha, Prabhat
    2017 ISEA ASIA SECURITY AND PRIVACY CONFERENCE (ISEASP 2017), 2017, : 9 - 12
1234