ON THE DISCRETE LOGARITHM PROBLEM IN CLASS GROUPS OF CURVES

被引:18
作者
Diem, Claus [1 ]
机构
[1] Univ Leipzig, Inst Math, D-04103 Leipzig, Germany
关键词
Discrete logarithm problem; curves; index calculus; ROOTS;
D O I
10.1090/S0025-5718-2010-02281-1
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We study the discrete logarithm problem in degree 0 class groups of curves over finite fields, with particular emphasis on curves of small genus. We prove that for every fixed g >= 2, the discrete logarithm problem in degree 0 class groups of curves of genus g can be solved in an expected time of a (O) over tilde (q(2-2/g)), where F-q, is the ground field. This result generalizes a corresponding result for hyperelliptic curves given in imaginary quadratic representation with cyclic degree 0 class group, and just as this previous result, it is obtained via an index calculus algorithm with double large prime variation. Generalizing this result, we prove that for fixed g(0) >= 2 the discrete logarithm problem in class groups of all curves C/F-q of genus g >= g(0) can be solved in an expected time of (O) over tilde((q(g))(2/g0(1- 1/g0))) and in an expected time of (O) over tilde(#Cl-0(C)(2/g0(1 - 1/g0))). As a complementary result we prove that for any fixed n is an element of N with n >= 2 the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields F-qn, q a prime power, can be solved in an expected time of (O) over tilde (q(2-2/n)). Furthermore, we give an algorithm for the efficient construction of a uniformly randomly distributed effective divisor of a specific degree, given the curve and its L-polynomial.
引用
收藏
页码:443 / 475
页数:33
相关论文
共 50 条
[41]   New Blind Signature Schemes Based on the (Elliptic Curve) Discrete Logarithm Problem [J].
Mala, Hamid ;
Nezhadansari, Nafiseh .
PROCEEDINGS OF THE 3RD INTERNATIONAL CONFERENCE ON COMPUTER AND KNOWLEDGE ENGINEERING (ICCKE 2013), 2013, :196-201
[42]   An Efficient Digital Signature Scheme by using Integer Factorization and Discrete Logarithm Problem [J].
Tripathi, Shailendra Kumar ;
Gupta, Bhupendra .
2017 INTERNATIONAL CONFERENCE ON ADVANCES IN COMPUTING, COMMUNICATIONS AND INFORMATICS (ICACCI), 2017, :1261-1266
[43]   Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval [J].
Galbraith, Steven D. ;
Ruprai, Raminder S. .
PUBLIC KEY CRYPTOGRAPHY - PKC 2010, PROCEEDINGS, 2010, 6056 :368-+
[44]   Post-quantum signature algorithms based on the hidden discrete logarithm problem [J].
Moldovyan, A. A. ;
Moldovyan, N. A. .
COMPUTER SCIENCE JOURNAL OF MOLDOVA, 2018, 26 (03) :301-313
[45]   Cryptanalysing the critical group: efficiently solving Biggs's discrete logarithm problem [J].
Blackburn, Simon R. .
JOURNAL OF MATHEMATICAL CRYPTOLOGY, 2009, 3 (03) :199-203
[46]   Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields [J].
Joux, Antoine ;
Vitse, Vanessa .
JOURNAL OF CRYPTOLOGY, 2013, 26 (01) :119-143
[47]   An efficient ID-based cryptographic encryption based on discrete logarithm problem and integer factorization problem [J].
Meshram, Chandrashekhar .
INFORMATION PROCESSING LETTERS, 2015, 115 (02) :351-358
[48]   A method of solution of the problem of taking the discrete logarithm on an elliptic curve by division of points by two [J].
Bessalov A.V. .
Cybernetics and Systems Analysis, 2001, 37 (6) :820-823
[49]   Practical Solving of Discrete Logarithm Problem over Prime Fields Using Quantum Annealing [J].
Wronski, Michal .
COMPUTATIONAL SCIENCE, ICCS 2022, PT IV, 2022, :93-106
[50]   Robust Comparative Analysis of Zero-Knowledge Proofs using Discrete Logarithm Problem [J].
Sah, Chitranjan Prasad ;
Gupta, Preeti Rani .
PROCEEDINGS OF THE 7TH INTERNATIONAL CONFERENCE ON COMPUTING FOR SUSTAINABLE GLOBAL DEVELOPMENT (INDIACOM-2020), 2019, :11-15