IEICE TRANS. FUNDAMENTALS, VOL. TO APPEAR, NO. 9 SEPTEMBER 2000

1

PAPER

Gaudry’s variant against Cab curves
Seigo ARITA† , Member

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 intime O(q 2+² ). 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 byGaudry’s variant.
key words: discrete logarithm, hyperelliptic curve, superelliptic
curve, Cab curve

1.

Introduction

Gaudry[7] has described a new algorithm (Gaudry’s
variant) for the discrete logarithm problem (DLP) in
hyperelliptic curves. Gaudry’s variant uses the method
for Pollard’s rho algorithm [12] with the function fieldsieving algorithm of Adleman,DeMarrais, and Huang[1]. Gaudry’s variant solves the DLP in a hyperelliptic curve of a genus g defined on a finite field Fq intime O(q 2+² ) when the genus g is sufficiently small incomparison to the order q of the definition field.
Arita[3] and Galbraith et al.[6] described addition
algorithms on the Jacobian group of Cab and superelliptic curves respectively, and demonstrated algorithm
applications in discrete-log-based public key cryptosystems. This paper shows that Cab and superelliptic
curves can be attacked by a modified Gaudry’s variant
and presents timing results from the attack.
With hyperelliptic or Cab curve cryptosystems, one
usually selects a curve of a sufficiently large genus sothat definition fields are less than one word in size tohasten computations [3], [14]. Gaudry’s variant has excluded out this conventional hastening method. However, Gaudry’s variant cannot be effective in all of the
non-elliptic algebraic curve cryptosystems. This paper
also provides an example of a Cab curve that is unassailable by Gaudry’s variant.
2.

Gaudry’s variant

Take a hyperelliptic curve C : y 2 = x2g+1 + a1 x2g +· · · a2g+1 of genus g defined on a finite filed Fq . SupManuscript received
Manuscript revised†
The author is with NEC Co.,Kawasaki-shi,216 Japan.

pose its genus g is sufficiently small in comparison tothe order q of the definition field. Let JC denote theJacobian group of the hyperelliptic curve C. To handle
with the DLP, we look for an integer λ that satisfies
D2 = λD1 for two elements D1 and D2 in JC .
In Pollard’s rho algorithm, we calculate random
linear sums Ri = αi D1 + βi D2 (i = 1, 2, · · ·) of D1 andD2 step by step through a random walk, and wait for acollision Ri = Rj . Once it occurs, from αi D1 + βi D2 =αj D1 + βj D2 , we get λ = (αi − αj )/(βj − βi ).
In Gaudry’s variant[7], just as in the case of rho
algorithm, we calculate random linear sums Ri =αi D1 + βi D2 (i = 1, 2, · · ·) of D1 and D2 . However,
we gather smooth Ri value’s instead of waiting for acollision. An element D in JC is called smooth when
D is a sum of Fq rational points on C. Let all of theFq rational points on C be {P1 , P2 , ..., Pw },where thenumber w is approximately equal to q. Then, every
smooth Ri corresponds to a w-dimensional vector
Mi =P(mi,1 , · · · , mi,w ) through the relation Ri = k mi,k Pk .
Using the polynomial expression Ri = [ui (x), vi (x)]from Cantor’s algorithm [4], Ri is smooth if and only ifthelinear productQ polynomial ui (x) is factored into the P
(x−c
)
over
F
,
and
then
we
get
R
=
k
q
i
k (ck , v(ck )).
kTherefore, by calculating all of the Fq rational points{P1 , P2 , · · · , Pw } in advance at a complexity of O(q),the vector Mi is easily obtained.
When g is sufficiently small in comparison to q,
about 1/g! of all of the elements in JC are smooth([7]Prop.4). So, we obtain w0 ( >= w) smooth Ri values
after g!·w0 steps. w0 vectors Mi = (mi,1 , · · · , mi,w ) (i =1, · · · , w0 ) must be linearly dependent. By solving thew-dimensional linear equation, we obtain values forγi (i = 1, · · · , w0 ) satisfying
0w
X

γi Mi = 0.

i=1ThesePvalues for γi produce λ through the equation
Ri = k mi,k Pk ;XXλ=−γi αi /
γi β i .
i

i

In Gaudry’s variant, the most complex
step is solvP
ing the w-dimensional linear equation i γi Mi = 0 (i =1, 2, · · · , w0 ). The matrix (mi,k ) has a size equal toIEICE TRANS. FUNDAMENTALS, VOL. TO APPEAR, NO. 9 SEPTEMBER 2000

2

about q × q and is sparse since there are only g nonzero elements in each row. So the linear equation can besolved in q 2 steps. Hence, the complexity of Gaudry’s
variant is O(q 2 logγ (q)) for some constant γ, so it isO(q 2+² ).
When C has a non-trivial automorphism φ,
Gaudry’s variant becomes more powerful. Let m denote the order of φ. In this case, all of the Fq rational
points are unnecessary. Only the representatives of orbits in Fq rational points for the action of φ are needed.
The number of the orbits is q/m, so the complexity of
Gaudry’s variant becomes O((q/m)2+² ).
However,
Theorem 1: [2] The order of the automorphismgroup of a smooth algebraic curve of genus >= 2 is at
most 84(g − 1).
So, the effect of automorphisms can be ignoredby expanding the size of the definition field withlog2 (84(g − 1)) more bits.

In the tables, “simple” denotes a Cab curve with aequation of the form Y a + αX b + β, and “random” denotes a randomly chosen Cab curve. “Sum”, “double”,
and “scalar” denote addition, doubling, and scalar multiplication of random elements, respectively.
A superelliptic curve is a nonsingular affine curveof the equation

3.

We modify Gaudry’s variant to apply it to Cab curves.
The problems we encounter are how to decide if a given
element in a Jacobian group is smooth or not, and, if
it is, how to represent it as a sum of Fq rational points.
Note that about 1/g! of all of the elements in JC aresmooth when g is sufficiently small just as in the caseof hyperelliptic curves (See the proof of [7]Prop.4).
For example, take a C37 curve. The genus is six.
An element R in the Jacobian group of C37 curve isexpressed as an ideal of the coordinate ring. The ideal
has the following form of Gröbner basis with respect to
the C37 order [3]:Cab and superelliptic curves

A Cab curve is a nonsingular affine curve with the equationXαi,j xi y j = 0,
0<
= i<
=b,0<
=j <
=a,ai+bj <=abwhere both αb,0 and α0,a are not equal to zero [10].
Arita[3] described an addition algorithm for the Jacobian group of a Cab curve in terms of ideals of the coordinate ring, aiming at cryptosystems using Cab curves.
For a Cab curve with 160 bits of a Jacobian group, timing results from the addition algorithm are listed inTables 1,2, and 3.
Table 1
Performance for the C35 curve in ms at 266 MHz,
using a Pentium II chip.
sum
doublescalarsimple
3.39
3.76
862

random
3.65
4.21
958

Table 2
Performance for the C37 curve in ms at 266 MHz,
using a Pentium II chip.
sum
doublescalarsimple
1.15
1.15
273

random
1.24
1.28
300

Table 3
Performance for the C2,13 curve in ms at 266 MHz,
using a Pentium II chip.
sum
doublescalarsimple
0.70
0.65
158

random
0.73
0.68
167

y n = aδ xδ + · · · + a0 ,where n is prime to the characteristics of the definition
field, and n and δ are prime to each other [6]. Galbraith et al.[6] described an addition algorithm in the
Jacobian group of a superelliptic curve in terms of lattice computations.
Given these definitions, Cab curves clearly include
superelliptic curves. Only Cab curves will be examined.
4.

Application
Cab curvesofGaudry’svarianttoR = {a0 + a1 x + a2 x2 + a3 y + a4 x3 + a5 xy + x4 ,b0 + b1 x + b2 x2 + b3 y + b4 x3 + b5 xy + x2 y,
c0 + c1 x + c2 x2 + c3 y + c4 x3 + c5 xy + x2 y}.
Here, ai , bi , and ci are elements in the definition field.
The common zeroes of these three equations are six
points on the C37 curve, that comprise R.
When the definition field Fq is large enough, thesix points comprising R have distinct x-coordinates toeach other for almost any R in the Jacobian group. So,
almost any R can be expressed as common zeroes of
two polynomials:
R = {sixth degree polynomial of x,y + (fifth degree polynomial of x)},just as in the case of hyperelliptic curves. The expression is nothing but the Gröbner basis of (the ideal corresponding to) R with respect to the lexicographic order.
Therefore, in Gaudry’s variant against Cab curves,for almost any Ri , the decision regarding the Ri value’ssmoothness and representation as a sum of Fq rational points follows the same pattern as for hyperelliptic
curves, after translating the Gröbner basis of Ri w.r.t.

ARITA: GAUDRY’S VARIANT AGAINST Cab CURVES

3

Cab order to another Gröbner basis w.r.t. lexicographic
order. It is well known that Gröbner bases can be effectively translated between distinct monomial orders.
Note that if exceptional values for Ri are found, we
can simply discard them. Thus, now we know that
Gaudry’s variant can also be applied to Cab curves.

Collection of rational points (PARI-GP)
5 m 13 s
Collection of smooth elements (C)2 h 33 m 6 s
Solving linear equation (C)32 m 2 s
Total
3 h 11 m 21 s
Table 5
Timing results of modified Gaudry’s variant against
the C37 curve from Table 4 using a 266-MHz Pentium II chip.

finite field
F84211
defining equation
1 + 24740x7 + 32427y 3 = 0
genus
6order of Jacobian
43 · 8068970623016239605318986617
order of automorphism
3·7
Table 4 93 bits of a C37 curve over 17 bits of a prime field5.

We implemented the modified Gaudry’s variant
with C language and the PARI-GP [11], and then tested
it against the C37 curve in Table 4. The curve has 93
bits of a Jacobian group over 17 bits of a prime field.
Let ζ3 and ζ7 denote the primitive third and the seventh root of unity, respectively. Since the curve has
the automorphism φ(x, y) = (ζ7 x, ζ3 y) of order 21, thenumber of the orbits of φ on the rational points shouldbe 84211/21 = 4010. · · · or more. We needed to collect4011 or more smooth elements and then solve about
4011 dimensional sparse linear equations. For solving
these linear equations, we also used the Lanczos algorithm [9].
Two elements D1 and D2 in the Jacobian groupwere randomly generated:
D1 = {x4 + 77465x3 + 75875x2 + (37117y + 57992)x+ (42876y + 21588),
5485x3 + (y + 79222)x2 + (4298y + 50456)x+ (36882y + 81869),
41971x3 + 64608x2 + (26263y + 16207)x+ (y 2 + 42778y + 62216)},
D2 = {x4 + 64296x3 + 44620x2 + (29434y + 15779)x+ (61013y + 42557),
51156x3 + (y + 32172)x2 + (62401y + 22153)x+ (78055y + 13056),
79116x3 + 5028x2 + (69977y + 21979)x+ (y 2 + 75761y + 2009)}.
Then, running the modified Gaudry’s variant, we
obtained
λ = 4082271804134874346983670415
for D2 = λD1 in the time given in Table 5. The average and variance of the number of steps needed to
produce a smooth element were 848.265 and 680786,
respectively, reasonable results compared to Gaudry’s
theoretical estimate 1/6! = 1/720 of the probability for
an element to be smooth[7].

Cab curves that are unassailable by Gaudry’s
variant

Let a and b be distinct prime numbers. Let C(p, α, β)(=C(p, a, b, α, β)) denote a Cab curve over a prime field Fp
with the equation
αY a + βX b + 1 = 0.
In this section, we will construct a Cab curve C(p, α, β)of a small genus, that is secure against Gaudry’s variant. Let h be the order of the Jacobian group ofC(p, α, β). Conditions for security are:Condition 1 The order h has 160 or more bits ofprime factor l [12],Condition 2 l does not divide pk − 1 for small valuesof k [5],Condition 3 l is not equal to p [13], andCondition 4 p has (40 + log2 (84(g − 1))) or more bits.
The fourth condition secures a curve against Gaudry’s
variant (Theorem 1). Because we are handling a curvewith a small genus, we do not need to consider Adleman,DeMarrais,and Huang’s algorithm [1] or its extension to superelliptic curves [6].
Koblitz[8] used Jacobi sums to calculate the orderof Jacobian groups of hyperelliptic curves. Jacobi sums
can also be used for a curve C(p, α, β). For simplicity,p ≡ 1 (mod lcm(a, b)) has been assumed.
Fix the generator w of the multiplicative group Fp∗ .
For a rational number s such that (p − 1)s is an integer,character χs of Fp∗ is defined by
χs (w) = e2πis .
Extend χs to the whole Fp by setting χs (0) = 0 whens is not an integer and setting χs (0) = 1 when it is.
For integers l = 1, 2, . . . , a−1 and m = 1, 2, . . . , b−
1,X
jp (l, m) =χl/a (v1 )χm/b (v2 )(1)
1+v1 +v2 =0

is called a Jacobi sum. Here, v1 and v2 run over Fp
under the condition 1 + v1 + v2 = 0.
Weil[16] has demonstrated that the L-polynomial
Lp (U ) of C(p, α, β) can be expressed by Jacobi sums:

IEICE TRANS. FUNDAMENTALS, VOL. TO APPEAR, NO. 9 SEPTEMBER 2000

4Y

Lp (U ) =(1 + χl/a (α)χm/b (β)jp (l, m)U ),

l=1,2,...,a−1
m=1,2,...,b−1

where χs denotes the complex conjugate of χs .
Generally, the order of a Jacobian group of a curveis equal to the value of the L-polynomial L(U ) of thecurve at U = 1 [15], so the order h of the Jacobiangroup of C(p, α, β) is given by
h = Lp (1)Y=(2)(1 + χl/a (α)χm/b (β)jp (l, m))= NormQ(ζ)|Q (1 + χ1/a (α)χ1/b (β)jp (1, 1))
Thus, to know the order h of the Jacobian group,
it is sufficient to know the values of the Jacobi sumsjp (l, m). However, direct computation of those values
using the formula (1) are infeasible from the computational point of view. We use the Stickelberger element
to know the values of the Jacobi sums jp (l, m).
Let [λ] denote the largest integer under the rational
number λ, and < λ > denote λ−[λ]. Take a cyclotomic
field Q(ζ) with a primitive ab-th root ζ of unity. Let
σt denote the Galois map ζ 7→ ζ t of Q(ζ). An element
ω(a, b) in the group ring Z[Gal(Q(ζ)|Q)] defined by
X
t

[<

t
t
−1
> + < >]σ−t
,
a
b

(3)

where t runs over reduced residue classes mod ab, iscalled a Stickelberger element. As an ideal of Q(ζ), it
is known that(jp (l, m)) = P ω(a,b) ,(4)

where P denotes a prime ideal of Q(ζ) lying over p [17].
Suppose that the prime ideal P is principal:
P = (γ).
Then, we have(jp (l, m)) = (γ ω(a,b) ).

(5)

From this, we know that jp (l, m) and γ ω(a,b) differ by
the product of some unit of Q(ζ). Moreover, jp (l, m)and γ ω(a,b) has the same absolute value p1/2 in any embedding into the complex number field [17]. So, jp (l, m)and γ ω(a,b) differ only by the power of −ζ. Now we seethat Equation (5) can be used to determine jp (l, m) up
to the power of −ζ by knowing the prime p and theprincipal prime ideal P = (γ) in advance.
We arrive at the following algorithms:
Algorithm 1 (Search for a secure C(p, α, β)):Input: a, b
Output: p, α, β, and the order h of the Jacobian group
1. g ← (a − 1)(b − 1)/2

3. Search the candidate j for the value of a Jacobi
sum for some prime p of m or more bits by using
Algorithm 2:(p, j) ← Algorithm2(m).
4. For every k = 0, 1, . . . , ab − 1,hk ← NormQ(ζ)|Q (1 + (−ζ)k j).

l=1,2,...,a−1
m=1,2,...,b−1

ω(a, b) =2. m ← M ax(d160/ge, d40 + log2 (84(g − 1))e)dne denotes the least integer over n.

5. Check that there is a value hk that satisfies
Conditions 1,2, and 3 for security in the set{h0 , h1 , . . . , hab−1 }. If there is not, go to step 3.
If it does, h ← hk .
6. Let ζa and ζb denote the primitive a-th and b-throot of unity modulo p, respectively. For every hk
obtained at step 5, do as follows. For every l =0, 1, · · · , a − 1 and m = 0, 1, · · · , b − 1, check if theorder of the Jacobian group of C(p, ζal , ζbm ) is equal
to h or not; for example, check if h times the random element is equal to the unit element, or not.
If the order is equal, output p, α = ζa l , β = ζb m ,and h. If there is no such l and m, go to step 3.
As per step 2, p has 40 + log2 (84(g − 1)) or more
bits, so the curve obtained by Algorithm 1 is secureagainst Gaudry’s variant. At step 6, we check only thenecessary condition for the group order to be h. So
strictly the order may be different from h. But, thetest at step 6 ensures that the order has the same large
prime factor l as the one of h. This is sufficient for our
purpose.
Algorithm 2, contained in Algorithm 1, makes useof Equation (3) and (5) for the Stickelberger element tofind the candidate value of the Jacobi sum.
Algorithm 2 (Finding the candidate of the Jacobi sum):
Input: m
Output: pPand j−1
1. ω ← t [< at > + < bt >]σ−t
2. Randomly generateP(a−1)(b−1)−1 l
cl ζ (−20 <γ0 = l=0= 20).
= cl <
3. For every i = 1, 2, . . .,γ ← γ0 + i
p ← NormQ(ζ)|Q (γ)
If p < 2m , then try the next i.
If p >> 2m , then go to step 2.
‘>>’ means ‘sufficiently larger than.’If p is not prime, then try the next i.
4. j ← γ ωOutput p and j.

ARITA: GAUDRY’S VARIANT AGAINST Cab CURVES

5Note that p obtained by Algorithm 2 satisfies thecondition p ≡ 1(mod lcm(a, b)), because the prime ideal(γ) has the residue degree one over the prime p.
Experimentally, we observed that numbers of repeating steps 2 and 3 depends heavily on the range ofcl at step 2. We take the range −20 <= cl <= 20, so that
Algorithm 2 stops after repeating steps 2 and 3 for several times, for the input m of the size used in the realworld.
Example6. Forα=579364850535396
and β = 289406374935593, it is verified that theorder of the Jacobian group of C(p, α, β) is equal
to h.
Thus, a C35 curve is obtained with
579364850535396y 3 + 289406374935593x5 + 1 = 0
over the prime field GF(581929936583251) with the Jacobian group of the order2511 · 456705293264421778523592
02972228519045793876036569858671,

Algorithm 1 was run for a = 3 and b = 5.
1. g ← (3 − 1)(5 − 1)/2 = 4

which is secure against Gaudry’s variant.

2. m ← max(160/4, d40 + log2 (84 · 3)e) = 48
3. Run Algorithm 2 for m = 48.
P−1
a. ω ← t [< 3t > + < 5t >]σ−t= σ1 + σ7 +σ11 + σ13b. γ0 ← 20 − 3ζ − 12ζ 2 + 20ζ 3 − 11ζ 4 − 4ζ 5 +3ζ 6 − 16ζ 7 was randomly generated.
For γ ← γ0 + 60 = 80 − 3ζ − 12ζ 2 + 20ζ 3 −11ζ 4 − 4ζ 5 + 3ζ 6 − 16ζ 7 ,p ← Norm(γ) = 581929936583251 is a primeof 50 bits. Now, the candidate value j of theJacobi sum for p isj ← γγ (7) γ (11) γ (13)= 18682331 + 1900434ζ + 3903200ζ 2+ 735220ζ 3 + 2683534ζ 4 − 6028054ζ 5− 1372490ζ 6 + 3103044ζ 7
4. For every k = 0, 1, . . . , 29, compute hk
Norm(1 + (−ζ)k j):←h0 ← 1146786729413035548075542797106
71283827257404103736047882496···
h6 ← 1146786991386963085872739586632
65811323988422727826915122881···
h29 ← 1146787464216129098443264922470
07547650638094985955354652416
5. h6 satisfies Condition 1,2 and 3. In fact,h ← h6 = 2511 · l
Here,l = 456705293264421778523592
02972228519045793876036569858671
is a prime of 185 bits, distinct from p. Condition
2 is satisfied for k <= 1000.

6.

Conclusion

We demonstrated that Cab and superelliptic curves canbe attacked by a modified Gaudry’s variant, and reported timing results for the attack.
However, Gaudry’s variant cannot be effective inall of the non-elliptic algebraic curve cryptosystems.
We provided an example of a C35 curve that is unassailable by Gaudry’s variant.
References[1] L.M.Adleman,J.DeMarrais, and M.D.Huang, “A Subexponential Algorithm for Discrete Logarithms over the Rational Subgroup of the Jacobians of Large Genus Hyperelliptic Curves over Finite Fields,” ANTS-I, LNCS 877, pp.2840,Springer, 1994.
[2] E.Arbarello, M.Cornalba, P.A.Griffiths, and J.Harris, “Geometry of Algebraic Curves Volume I,” Springer-Verlag,
1984.
[3] S. Arita, “Algorithms for computations in Jacobian group of
Cab curve and their application to discrete-log-based public key cryptosystems,” Conference on The Mathematics of
Public Key Cryptography, Toronto, 1999.
[4] D.G.Cantor, “Computing in the Jacobian of a hyperelliptic curve,” Mathematics of Computation, 48(177), pp.95101,1987.
[5] G.Frey and H.-G.Rück, “A remark concerning m-divisibility
and the discrete logarithm in the divisor class group of
curves,” Math. Comp.,62(206),pp.865-874,1994.
[6] S.D.Galbraith, S.Paulus, and N.P.Smart “Arithmetic on
Superelliptic Curves,” preprint,1999.
[7] P.Gaudry, “A variant of the Adleman-DeMarris-Huang algorithm and its application to small genera,” Conferenceon The Mathematics of Public Key Cryptography, Toronto,
1999.
[8] N.Koblitz, “A very easy way to generate curves overprime fields for hyperelliptic cryptosystems,” Rump-session
Crypto’97, 1997.
[9] B.A.LaMacchia and A.M.Odlyzko, “Solving large sparselinear systems over finite fields,” Crypto ’90, LNCS 537,
pp.109-133,Springer, 1990.
[10] S. Miura, “Linear Codes on Affine Algebraic Curves,”
Transactions of IEICE, Vol. J81-A, No 10, pp.13981421,1998.
[11] PARI-GP, ftp://megrez.math.u-bordeaux.fr/pub/pari

IEICE TRANS. FUNDAMENTALS, VOL. TO APPEAR, NO. 9 SEPTEMBER 2000

6[12] J.M.Pollard, “Monte Carlo methods for index computation
mod p,” Math. Comp.,32(143),pp.918-924,1978.
[13] H.-G.Rück, “On the discrete logarithm in the divisor classgroup of curves,” Math. Comp.,68(226),pp.805-806,1999.
[14] Y.Sakai and K.Sakurai, “Design of hyperelliptic cryptosystems in small characteristic and a software implementation
over F2n ,” Asiacrypt ’98, Advances in Cryptology, LNCS
1514, pp.80-94,Springer, 1998.
[15] H.Stichtenoth, “Algebraic Function Fields and Codes”,
Springer-Verlag, 1993.
[16] A.Weil “Numbers of solutions of equations in finite fields,”
Bull.Amer.Math.Soc.,55,pp.497-508,1949.
[17] A.Weil“JacobiSums
as“Grössencharaktere”,”
Trans.Amer.Math.Soc.,73,pp.487-495,1952.

Seigo Arita
Since 1990, he has beenwith C&C Media Research Laboratories,
NEC. He is a member of IEICE and JMS.