Elliptic Curve Discrete Logarithm Problem over Small Degree Ext

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

زمینه: رمزنگاری خم بیضوی

لینک مشاهده صفحه اول مقاله

لینک دانلود مقاله

ایران سای – مرجع علمی فنی مهندسی

حامی دانش بومی ایرانیان