Security of Cryptosystems Based on Class Groups ofImaginary Quadratic Orders
Safuat Hamdy

Bodo Möller

Fachbereich Informatik, TU Darmstadt{hamdy,moeller}@cdc.informatik.tu-darmstadt.deMay 29, 2000

Abstract
In this work we investigate the diculty of the discrete logarithm problem in classgroups of imaginary quadratic orders. In particular, we discuss several strategies to compute discrete logarithms in those class groups. Based on heuristic reasoning, we give advice
for selecting the cryptographic parameter, i.e. the discriminant, such that cryptosystems
based on class groups of imaginary quadratic orders would oer a similar security as
commonly used cryptosystems.

1

Introduction

Cryptosystems based on class groups of imaginary quadratic orders (IQC) have been rstproposed by Buchmann and Williams [3, 4] in 1988 and 1990. Since then, there was no clear
advice on how to select the cryptographic parameter, i.e. the discriminant of the quadraticorder. The goal of this work is to close this gap. In particular, we demonstrate how large∆

must be selected such that computing logarithms in Cl (∆) is as hard as factoring an integer

n of given size. We consider several strategies to compute discrete logarithms in class groups,
such as reductions to other computational problems, index-calculus algorithms, Pollard's λalgorithm, and the Pohlig-Hellman algorithm in connection with an algorithm similar to the(p − 1)-factoring method. In particular, in order to get the same security with IQC as with
RSA with 1024 bit moduli, the discriminant should have at least 687 bits.
The security of IQC is based on the apparent diculty of computing discrete logarithms
in class groups of imaginary quadratic orders (Cl-DLP). The Cl-DLP can be extended to classgroups of orders of number elds with arbitrarily high degree, and in furthermore, there is a
generalization of the discrete logarithm problem [2]. However, in this work we shall focus only
on imaginary quadratic elds, and whenever the term class groups appears in the sequel, we
actually mean class groups of imaginary quadratic orders.
It is well known that solving the Cl-DLP is at least as hard as solving the integer factorization problem (IFP, we shall describe the reduction later in this work), yet it is still
unknown whether the Cl-DLP is really harder than the IFP. The Cl-DLP can be solved with

2

Security of Cryptosystems Based on Class Groups

a subexponential index-calculus algorithm due to Hafner and McCurley [11]. This algorithm
was improved by Düllmann [9]. Recently, in [28] it has been rigorously proven that for solving
the Cl-DLP one can expect a running time proportional to L|∆|

1 3√
2 , 4 2 + o(1) , where ∆ isthe discriminant of the imaginary quadratic order. Moreover, Jacobson [15] has applied theideas of the MPQS to class group computations. In fact, the machinery behind his algorithm

is the same as that of the original MPQS, and although his algorithm hasn't been analyzed,
empirical data suggest a running time proportional to L|∆|

1

2 , 1 + o(1) .

The best known algorithm to solve the IFP is the GNFS with asymptotic expected running
time proportional to Lnhq i

1 3 643,
9 ; the best known algorithm to solve the GF-DLP (DLP in

multiplicative groups of Galois elds) is a variant of the GNFS with the same asymptotic
expected running time. Thus, currently the IFP or the GF-DLP can be solved asymptoticallyfaster than the Cl-DLP. This means that the Cl-DLP is apparently harder than the IFP or
the GF-DLP.
Hence class groups form another potential alternative to nite elds for DL-based cryptographic protocols. Unfortunately, popular signature protocols such as DSA can't be usedwith class groups in a direct way, because DSA requires the knowledge of the group order.
Computing the order of an arbitrary class group appears to be as hard as computing discrete
logarithms in class groups, because there's no ecient algorithm known that computes theclass number. In [21] a variant of the Schnorr signature scheme that doesn't require knowledgeof the group order has been proposed.
Computing roots without knowing the class number also appears to be intractable. This
makes the Guillou-Quisquater signature protocol [10] suitable for class groups, since in thisprotocol even the signer does not need to know the class number. Moreover, in [1] a variantof DSA was presented that is based on the intractability to compute roots in nite abeliangroups.
This paper is organized as follows: In Section 2 we recall the background we need, and in
Section 3 we give advice for selecting the security parameters.

2

Class groups

Recall that we consider class groups of imaginary quadratic elds only. We shall state only

∆ be a negative
integer such that ∆ ≡ 0, 1 (mod 4). Then ∆ is the discriminant of a unique order O∆ =√√Z + Z(∆ + ∆)/2 of Q( ∆). O∆ is maximal if and only if ∆ is fundamental, i.e. ∆ or ∆/4
is square free if ∆ ≡ 1 (mod 4) or ∆ ≡ 0 (mod 4), respectively.

some necessary facts without proofs; for details we refer to [8, 5].

Let O∆ be any (not necessarily maximal) order.

Let

The class group ofO∆ is denoted byCl (∆), its elements are equivalence classes of invertible ideals of O∆ . The group order ofCl (∆) is the class number h(∆). Later in this work we shall need the odd parts of classgroups. We denote the odd part of a class group Cl (∆) by Cl odd (∆) and its cardinality by
hodd (∆).
√
Any ideal of O∆ can be expressed as Za + Z(b +∆)/2 such that a, b ∈ Z, a > 0 and
2
4a | (b − ∆), that is, such that there exists a positive integer c such that ∆ = b2 − 4ac. Thus
we represent ideals as pairs (a, b) of integers. Observe that if b = 0 or b = a, then ∆ = −4ac

3 Selecting the class group3or ∆ = a(a − 4c), respectively, and if a = c, then ∆ = (b − 2a)(b + 2a). Such ideals are called

ambiguous and have order two in Cl (∆).

reduced if gcd(a, b, c) = 1, −a < b ≤ a ≤ c, and b ≥ 0 if a =c. Each equivalence class of O∆ contains exactly one reduced ideal, thus the elements ofCl (∆) can be represented by the reduced ideals of O∆ , and checking equality of two idealclasses means to compare the representatives. The neutral element of Cl (∆) is represented by(1, ∆ mod 2). The group operation of Cl (∆) is ideal multiplication with reduction (e.g. see [15]2or [5, Chap. 5]). It can be shown that a group operation requires O(log |∆|) bit operations.
The inverse of an ideal (a, b) under this operation is (a, −b). If an ideal (a, b) is reduced, thenppa < |∆|/3, therefore a, |b| = O( |∆|).
An ideal is said to be

3

Selecting the class group

In this section we shall see that the discriminant is the cryptographic parameter. We shalldiscuss how to select a discriminant such that, based on heuristic grounds, computing discrete
logarithms or the order of arbitrary elements in the corresponding class group is intractable.
In particular,• ∆ must be chosen so that there is no ecient reduction of the CL-DLP to simpler
problems,• |∆| must be large enough to preclude attacks with index-calculus algorithms,• h(∆) must be large enough to preclude attacks with λ algorithms,• h(∆) must not be smooth in order to preclude the computation of h(∆) by an algorithm
similar to the (p − 1)-factoring algorithm with subsequent application of the PohligHellman algorithm.
It is tempting to ask whether the discriminant can be chosen such that its class number
has properties selected à priori. However, we have no control over the class number, i.e. there's
not even a probabilistic ecient algorithm known which outputs a fundamental discriminant
whose class number has certain interesting properties (e.g. contains a large prime factor).
We shall show in the following subsections that if∆ is chosen appropriately, then theabove conditions hold with high probability. In particular, in Sect. 3.1 we show that selecting∆ = −p or ∆ = −8pq where p, q are primes precludes reductions to the GF-DLP and keeps
the two-part of Cl (∆) small. In Sect. 3.2 we show how large ∆ must be to preclude indexcalculus attacks. In Sect. 3.3 we show how large the class group must be to preclude attacks
with the aid of Pollard's λ-method; based on the Brauer-Siegel theorem we deduce the size ofthe discriminant. In Sect. 3.4 we describe the relevance of the Pohlig-Hellman algorithm forclass groups and discuss a possible application in conjunction with another algorithm, which
is similar to the (p − 1)-factoring method. Let a smoothness bound B be given; in Sect. 3.5,
based on heuristic assumptions we show how∆ must be chosen so that the class number is

B -smooth only with negligible probability.
It turns out that asymptotically the index-calculus methods dominate the selection of thediscriminant with respect to order of magnitude. Moreover, since the best known algorithm

4Security of Cryptosystems Based on Class Groups

to compute class numbers of fundamental discriminants are again index-calculus methods,
it is infeasible to compute the class number of fundamental discriminants if these are large.
Therefore, the Pohlig-Hellman algorithm plays no role for class groups of maximal orders,
unless the class number is smooth, because then an algorithm similar to the(p − 1)-factoringalgorithm can be applied to compute the class number.

3.1

Class group computation by reduction to other problems∆ be a negative fundamental discriminant and let f be a positive integer.
∆ 6= −3, −4Let2h(∆f ) = h(∆)f

Y

1−

p|f

∆
p

 
1
,
p

h(−8) = 1 and h(−8p2 ) = p −Since in general it is intractable to compute class numbers of large fundamental

where (∆/p) denotes the Kronecker symbol.

(−8/p).



Then, if

For instancediscriminants (see below), this could be a nice way to avoid it altogether.

2

However, the Cl-DLP in Cl (−8p ) can be reduced in polynomial time to the GF-DLP in Fp[13]. Currently no ecient reductions of this type for maximal orders are known, therefore weshall use only class groups of maximal orders, and in the sequel ∆ will always be fundamental
and thus O∆ will be maximal.

3.1.1

Selection of a fundamental discriminant

In order to check whether an arbitrary discriminant∆ is fundamental, it must be checked

whether ∆ (if ∆ ≡ 1 (mod 4)) or ∆/4 (if ∆ ≡ 0 (mod 4)) is square free. This can be achieved
by factoring the discriminant, but this is infeasible if the discriminant under consideration is
A better method is to construct D from distinct prime factors, and set ∆ = −D if
D ≡ 3 (mod 4) and ∆ = −4D otherwise.
large.

Some of the simplest cases are

1.

∆ = −p where p ≡ 3 (mod 4) is prime; and2.

∆ = −8pq where p and q are primes such that p ≡ 1 (mod 8), p + q ≡ 8 (mod 16), and(p/q) = −1, where (p/q) denotes the Legendre symbol.

Discriminants selected like this have the additional advantage that the two-part of the classnumber is known to be small: In case 1,h(∆) is odd; in case 2, the even part of h(∆) is0

exactly 8 (see [16, Proposition B 9 ]).
Observe that ∆ = −8pq is attractive by a complexity theoretic argument, because if∆ is composite, then Cl (∆) has non-trivial ambiguous elements, whose components lead
immediately to a factorization of ∆; these ambiguous elements can be obtained by computing
discrete logarithms in Cl (∆), therefore IFP ≤ Cl-DLP.

3.2

Class group computations by index-calculus techniques

3.2

Class group computations by index-calculus techniques

5

Let Lx [e, c] be dened as usual, that isdef

Lx [e, c] = exp c(log x)e (log log x)1−e

for real positive x, real positive c, and 0 ≤ e ≤ 1. In practice, instead of the term Lx [e, c] we
often see Lx [e, c + o(1)], but in the sequel we shall ignore the o(1) term.
We want to compare the expected computational work for solving the IFP and the ClDLP. In the following, we assume the expected running time for factoring an integer

h

n by

q i

Ln 13 , 3 64
9 . For the Cl-DLP, an expected running time
1 3√ proportional to L|∆|2 , 4 2 has been shown in [28]. However, Jacobson [15] showed that
one can use a variant of the MPQS for DL-computations in Cl (∆). The MPQS factoring1 algorithm has a conjectured expected running time proportional to Ln
2 , 1 , while the MPQS

the GNFS to be proportional to

DL-computation algorithm hasn't been analyzed, yet (not even heuristically). Empirical datasuggests an expected running time ofrunning time.

L|∆|

1


,
1
, so we shall base our arguments on this2

In terms of security and eciency, this will yield slightly larger keys: If weunderestimate the running time of the Cl-MPQS, we overestimate the size of the security
relevant parameters. This conservative approach is quite common practice.
The usual approach to estimate running times of an algorithm for large input parameters
is to start from the empirical running time for smaller input parameters.

If

x1 and x2 are

inputs for an algorithm with expected running time Lx [e, c] and t1 is the running time of thealgorithm when executed with x1 , then (see [20] or [17]) the running time t2 of the algorithmwith input x2 can be estimated by the equation

Lx1 [e, c]
t1
=
.
(1)
Lx2 [e, c]t2
However, this holds only if the sizes of x1 and x2 do not dier too much, otherwise it can'tbe ignored that o(1) → 0. Thus, if x2 is much larger than x1 , then t2 will be a signicantoverestimate. To obtain more precise estimates a ner expression for the running time must
be used or the o(1) term must be taken into account by modifying (1) as in [12]. We stick to(1), since the estimates presented here dier only slightly from those given in [12].
magnitude of

expected no. of MIPS-yearsnto factor n

2512
2768
21024
21280
21536
21792
22048
22560
23072
23584
24096

8.00 × 103
4.91 × 107
5.99 × 1010
2.68 × 1013
5.97 × 1015
7.91 × 1017
6.98 × 1019
2.16 × 1023
2.64 × 1026
1.63 × 1029
5.87 × 1031

Table 1: Estimated expected computational work of the GNFS for larger inputs

6

Security of Cryptosystems Based on Class Groups

Table 1 shows some extrapolated running times for the GNFS. They are based on data
points of the factorization of RSA-155 (155 decimal digits, 512 bits) with the GNFS [26]. In
particular, it was estimated that about 8000 MIPS-years were spent.
To estimate the expected running time of the MPQS for DL-computations in class groups
for large groups, we made extensive experiments where we computed discrete logarithms
in 20 class groups of dierent negative discriminants for each magnitude tabulated below.
The computations were carried out on a Sparc with ULTRA-170 processor. The results are
summarized in Table 2.
magnitude ofmean running time (sec)standard|∆|t∆deviation

2140
2142
2144
2146
2148
2150
2152
2154
2156
2158
2160
2162
2164
2166
2168
2170
2172
2174
2176
2178
2180
2184
2188
2192
2196
2200
2210
2220

8.59 × 101
1.29 × 102
1.36 × 102
1.32 × 102
1.98 × 102
2.20 × 102
2.63 × 102
3.26 × 102
3.52 × 102
4.90 × 102
4.41 × 102
7.67 × 102
6.84 × 102
8.79 × 102
1.07 × 103
1.49 × 103
1.74 × 103
1.54 × 103
1.61 × 103
2.77 × 103
2.73 × 103
3.37 × 103
4.07 × 103
5.96 × 103
9.23 × 103
1.30 × 104
2.63 × 104
6.28 × 104

3.58 × 101
8.66 × 101
5.32 × 101
3.87 × 101
6.98 × 101
1.38 × 102
1.44 × 102
1.82 × 102
1.64 × 102
3.28 × 102
1.98 × 102
4.21 × 102
2.20 × 102
3.22 × 102
4.12 × 102
8.25 × 102
8.99 × 102
9.83 × 102
8.45 × 102
1.37 × 103
1.39 × 103
1.82 × 103
1.95 × 103
2.86 × 103
3.80 × 103
5.13 × 103
8.49 × 103
3.78 × 104

L|∆|

1



2, 1

/ t∆ (sec−1 )1.65 × 107
1.31 × 107
1.50 × 107
1.85 × 107
1.47 × 107
1.59 × 107
1.59 × 107
1.53 × 107
1.69 × 107
1.44 × 107
1.90 × 107
1.30 × 107
1.73 × 107
1.60 × 107
1.56 × 107
1.33 × 107
1.34 × 107
1.79 × 107
2.03 × 107
1.39 × 107
1.67 × 107
1.87 × 107
2.14 × 107
2.02 × 107
1.79 × 107
1.74 × 107
1.87 × 107
1.68 × 107

Table 2: Empirical computational work of the Cl-MPQS for relatively small inputs

Table 2 supports the conjectured running time of L|∆|

1

2 , 1 for the MPQS. Note also thatthe standard deviation is almost always about half the running time.

This shows that the3.2

Class group computations by index-calculus techniques

7

running times are pretty spread, which in turn conrms our suspicions of taking just a single
sample.
All computations were performed on a SUN-workstation with a Sparc ULTRA-170 processor. SUN Microsystems does not publish MIPS ratings for its machines, and in fact, theunit MIPS-year is actually not appropriate [25]. However, it is widely used, so for simplicity
we assume 100 MIPS, which is a value of reasonable order of magnitude for this machine. By
Table 2 let us assume that L|∆|in Table 3.

,1/t∆ = 1.8 × 107 sec−1 . Then we get the extrapolations
2

1

When we align the parameters of the IFP and of the Cl-DLP in such a way that the
expected running time for solving the Cl-DLP roughly equals the expected running time forsolving the IFP for n of some particular magnitudes, we get Table 4.

magnitude of

expected no. of MIPS-years

|∆|
2256
2348
2512
2640
2768
2896
21024
21280
21536
21792
22048
22560
23072
23584
24096

for solving the Cl-DLP in Cl (∆)

2.58
9.75 × 103
1.18 × 107
6.74 × 109
2.24 × 1012
4.94 × 1014
7.79 × 1016
8.90 × 1020
4.56 × 1024
1.26 × 1028
2.13 × 1031
1.92 × 1037
5.30 × 1042
5.88 × 1047
3.15 × 1052

Table 3: Estimated expected computational work of the Cl-MPQS for larger inputs

magnitude of

n
2768
21024
21536
22048
23072
24096

|∆|
2540
2687
2958
21208
21665
22084

expected no. of MIPS-years

4.99 × 107
6.01 × 1010
5.95 × 1015
7.05 × 1019
2.65 × 1026
5.87 × 1031

Table 4: Estimated expected computational work of the GNFS and the Cl-MPQS aligned

8

Security of Cryptosystems Based on Class Groups

3.3

Class group computations by Pollard's

λ method

We now consider Pollard's λ method for computing discrete logarithms, orders of group elements and hence roots of group elements.

From [27] it is known that the unparallelizedpπ|G|/2 group operations (ignoring lower order terms) for
cyclic groups G. Moreover, r -fold parallelization speeds the λ-method up by factor r .

version of this algorithm takes

Cl odd (∆) is cyclic is
Cl odd (∆) is not
cyclic, then with high probability Cl odd (∆) has a cyclic subgroup Gcyc such that |Gcyc | has
the same order of magnitude as hodd (∆), and therefore, by our selection of ∆, the even partis 1 or 8 and thus |Gcyc | and h(∆) have the same order of magnitude.
By the heuristics of Cohen and Lenstra [7, 6], the probability that

equal to 0.9775 . . . . Moreover, it can be deduced from the heuristics that if

In order to provide a lower bound for ∆ we need an (asymptotic) lower bound for h(∆)
that depends on ∆ only. The best proven explicit lower bound is h(∆) > 1/55 ln |∆|Qp|∆ (1 −√2 p/(p + 1)) [5, Sect. 5.10.1], which is too weak for our purposes. By the Brauer-Siegel
p
p 1−
p 1+
Theorem we know that ln h(∆) ∼ ln|∆| as ∆ → −∞, that is, |∆|≤ h(∆) ≤ |∆|for any positive real  and suciently large ∆, but no explicit constants are known to makepthis statement eective. However, it is possible to show that h(∆) is on average c|∆| withc = 0.461559 . . . [5, Sect. 5.10.1]. This result has been proven for averages taken over classnumbers of fundamental discriminants. In this work we make the assumption that this result
is not aected by the restriction to the special discriminants given in section 3.1.1.

ExampleThe time to perform a single group operation in Cl (∆) depends on ∆, yet let us

assume a xed time of 1 ms on a machine with a computing power of 100 MIPS. Then thecomputational work of a single MIPS-year is equivalent to

229 group operations. Based on

this assumption and on the assumed average for the class number of a prime discriminant, inTable 5 we present some samples for (prime) discriminants, their average class number, andthe expected computing amount to compute discrete logarithms by the

λ-method; compare

this with Table 1.

magnitude of

h(∆)
2108
2129
2162
2189
2233
2268

expected no. of Group operations

|∆|
2218
2260
2326
2380
2468
2538

p

πh(∆)/2
254
264
281
294
2116
2134

expected no. of MIPS-years

4.56 × 107
6.60 × 1010
6.12 × 1015
7.09 × 1019
2.97 × 1026
5.51 × 1031

Table 5: Estimated expected computational work of the λ-method

3.4

Class group computations and the Pohlig-Hellman algorithm

The Pohlig-Hellman algorithm utilizes the prime factorization of the group order in order
to simplify DL computations.

However, the best known algorithm for computing the class

3.5

The smoothness probability of class numbers

9number is a variant of MPQS for DL computations in class groups and has the same expected
asymptotic running time. Thus, if |∆| is large, it is infeasible to compute h(∆) or even oddh(∆). Moreover, there is no ecientmethod known that checks whether a particular odd prime divides h(∆). Consequently,
multiples or factors (in particular the smooth part) of

the Pohlig-Hellman algorithm is not applicable to class groups in general.

There are also

cryptographic protocols (e.g. the Guillou-Quisquater signature protocol) that depend explicitly
on the fact that the group order is unknown.
We now consider the special case whenh(∆) is smooth. If the class number is smooth,there is a practical method to compute the order of an arbitrary element by a method similar
That is, given γ ∈ Cl (∆), set α0 = γ and successivelye(p ,B)pi icompute αi = αi−1
for all pi ≤ B , where pi is the ith prime, B is a smoothness bound,and e(pi , B) depends only on pi and B . For instance, if e(pi , B) = logp B for each pi , thenito the(p − 1)-factoring method.

the algorithm will cover each possible prime power below the smoothness bound.
If h(∆) is B -smooth, then this computation may yield 1Cl(∆) . If this happens, then there
is an i such that αi= 1Cl(∆) but αi−1 6= 1Cl(∆) , and we immediately know that pi is thelargest prime factor of ordCl(∆) γ . If we set γ
e(p )

pi i
integer such that αi−1e(pi )

0 = γ pi

where e(pi ) is the smallest positive= 1Cl(∆) and repeat the complete procedure with γ 0 , then we obtainthe second largest prime factor, and eventually we get the complete prime factorization of

ordCl(∆) γ . Then we are able to compute roots as well as discrete logarithms in hγi with theaid of the Pohlig-Hellman algorithm.
Assume that the (p−1)-like method above succeeds for an element γ and a bound B , and let

q denote the largest prime factor of ordCl(∆) P
γ . It is obvious that if we use a fast exponentiation
method, then we have to perform at leastp<q e(p, B) log2 p group operations to nd q . In
order to nd a smoothness-bound, we must consider the easiest case, i.e. e(pi , B) = 1 forP
all pi . Now
p<q log2 p = θ(q)/ ln 2, where θ is the Chebyshev θ -function. In [23, 24] it
was shown that 0.998697 x < θ(x) < 1.001093 x for all x ≥ 1155901 (under assumption√
2of the Riemann hypothesis, it is even possible to show that |θ(x) − x| = 1/(8π) x ln x
for x ≥ 599, cf. [23, 24]). Therefore, to nd q we have to perform about q/ ln 2 group
operations. Note that we get the same result even in the case e(pi , q) = logp q , becauseiP
p<q log2 pi logpi q = π(q) log2 q = q/ ln 2 as q → ∞.
ExampleWe continue the example from the previous section. By Table 5,

264 group oper-

10 MIPS-years (similar to the computational work to factor a 1024
ations take about 6.6 × 10
bit integer with the aid of the GNFS). If we assume that this amount of work is infeasible,
then it is safe to select a 63 bit smoothness-bound. At the end of the next section we shallsee that a smaller smoothness-bound is sucient.

3.5

The smoothness probability of class numbers

The estimates in this section are based on the heuristics of Cohen and Lenstra [7, 6], although
our derivation is not rigorous at all.

A more rigorous derivation should be done as in [6];this is work in progress, and we shall present the results in a future work.

In this work

we compare class numbers and ordinary integers with respect to smoothness, and we argue
that under reasonable assumptions the probability to get a smooth class number of a random

10

Security of Cryptosystems Based on Class Groups

fundamental discriminant is not much larger than the probability that a random integer issmooth.
Consider the set of all negative fundamental discriminants ∆ such that |∆| ≤ N for somebound N . Based on the heuristics of Cohen and Lenstra we assume that, given an odd prime

p much smaller than N and a positive integer i, the proportion of such discriminants satisfying
pi | h(∆) (or the probability that pi | h(∆)) is at most 1/pi + 1/pi+1 = (1 + 1/p)/pi . (Theconjectures of Cohen and Lenstra predict that for N → ∞, the probability that p | h(∆)
converges to

1−

Y

j≥1

1
1− j
p



=

1
1
1
1
1
1
+ 2 − 5 − 7 + 12 + 15 − · · ·
p p
p
p
p
p

(see [6]). Our assumption for i ≥ 2 is accordance with computational experiments.)
We cannot use similar heuristics for primes that are not small compared to N . However, weknow by the Brauer-Siegel theorem that ln h(∆) ∼ ln
are usually not small themselves.

p|∆| for ∆ → −∞, thus class numbers

Which power of 2 divides h(∆) depends on the factorization of ∆. As discussed in section 3.1.1, we will restrict to special discriminants in order to control the two-part ofh(∆).

In extension to the heuristics of Cohen and Lenstra, we assume that such restrictions do notaect the probabilities discussed above.
For x uniformly chosen from a suciently large interval of integers, the probability thatpi | x is only about 1/pi . Comparing this with the above estimates for class numbers, we
obtain
Pr pi | h(∆)
1≤1+i
Pr (p | x)pfor small odd primes, which suggests that it must be expected to occur more frequently for
negative fundamental discriminants to have smooth class numbers than for uniformly chosen
integers to be smooth. We will now argue, however, that this increase in smoothness does not
imply that a signicant proportion of class numbers will be smooth.
Let k be any odd smooth integer.

We write

k as

Q

p|k p

ep (k) . If k is not so large thatk | h(∆) is actually impossible, then k will have only a few dierent prime factors. Thus, it isconceivable that the probabilities discussed above will be reasonably close to being statisticallyindependent over the dierent p dividing k . Under this presumption, we obtainQep (k) | h(∆)
YPr k | h(∆)
1p|k Pr p
 = Q
 ≤
1
+
=: Fk .
ep (k) | xpPr k | xp|k Pr p
p|kk not exceeding|∆| (as suggested by theQ
Brauer-Siegel Theorem). For reaching the maximum,
k obviously must be of the form k = p<t p, i.e. the product of the smallest primes up toQtsome bound. We havep<t p = e as t tends to innity (e.g. see [22, Chap. 12]), i.e. t ≈pln k ≈ ln |∆|; and thus we estimate the maximum for Fk as


Y
Y 
p
1
1
1+
1+
≈
≈ ln ln |∆| ,
p
p
√
p<t
We now want to estimate the maximum value that this product can take forthe order of

p

p<ln

|∆|

4 Conclusion

11

where the latter approximation can be seen as follows:−γ
ln2 t) (Mertens' theorem, cf. [22, Chap. 12]), whilep<t (1 − 1/p) = e / ln t + O(1/
Q
2
2
γ
2
p (1 − 1/p ) = 1/ζ(2) = 6/π , thusp<t (1 + 1/p) = 6e /π ln t ≈ 1.08 ln t as t tends toandQ(1 + 1/p) = (1 − 1/p2 )/(1 − 1/p),

Qinnity.

|∆| so large that random integers of the expected order of h(∆) aresmooth only with probability close to 0, then the modest maximum size of Fk indicates that
Now if we choose

the tendency of the class number towards having small factors does not mean it will be smoothwith non-negligible probability.
Specically, let B = M

1/u ; then the probability that a random positive integer less than

M is B -smooth is approximately ρ(u), where ρ is Dickmann's ρ-function [14]. We arrive at
an estimated probability of at most ρ(u) ln ln M for the class number being B -smooth byhodd (∆) ph(∆)
requiring M ≈h(∆) c |∆| where hodd (∆) is either 1 or 8 depending on how ∆ is chosen(section 3.1.1) and where c = 0.461559 . . . [5, Sect. 5.10.1]. I.e.,|∆| ≈ 22 B 2u
if h(∆) is odd and|∆| ≈ 28 B 2u
4600 , then ln ln

if the even part of h(∆) is 8. Note that if |∆| < 2
an upper bound for the probability estimate.

p|∆| < 23 so that 8ρ(u) is

Assume that an attacker applies the algorithm from the preceding section to class groupsof random discriminants of a certain length (chosen as described in Sect. 3.1.1).
assume that he will spend at mostFurther

Wmax computational work for a single class group until

he gives up, and that B is the smoothness-bound for which he can succeed with this amountof work.

Then he can expect one case of success for an investment of computational work


W = Wmax / Pr h(∆) is B -smooth . We will determine lower bounds for the size of ∆ basedon this attack scenario.

29 group operations. Let W = 264

Recall that 1 MIPS-year is approximately equivalent to 2

group operations which, by Tables 1 and 5, is comparable to the expected computational work

W is currently infeasible (see also
Wmax = 242 group operations (corresponding to42
a smoothness bound of approximately 2 / ln 2, cf. section 3.4), which is comparable to theto factor a composite 1024 bit integer by the GNFS; then[17] for extrapolations into the future). Let

expected work to factor a 512 bit integer by the GNFS. Then a smoothness-probability of up
to 2−22 is acceptable, thus we need u such that ρ(u) ≈ 8 · 2−22 , and this is satised by u = 8.

Since B ≈ 2

41.5 , the discriminant should have at least 666 bits for case 1 of section 3.1.1, andat least 672 bits for case 2 of section 3.1.1.
If

Wmax is larger or if a smaller smoothness-probability is demanded, then the orderof magnitude of the discriminant will increase accordingly.

For instance, if we choosePr h(∆) is B -smooth = 2−30 with Wmax (and hence B ) as before, then u = 9.6, and thus
the discriminant should have at least 799 (case 1) or 805 (case 2) bits.

4

Conclusion

Based on the investigation of several strategies to solve the CL-DLP and based on heuristic
reasoning, we have shown how to select the discriminant such that the security of cryptosys-

12

Security of Cryptosystems Based on Class Groups

tems based on class groups oer a comparable security as commonly used cryptosystems (suchas RSA). In particular, we have shown that the size of the discriminant asymptotically depends only on index-calculus algorithms (see Table 4). Thus, since index-calculus algorithms
for solving the Cl-DLP are asymptotically much slower than index-calculus algorithms to solve
the IFP (such as the GNFS), the discriminant can be selected smaller than a RSA modulus.
In a future work we shall demonstrate the impact of this result on the eciency andperformance of IQC. As a further research project we would also like to replace the heuristic
reasoning of Sect. 3.5 by a more rigorous reasoning.

References[1] Biehl, I., Buchmann, J., Hamdy, S., and Meyer, A.

Cryptographic Protocols

Based on Intractability of Extracting Roots and Computing Discrete Logarithms. Tech.
Rep. TI-1/00, Fachbereich Informatik, TU Darmstadt, 2000.

tu-darmstadt.de/TI/Veroeffentlichung/TR/ .
[2] Buchmann, J., and Paulus, S.

http://www.informatik.

A One Way Function Based on Ideal Arithmetic in

Number Fields. In Advances in Cryptology  CRYPTO '97 (1997), B. S. Kaliski, Ed.,

vol. 1294 of Lecture Notes in Computer Science , SpringerVerlag, pp. 385394.
[3] Buchmann, J., and Williams, H. C.
quadratic elds.

A key-exchange system based on imaginary

Journal of Cryptology 1 (1988), 107118.

[4] Buchmann, J., and Williams, H. C. Quadratic elds and cryptography. In Number

Theory and Cryptography , J. H. Loxton, Ed., vol. 154 of London Mathematical Society
Lecture Note Series . Cambridge University Press, 1990, pp. 925.

A Course in Computational Algebraic Number Theory , vol. 138 of Graduate
Texts in Mathematics . SpringerVerlag, 1995.

[5] Cohen, H.

[6] Cohen, H., and Lenstra, Jr., H. W.

Heuristics on class groups of number elds.

In Number Theory , vol. 1068 of Lecture Notes in Mathematics . SpringerVerlag, 1983,
pp. 3362.
[7] Cohen, H., and Lenstra, Jr., H. W. Heuristics on class groups. In Number Theory ,vol. 1052 of Lecture Notes in Mathematics . SpringerVerlag, 1984, pp. 2636.

[8] Cox, D. A.

Primes of the form x2 + ny 2 . John Wiley & Sons, 1989.

Ein Algorithmus zur Bestimmung der Klassengruppe positiv deniterbinärer quadratischer Formen . PhD thesis, Universität des Saarlandes, Saarbrücken,[9] Düllmann, S.
Germany, 1991.

[10] Guillou, L. C., and Quisquater, J.-J. A Practical Zero-Knowledge Protocol Fitted

Advances in
Cryptology  EUROCRYPT '88 (1988), C. G. Günther, Ed., vol. 330 of Lecture Notes
in Computer Science , SpringerVerlag, pp. 123128.
To Security Microprocessors Minimizing Both Transmission and Memory. In[11] Hafner, J. L., and McCurley, K. S. A rigorous subexponential algorithm for computation of class groups.

Journal of the American Mathematical Society 2 (1989), 837850.

References

13[12] Hühnlein, D. Quadratic orders for NESSIE  Overview and parameter sizes of threepublic key families.

Tech. Rep. TI-3/00, FB Informatik, TU Darmstadt, 2000.

//www.informatik.tu-darmstadt.de/TI/Veroeffentlichung/TR/ .
[13] Hühnlein, D., and Takagi, T.

Reducing logarithms in totally non-maximal imag-

inary quadratic orders to logarithms in nite eld.
ich Informatik, TU Darmstadt, 1999.

Veroeffentlichung/TR/ .

http:Tech. Rep. TI-8/99, Fachbere-

http://www.informatik.tu-darmstadt.de/TI/[14] Hunter, S., and Sorenson, J. Approximating the Number of Integers Free of Large
Prime Factors.

Mathematics of Computation 66 , 220 (1997), 17291741.

[15] Jacobson, Jr., M. J.

Subexponential Class Group Computation in Quadratic Orders .

PhD thesis, Fachbereich Informatik, TU Darmstadt, Darmstadt, Germany, 1999.
[16] Kaplan, P.

J. reine

Sur le 2-groupe des classes d'idéaux des corps quadratiques.

angew. Math. 283/284 (1976), 313363.
[17] Lenstra, A. K., and Verheul, E. R.

Selecting Cryptographic Keysizes.

H. Imai

Lecture Notes in Computer Science , SpringerVerlag,
pp. 446465. Full version available from http://www.cryptosavvy.com/ .

and Y. Zheng, Eds., vol. 1751 of[18]

LiDIA  A C++ Library For Computational Number Theory. http://www.informatik.

tu-darmstadt.de/TI/LiDIA/ . The LiDIA Group.

[19] Menezes, A. J., van Oorschot, P. C., and Vanstone, S. A.

Cryptography . CRC Press, 1997.
[20] Odlyzko, A. M. The Future of Integer Factorization.

//www.rsa.com/rsalabs/pubs/cryptobytes/ .
[21] Poupard, G., and Stern, J.

Handbook of Applied

CryptoBytes 1 , 2 (1995). http:Security Analysis of a Practical on the y Authen-tication and Siganture Generation.

In

Advances in Cryptology  EUROCRYPT '98(1998), K. Nyberg, Ed., vol. 1403 of Lecture Notes in Computer Science , SpringerVerlag,
pp. 422436.
[22] Rose, H. E.

A Course in Number Theory , 2 ed. Oxford University Press, 1994.

[23] Rosser, J. B., and Schoenfeld, L.

Sharper bounds for the Chebyshev Functions

θ(x) and ψ(x). Mathematics of Computation 29 , 129 (1975), 243269.
[24] Schoenfeld, L. Sharper bounds for the Chebyshev Functions θ(x) and ψ(x), II. Math-ematics of Computation 30 , 134 (1976), 337360.

[25] Silverman, R. D.

Exposing the Mythical MIPS Year.

IEEE Computer 32 , 8 (1999),2226.
[26] te Riele, H. J. J. Factorization of a 512-bits RSA key using the Number Field Sieve.
Announcment on the Number Theory List ( NMBRTHRY@listserv.nodak.edu ), August1999.
[27] van Oorschot, P. C., and Wiener, M. J. Parallel Collusion Search with Cryptanalytic Applications.

Journal of Cryptology 12 , 1 (1999), 128.

14Security of Cryptosystems Based on Class Groups[28] Vollmer, U.

Asymptotically Fast Discrete Logarithms in Quadratic Number Fields.

Accepted for ANTS IV, 2000.