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 条

[1]

[Anonymous], 1978, GRUNDLEHREN MATH WIS

[2]

BIRCH BJ, 1965, J REINE ANGEW MATH, V218, P79

[3]

BIRCH BJ, 1975, LECT NOTES MATH, V476, P2

[4]

CASSELS JWS, 1966, J LONDON MATH SOC, V41, P193

[5]

CHEON JH, ANALOGUE INDEX CALCU

[6] CONJECTURE OF BIRCH AND SWINNERTON-DYER [J].

COATES, J ;

WILES, A .

INVENTIONES MATHEMATICAE, 1977, 39 (03) :223-251

[7] ON THE BIRCH AND SWINNERTON-DYER CONJECTURE [J].

GREENBERG, R .

INVENTIONES MATHEMATICAE, 1983, 72 (02) :241-265

[8] Extended GCD and Hermite normal form algorithms via lattice basis reduction [J].

Havas, G ;

Majewski, BS ;

Matthews, KR .

EXPERIMENTAL MATHEMATICS, 1998, 7 (02) :125-136

[9] THE CANONICAL HEIGHT AND INTEGRAL POINTS ON ELLIPTIC-CURVES [J].

HINDRY, M ;

SILVERMAN, JH .

INVENTIONES MATHEMATICAE, 1988, 93 (02) :419-450

[10]

KOBLITZ N, 1987, MATH COMPUT, V48, P203, DOI 10.1090/S0025-5718-1987-0866109-5

← 1 2 3 4 →