Analysis of the Xedni calculus attack

被引：21

作者：

Jacobson, MJ ^{[1
]}

Koblitz, N ^{[1
]}

Silverman, JH ^{[1
]}

Stein, A ^{[1
]}

Teske, E ^{[1
]}

机构：

[1] Univ Waterloo, Ctr Appl Cryptog Res, Waterloo, ON N2L 3G1, Canada

来源：

DESIGNS CODES AND CRYPTOGRAPHY | 2000年 / 20卷 / 01期

关键词：

elliptic curve; discrete logarithm; Xedni calculus;

D O I：

10.1023/A:1008312401197

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The xedni calculus attack on the elliptic curve discrete logarithm problem (ECDLP) involves lifting points from the finite field F-p to the rational numbers Q and then constructing an elliptic curve over Q that passes through them. If the lifted points are linearly dependent, then the ECDLP is solved. Our purpose is to analyze the practicality of this algorithm. We find that asymptotically the algorithm is virtually certain to fail, because of an absolute bound on the size of the coefficients of a relation satisfied by the lifted points. Moreover, even for smaller values of p experiments show that the odds against finding a suitable lifting are prohibitively high.

引用

页码：41 / 64

页数：24

共 38 条

[11]

Koblitz N., 1998, ALGEBRAIC ASPECTS CR

[12]

Koblitz N., 1993, INTRO ELLIPTIC CURVE

[13]

Lang S., 1983, FUNDAMENTAL DIOPHANT

[14] SPECIALIZATIONS OF FINITELY GENERATED SUBGROUPS OF ABELIAN-VARIETIES [J].

MASSER, DW .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 311 (01) :413-424

[15]

MAZUR B., 1977, I HAUTES ETUDES SCI, P33, DOI [DOI 10.1007/BF02684339, 10.1007/BF02684339]

[16]

Menezes A.J., 1993, ELLIPTIC CURVE PUBLI

[17]

Menezes AJ., 1997, HDB APPL CRYPTOGRAPH

[18]

MESTRE JF, 1982, CR ACAD SCI I-MATH, V295, P643

[19]

MESTRE JF, 1986, COMPOS MATH, V58, P209

[20] USE OF ELLIPTIC-CURVES IN CRYPTOGRAPHY [J].

MILLER, VS .

LECTURE NOTES IN COMPUTER SCIENCE, 1986, 218 :417-426

← 1 2 3 4 →