Gaudry's Variant against Cab Curves

Seigo ARITA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.9   pp.1809-1814
Publication Date: 2000/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
Keyword: 
discrete logarithm,  hyperelliptic curve,  superelliptic curve,  Cab curve,  

Full Text: PDF>>
Buy this Article




Summary: 
Gaudry has described a new algorithm (Gaudry's variant) for the discrete logarithm problem (DLP) in hyperelliptic curves. For a hyperelliptic curve of a small genus on a finite field GF(q), Gaudry's variant solves for the DLP in time O(q2+ε). This paper shows that Cab curves can be attacked with a modified form of Gaudry's variant and presents the timing results of such attack. However, Gaudry's variant cannot be effective in all of the Cab curve cryptosystems. This paper also provides an example of a Cab curve that is unassailable by Gaudry's variant.