Elliptic Curve Discrete Logarithm Problem over Small Degree Extension FieldsTit
Title: Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields
Authors: Antoine Joux Vanessa Vitse
Abstract: In 2008 and 2009, Gaudry and Diem proposed an index calculus method for the resolution of the discrete logarithm on the group of points of an elliptic curve defined over a small degree extension field F q n. In this paper, we study a variation of this index calculus method, improving the overall asymptotic complexity when n = O( 3 log q). In particular, we are able to successfully obtain relations on E(F ), 2 q 5 whereas the more expensive computational complexity of Gaudry and Diem s initial algorithm makes it impractical in this case. An important ingredient of this result is a variation of Faugure_s Grabner basis algorithm F4, which significantly speeds up the relation computation. We show how this index calculus also applies to oracle-assisted resolutions of the static Diffi&Hellman problem on these elliptic curves.
Publish Year: 2013
Journal of Cryptography - Journal of Springer
زمینه: رمزنگاری خم بیضوی
حامی دانش بومی ایرانیان