Main text appears in T. Okamoto (Ed.): Advances in Cryptology – ASIACRYPT 2000,
Springer-Verlag LNCS 1976, pp. 234-247, ISBN 3-540-41404-5.
Addendum does not appear in proceedings.

Security of Cryptosystems Based on ClassGroups of Imaginary Quadratic Orders
Safuat Hamdy? and Bodo Möller
TU Darmstadt, Fachbereich Informatik{hamdy,moeller}@cdc.informatik.tu-darmstadt.de

Abstract. In this work we investigate the difficulty of the discrete logarithm problem in class groups of imaginary quadratic orders. In particular, we discuss several strategies to compute discrete logarithms in thoseclass 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 offer asimilar security as commonly used cryptosystems.

1

Introduction

Cryptosystems based on class groups of imaginary quadratic orders (IQC) havebeen first proposed 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 quadratic order. The goal of this work is to close
this gap. In particular, we demonstrate how large ∆ must be selected such thatcomputing logarithms in Cl (∆) is as hard as factoring an integer n of given size.
We consider several strategies for computing 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 analgorithm similar to the (p − 1)-factoring method. We obtain the result that, inorder to get the same security with IQC as with RSA with 1024 bit moduli, thediscriminant should have at least 687 bits.
The security of IQC is based on the apparent difficulty of computing discrete
logarithms in class groups of imaginary quadratic orders (Cl-DLP). The Cl-DLP
can be extended to class groups of orders of number fields with arbitrarily highdegree, and in furthermore, there is a generalization of the discrete logarithm
problem [2]. However, in this work we shall focus only on imaginary quadratic
fields, and whenever the term “class groups” appears in the sequel, we actuallymean 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 thiswork. However, it is still unknown whether the Cl-DLP is really harder than the
IFP. The Cl-DLP can be solved with a subexponential index-calculus algorithm?

Supported by the Deutsche Forschungsgemeinschaft (DFG)1due to Hafner and McCurley [11]. This algorithm was improved by Düllmann[9]. Recently, in [30] it has been rigorously proven under the Generalized Riemann Hypothesis that for solving the Cl-DLP using index-calculus√algorithms
one can expect a running time proportional to L|∆| 12 , 34 2 + o(1) where ∆is the discriminant of the imaginary quadratic order. Moreover, Jacobson [16]has applied the ideas of the MPQS to class group computations. In fact, themachinery behind his algorithm is the same as that of the original MPQS, andalthough this algorithm has
empirical data suggest a running not been analyzed,time proportional to L|∆| 21 , 1 + o(1) .
The best known algorithm to solve theq isi the GNFS with asymptotic
h IFP
expected running time proportional to Ln 13 , 3 64
where n is the number to be
9
factored; the best known algorithm to solve the GF-DLP (DLP in multiplicative
groups of Galois fields) is a variant of the GNFS with a similar asymptotic
expected running time where n is the order of the group. Thus, currently the
IFP or the GF-DLP can be solved asymptotically faster than the Cl-DLP. Thismeans that the Cl-DLP is apparently harder than the IFP or the GF-DLP.
Hence class groups form another potential alternative to finite fields for DLbased cryptographic protocols. Unfortunately, popular signature protocols suchas DSA can’t be used with class groups in a direct way, because DSA requires
the knowledge of the group order. Computing the order of an arbitrary classgroup appears to be as hard as computing discrete logarithms in class groups
because no efficient algorithm is known that computes the class number. In [22]a variant of the Schnorr signature scheme that doesn’t require knowledge of thegroup 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 forclass groups, since in this protocol even the signer does not need to know theclass number. Moreover, in [1] a variant of DSA was presented that is based on
the intractability of computing roots in finite abelian groups.
This paper is organized as follows: In Section 2 we recall the background weneed, and in Section 3 we give advice for selecting the security parameters.

2

Class Groups

Recall that we consider class groups of imaginary quadratic fields only. We shall
only state some necessary facts without proofs; for details we refer to [12]. Let∆ be a negative integer √such that ∆ ≡ 0, 1 (mod 4). Then
√ ∆ is the discriminantof a unique order of Q( ∆), namely O∆ = Z + Z(∆ + ∆)/2. O∆ is maximal
if and only if ∆ is fundamental, i.e. if ∆ is square free in case ∆ ≡ 1 (mod 4) or
if ∆/4 is square free in case ∆ ≡ 0 (mod 4).
Let O∆ be any (not necessarily maximal) order. The class group of O∆ isdenoted by Cl (∆), its elements are equivalence classes of invertible ideals of O∆ .
The group order of Cl (∆) is the class number h(∆). Later in this work we shallneed the odd parts of class groups. We denote the odd part of a class groupCl (∆) by Cl odd (∆) and its cardinality by hodd (∆).
2

√Any integral ideal of O∆ can be expressed as Za + Z(b + ∆)/2 such thata, b ∈ Z, a > 0 and 4a | (b2 − ∆), that is, such that there exists a positive integerc such that ∆ = b2 − 4ac. Thus we represent ideals as pairs (a, b) of integers.
Observe that if b = 0 or b = a, then ∆ = −4ac or ∆ = a(a − 4c), respectively,
and if a = c, then ∆ = (b − 2a)(b + 2a). Ideals of any of these forms are called
ambiguous, and their classes have order two in Cl (∆).
An ideal is said to be 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 theelements of Cl (∆) can be represented by the reduced ideals of O∆ , and checking
equality of two ideal classes means comparing the representatives. The neutral
element of Cl (∆) is represented by (1, ∆ mod 2). The group operation of Cl (∆)
is ideal multiplication followed by reduction (e.g. see [16] or [6, Chap. 5]). It
can be shown that a group operation requires O(log2 |∆|) bit operations. The
inverse of the ideal class represented by (a, b) under this operation is thep idealclass represented byp(a, −b). If an ideal (a, b) is reduced, then a <|∆|/3,
therefore a, |b| = O( |∆|).

3

Selecting the Class GroupIn this section we shall see that the discriminant is the cryptographic parameter. We shall discuss how to select a discriminant such that, based on heuristic
grounds, computing discrete logarithms or the order of arbitrary elements in thecorresponding class group is intractable. In particular,– ∆ must be chosen so that there is no efficient reduction of the CL-DLP tosimpler problems,– |∆| must be large enough to preclude attacks with index-calculus algorithms,– h(∆) must be large enough to preclude attacks with ρ or λ 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 Pohlig-Hellman algorithm.
It is tempting to ask whether the discriminant can be chosen such that its
class number has properties selected a priori. However, we do not have muchcontrol over the class number; there is not even a probabilistic efficient algorithm
known that 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 the above 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 index-calculus 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 required
size of the discriminant. In Sect. 3.4 we describe the relevance of the PohligHellman algorithm for class groups and discuss a possible application on class3

groups of smooth order in conjunction with an algorithm similar to the (p − 1)factoring method. Let a smoothness bound B be given; in Sect. 3.5, based onheuristic 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 selection of the discriminant size depends
only on the index-calculus methods. Moreover, since the best known algorithm
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 rolefor class groups of maximal orders, unless the class number is smooth, because
then an algorithm similar to the (p − 1)-factoring algorithm can be applied tocompute the class number.
3.1

Class Group Computation by Reduction to Other Problems

Let ∆ be a negative fundamental discriminant and let f be a positive integer.
Then, if ∆ 6= −3, −4,
  
Y
∆ 1
h(∆f 2 ) = h(∆)f
1−
,
(1)
p p
p|f

where (∆/p) denotes the Kronecker symbol. For instance, h(−8) = 1 and h(−8p2 ) =p − (−8/p). Since in general it is intractable to compute class numbers of large
fundamental discriminants (see below), this could be a nice way to avoid suchcomputations altogether and yet know the class number.
However, the Cl-DLP in Cl (−8p2 ) can be reduced in polynomial time to the
GF-DLP in Fp [14]. Currently no similar efficient reductions for maximal orders
are known. Therefore we shall use only class groups of maximal orders, and in
the sequel ∆ will always be fundamental and thus O∆ will be maximal.
Selection of a Fundamental Discriminant In order to check whether anarbitrary 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 underconsideration is large. A better method is to construct D from distinct prime
factors, and set ∆ = −D if D ≡ 3 (mod 4) and ∆ = −4D otherwise.
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-partof the class number is known to be small: In case 1, h(∆) is odd; in case 2, theeven part of h(∆) is exactly 8 (see [17, Proposition B09 ]).
4

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 (∆) [25], therefore IFP≤ Cl-DLP. This means that if ∆ is chosen like this and p and q are not disclosed, then solving the Cl-DLP for ∆ is at least as hard as breaking IFP-based
cryptosystems such as RSA with modulus pq.
3.2

Class Group Computations by Index-Calculus Techniques

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

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

for real positive x, real positive c, and 0 ≤ e ≤ 1. In practice, instead of the termLx [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 Cl-DLP. In the following, we assume the expected hrunningq i time forfactoring an integer n by the GNFS to be proportional to Ln 13 , 3 64
9 . For the
Cl-DLP, index-calculus
algorithms with an expected running time proportional√ 
to L|∆| 12 , 34 2 have been presented in [30]. However, Jacobson [16] showed that
one can use a variant of the MPQS for DL-computations in Cl (∆). The MPQS
factoring algorithm has a conjectured expected running time proportional to
Ln 21 , 1 , while the MPQS DL-computation algorithm hasn’t been analyzed,
yet (not even heuristically). Empirical data suggests an expected running timeof L|∆| 12 , 1 , so we shall base our arguments on this running time. In terms of
security and efficiency, this will yield slightly larger keys: If we underestimate therunning 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 the algorithm when executed with x1 , then therunning time t2 of the algorithm with input x2 can be estimated by the equationt1
Lx1 [e, c]=
Lx2 [e, c]t2(3)(cf. [21] or [18]). However, this holds only if the sizes of x1 and x2 do not differ
too much; otherwise it can’t be ignored that o(1) → 0. Thus, if x2 is much larger
than x1 , then t2 will be a significant overestimate. (For more precise estimatestaking into account the o(1) term, see [13]. We stick to (3) since the estimatespresented here differ only slightly from those given in [13].)
Table 1 shows some extrapolated running times for the GNFS. They are basedon data points of the factorization of RSA-155 (155 decimal digits, 512 bits) with5

Table 1. Estimated expected computational work of the GNFS for larger inputs
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

the GNFS [28]. In particular, it was estimated that about 8000 MIPS-years werespent.
To estimate the expected running time of the MPQS for DL-computations inclass groups for large groups, we made extensive experiments where we computed
discrete logarithms in 20 class groups of different negative discriminants for eachmagnitude tabulated below. The computations were carried out on a Sparc with
Ultra-170 processor using Jacobson’s MPQS implementation, which is part of
the C++ library LiDIA [19]. The results are summarized in Table
 2.
Table 2 supports the conjectured running time of L|∆| 12 , 1 for the MPQS.
Note also that the standard deviation is almost always about half the running
time. This shows that the running times are pretty spread, which in turn confirms
our suspicions of taking just a single sample.
SUN Microsystems does not publish MIPS ratings for its machines, and infact, the unit MIPS-year is actually not appropriate [27]. However, it is widelyused, so for simplicity we assume 100 MIPS, which is a value of reasonable orderof magnitude
for the machine that we used. By Table 2 let us assume thatL|∆| 21 , 1 /t∆ = 1.8 × 107 sec−1 . Then we obtain the extrapolations in Table 3.
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 for solving the IFP for n of some particular magnitudes,
we arrive at Table 4.
3.3

Class Group Computations by Pollard’s λ Method

We now consider Pollard’s λ method for computing discrete logarithms, ordersof group elements and hence roots of group elements.pFrom [29] it is known thatthe unparallelized version of this algorithm takes π|G|/2 group operations(ignoring lower order terms) for cyclic groups G. Moreover, r-fold parallelization
speeds up the λ-method by factor r.
6

Table 2. Empirical computational work of the Cl-MPQS for relatively small inputs
1 
magnitude of mean running time (sec) standard
L, 1 / t∆ (sec−1 )|∆|t∆deviation |∆| 2
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

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

By the heuristics of Cohen and Lenstra [7, 8], the probability that Cl odd (∆)
is cyclic is 0.9775 . . . . Moreover, it can be deduced from the heuristics that if
Cl odd (∆) is not cyclic, then with high probability Cl odd (∆) has a cyclic subgroup
Gcyc such that |Gcyc | is of nearly the same order of magnitude as hodd (∆), andtherefore, by our selection of ∆, the even part is 1 or 8 and thus |Gcyc | and h(∆)
have nearly the same order of magnitude.
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 boundQ
2 p
is h(∆) > 1/55 ln |∆| p|∆ 1 − p+1 [6, Sect. 5.10.1], which is too weak forp
our purposes. By the Brauer-Siegel Theorem we know that ln h(∆) ∼ ln |∆|7

Table 3. Estimated expected computational work of the Cl-MPQS for larger inputs
magnitude of
expected no. of MIPS-years|∆|
for solving the Cl-DLP in Cl (∆)
2256
2.58
2348
9.75 × 103
2512
1.18 × 107
2640
6.74 × 109
2768
2.24 × 1012
2896
4.94 × 1014
1024
2
7.79 × 1016
1280
28.90 × 1020
1536
2
4.56 × 1024
1792
2
1.26 × 1028
2048
2
2.13 × 1031
2560
2
1.92 × 10373072
25.30 × 1042
3584
2
5.88 × 1047
4096
2
3.15 × 1052
Table 4. Estimated expected computational work of the GNFS for factoring integers
and the Cl-MPQS for computing discrete logarithms in class groups aligned
magnitude of
expected no. of MIPS-years
n
|∆|
768
540
2
2
4.99 × 107
1024
687
2
2
6.01 × 1010
1536
958
2
2
5.95 × 1015
2048
1208
2
2
7.05 × 1019
3072
1665
2
2
2.65 × 1026
2084
4096
2
2
5.87 × 1031

p 1−
p 1+
as ∆ → −∞, that is, |∆|≤ h(∆) ≤ |∆|for any positive real  andsufficiently large ∆, but no explicit constants are known to make this statement
effective. However, if one assumes the Extended Riemann Hypothesis, then it ispossible to show [20] thatp
(1 + o(1)) |∆|h(∆) > c1
log log |∆|(4)for ∆ 6= −3, −4 where c1 =pπ/(12eγ ) ≈ 0.147. Moreover, it is possible to showthat h(∆) is on average c2 |∆| where c2 = 0.461559 . . . [6, Sect. 5.10.1]. This
result has been proven for averages taken over class numbers of fundamental dis8

Table 5. Estimated expected computational work of the λ-method
magnitude of expected no.
pof Group operations expected no. of MIPS-yearsh(∆)|∆|πh(∆)/2
2108
2218
254
4.56 × 107
129
260
64
2
2
2
6.60 × 1010
2162
2326
281
6.12 × 1015
2189
2380
294
7.09 × 1019
2233
2468
2116
2.97 × 1026
2268
2538
2134
5.51 × 1031

criminants. In this work we make the assumption that this result is not affectedby the restriction to the special discriminants given in section 3.1.
Example The time to perform a single group operation in Cl (∆) depends on ∆,yet let us assume a fixed time of 1 ms on a machine with a computing power of
100 MIPS. Then the computational work of a single MIPS-year is equivalent toabout 228.23 group operations. Based on this assumption and on the assumed
average for the class number of a prime discriminant, in Table 5 we present somesamples for (prime) discriminants, their average class number, and the expectedcomputing amount for computing discrete logarithms by the λ-method.

3.4

Class Group Computations and the Pohlig-Hellman Algorithm

The Pohlig-Hellman algorithm utilizes the prime factorization of the group orderin order to simplify DL computations. However, the best known algorithm forcomputing the class number is a variant of MPQS for DL computations in classgroups and has heuristically the same expected asymptotic running time as theoriginal MPQS. Thus, if |∆| is large, it is infeasible to compute h(∆) or evenodd multiples or factors (in particular the smooth part) of h(∆). Moreover,there is no efficient method known that checks whether a particular odd prime
divides h(∆). Consequently, the Pohlig-Hellman algorithm is not applicable toclass groups in general. There are also cryptographic protocols (e.g. the GuillouQuisquater signature protocol) that depend explicitly on the fact that the grouporder is unknown.
We now consider the special case when h(∆) is smooth. If the class number
is smooth, then it is possible to compute the order of an arbitrary element by amethod similar to the (p − 1)-factoring algorithm. That is, given γ ∈ Cl (∆), sete(pi ,B)piα0 = γ and successively compute αi = αi−1
for all pi ≤ B, where pi is theith prime, B is a smoothness bound, and e(pi , B) depends only on pi and B.
For instance, if e(pi , B) = logpi B for each pi , then the algorithm will cover eachpossible prime power below the smoothness bound. A similar method is used in
the factoring algorithm of Schnorr and Lenstra [25].

9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 immediatelye(pi )

know that pi is the largest prime factor of ordCl(∆) γ. If we set γ 0 = γ pie(pi )

pi
where e(pi ) is the smallest positive integer such that αi−1
= 1Cl(∆) and repeat
the complete procedure with γ 0 , then we obtain the second largest prime factor,
and eventually we get the complete prime factorization of ordCl(∆) γ. Then weare able to compute roots as well as discrete logarithms in hγi by applying the
Pohlig-Hellman algorithm.
Assume that the (p − 1)-like method above succeeds for an element γ anda bound B, and let q denote the largest prime factor of ordCl(∆) γ. It is obvious that
P if we use a fast exponentiation method, then we have to perform atleast p<q e(p, B) log2 p group operations to find q. In order to find a smoothness
P bound, we must consider the easiest case, i.e. e(pi , B) = 1 for all pi . Now
p<q log2 p = θ(q)/ ln 2, where θ is the Chebyshev θ-function. In [24] it has
been shown that 0.998684 x < θ(x) < 1.001102 x for all x ≥ 1319007 (under assumption of √the Riemann hypothesis, it is even possible to show that
|θ(x) − x| = 1/(8π) x ln2 x for x ≥ 599, cf. [26]). Therefore, to find q we have toperform about q/ ln 2 group operations.
P (Note that we get the same result evenin the case e(pi , q) = logpi q, because p<q log2 pi logpi q ≈ π(q) log2 q ≈ q/ ln 2
as q → ∞, where π(q) denotes the number of primes up to q.) In Sect. 3.5, we
will use this result to determine lower bounds for the required size of ∆.

Example We use part of the example from the previous section, namely, that 264
group operations require about 6×1010 MIPS-years (similar to the computational
work to factor a 1024 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 64 bit smoothness
bound. At the end of the next section we will see that a smaller smoothness
bound is sufficient.
3.5

The Smoothness Probability of Class Numbers

The estimates in this section are based on the heuristics of Cohen and Lenstra[7, 8], although our derivation is not rigorous at all. A more rigorous derivation
should be done as in [8]; 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 theprobability to get a smooth class number of a random fundamental discriminant
is not much larger than the probability that a random integer is smooth.
Consider the set of all negative fundamental discriminants ∆ such that |∆| ≤N for some bound 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, theproportion of such discriminants satisfying pi | h(∆) (or the “probability” thatpi | h(∆)) is at most 1/pi + 1/pi+1 = (1 + 1/p)/pi . The conjectures of Cohen and
Lenstra [8] predict that for N → ∞, the probability that p | h(∆) converges to
10

1−

Y

j≥1

1−

1
pj



=

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

(5)

Our assumption for i ≥ 2 is accordance with computational experiments [5].
We cannot use similar heuristics for primes that are not small comparedtop
N . However, we know by the Brauer-Siegel theorem that ln h(∆) ∼ ln |∆| for∆ → −∞, thus class numbers are usually not small themselves.
Which power of 2 divides h(∆) depends on the factorization of ∆. As discussed in section 3.1, we will restrict to special discriminants in order to control
the two-part of h(∆). In extension to the heuristics of Cohen and Lenstra, we
assume that such restrictions do not affect the probabilities discussed above.
For x uniformly chosen from a sufficiently large interval of integers, the probability that pi | x is only about 1/pi . Comparing this with the above estimatesfor class numbers, we obtain
Pr pi | h(∆)
1
≤1+
(6)
Pr (pi | 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 significant proportion ofclass numbers will be smooth.
Q
Let k be any odd smooth integer. We write k as p|k pep (k) . If k is not so largethat k | h(∆) is actually impossible, then k will have only a few different prime
factors. Thus, it is conceivable that the probabilities discussed above will bereasonably close to being statistically independent over the different p dividingk. Under this presumption, we obtainQep (k)Y| h(∆)Pr k | h(∆)
1  defp|k Pr p
 = Q
 ≤
1
+
= Fk .
(7)
ep (k) | xpPr k | xp|k Pr p
p|k

We now want to estimate thep maximum value that this product can take for k
not exceeding the order of |∆| (as suggested by the Brauer-Siegel Theorem).
Q
In order to reach the maximum, k obviously must be of the form k = p<t p,Qi.e. the product of the smallest primes up to some bound. We have p<t p ≈ etp
as t tends to infinity (e.g. see [23, Chap. 12]), i.e. t ≈ ln k ≈ ln |∆|; and thus
we estimate the maximum for Fk as


Y
Y 
p
1
1
1+
≈
1+
≈ ln ln |∆| ,
(8)
p
p
√
p<t
p<ln

|∆|

where the lattercan be seen as follows: (1+1/p) = (1−1/p2 )/(1−Q approximation−γ1/p), and p<t (1 − 1/p) = e / ln t + O(1/ ln2 t) (Mertens’ theorem, cf. [23,Q
Q
Chap. 12]), while p (1 − 1/p2 ) = 1/ζ(2) = 6/π 2 , thus p<t (1 + 1/p) ≈6eγ /π 2 ln t ≈ 1.08 ln t as t tends to infinity.
11Now if we choose |∆| so large that random integers of the expected order ofh(∆) are smooth only with probability close to 0, then the modest maximum
size of Fk indicates that the tendency of the class number towards having small
factors does not mean it will be smooth with non-negligible probability.
Specifically, 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 [15]. We arrive at an estimated probability of at most ρ(u) ln ln Mpodd (∆)
for the class number being B-smooth by requiring M ≈ hh(∆)
c |∆| where
hodd (∆)
h(∆)

is either 1 or 18 depending on how ∆ is chosen (Sect. 3.1) and wherec = 0.461559 . . . [6, Sect. 5.10.1]. I.e.,|∆| ≈ 22 B 2u

(9)

if h(∆) is odd and|∆| ≈ 28 B 2u

(10)p
if the even part of h(∆) is 8. Note that if |∆| < 2, then ln ln |∆| < 23 sothat 8ρ(u) is an upper bound for the probability estimate.
Assume that an attacker applies the algorithm from the preceding section
to class groups of random discriminants of a certain length (chosen as described in Sect. 3.1). Further assume that he will spend at most Wmax computational work for a single class group until he gives up, and that B is thesmoothness bound for which he can succeed with this amount of work. Thenhe 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 thesize of ∆ based on this attack scenario.
Recall that 1 MIPS-year is approximately equivalent to about 229 group
operations. Let W = 264 group operations which is comparable to the expectedcomputational work to factor a composite 1024 bit integer by the GNFS; thenW is currently infeasible (see the example in Sect. 3.4). Let Wmax = 242 group
operations (corresponding to a smoothness bound of approximately 242 / ln 2, seeSect. 3.4), which is comparable to the expected work to factor a 512 bit integer
by the GNFS. Then a smoothness probability of up to 2−22 is acceptable, thus weneed u such that ρ(u) ≈ 2−22 /8, and this is satisfied by u = 8. Since B ≈ 241.5 ,the discriminant should have at least 666 bits for case 1 of Sect. 3.1 and at least
672 bits for case 2 of Sect. 3.1 according to (9) and (10).
If Wmax is larger or if a smaller smoothness probability is demanded, then theorder of magnitude of the discriminant
will increase accordingly. For instance,
if we choose Pr 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.
4600

4Conclusion

Based on the investigation of several strategies to solve the CL-DLP and basedon heuristic reasoning, we have shown how to select the discriminant such that12

the security of cryptosystems based on class groups offer a comparable security
as commonly used cryptosystems (such as RSA). In particular, we have shownthat 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 an
RSA modulus.
In a future work we shall demonstrate the impact of this result on the efficiency and performance of IQC. As a further research project we would also liketo replace the heuristic reasoning of Sect. 3.5 by a more rigorous reasoning.

Acknowledgements
We would like to thank Johannes Buchmann and Ulrich Vollmer for valuable
discussions and comments, as well as the anonymous ASIACRYPT 2000 referee
for his comments and suggestions.

References
1. Biehl, I., Buchmann, J., Hamdy, S., and Meyer, A. A signature scheme
based on the intractability of extracting roots. Tech. Rep. TI-1/00, Technische
Universität Darmstadt, Fachbereich Informatik, 2000.
http://www.informatik.tu-darmstadt.de/TI/Veroeffentlichung/TR/.
2. Buchmann, J., and Paulus, S. A one way function based on ideal arithmetic innumber 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. A key-exchange system based on imaginary
quadratic fields. Journal of Cryptology 1, 3 (1988), 107–118.
4. Buchmann, J., and Williams, H. C. Quadratic fields and cryptography. In Number Theory and Cryptography, J. H. Loxton, Ed., vol. 154 of London MathematicalSociety Lecture Note Series. Cambridge University Press, 1990, pp. 9–25.
5. Buell, D. A. The expectation of success using a Monte Carlo factoring method— some statistics on quadratic class numbers. Mathematics of Computation 43,
167 (1984), 313–327.
6. Cohen, H. A Course in Computational Algebraic Number Theory, vol. 138 of
Graduate Texts in Mathematics. Springer–Verlag, 1995.
7. Cohen, H., and Lenstra, Jr., H. W. Heuristics on class groups. In Number
Theory, New York 1982, vol. 1052 of Lecture Notes in Mathematics. SpringerVerlag, 1984, pp. 26–36.
8. Cohen, H., and Lenstra, Jr., H. W. Heuristics on class groups of number
fields. In Number Theory, Noordwijkerhout 1983, vol. 1068 of Lecture Notes inMathematics. Springer-Verlag, 1984, pp. 33–62.
9. Düllmann, S. Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen. PhD thesis, Universität des Saarlandes,
Saarbrücken, Germany, 1991. German.
10. Guillou, L. C., and Quisquater, J.-J. A practical zero-knowledge protocol
fitted to security microprocessors minimizing both transmission and memory. In
Advances in Cryptology — EUROCRYPT ’88 (1988), C. G. Günther, Ed., vol. 330
of Lecture Notes in Computer Science, Springer–Verlag, pp. 123–128.

13

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.
12. Hua, L. K. Introduction to Number Theory. Springer–Verlag, 1982.
13. Hühnlein, D. Quadratic orders for nessie — overview and parameter sizes ofthree public key families. Tech. Rep. TI-3/00, Technische Universität Darmstadt,
Fachbereich Informatik, 2000.
http://www.informatik.tu-darmstadt.de/TI/Veroeffentlichung/TR/.
14. Hühnlein, D., and Takagi, T. Reducing logarithms in totally non-maximal
imaginary quadratic orders to logarithms in finite fields. In Advances in Cryptology— ASIACRYPT ’99 (1999), K. Y. Lam, E. Okamato, and C. Xing, Eds., vol. 1716
of Lecture Notes in Computer Science, Springer–Verlag, pp. 219–231.
15. Hunter, S., and Sorenson, J. Approximating the number of integers free oflarge prime factors. Mathematics of Computation 66, 220 (1997), 1729–1741.
16. Jacobson, Jr., M. J. Subexponential Class Group Computation in Quadratic
Orders. PhD thesis, Technische Universität Darmstadt, Fachbereich Informatik,
Darmstadt, Germany, 1999.
17. Kaplan, P. Sur le 2-groupe des classes d’idéaux des corps quadratiques. Journal
für die reine und angewandte Mathematik 283/284 (1976), 313–363. French.
18. Lenstra, A. K., and Verheul, E. R. Selecting cryptographic keysizes. In
Practice and Theory in Public Key Cryptography, PKCS 2000 (2000), H. Imai and
Y. Zheng, Eds., vol. 1751 of Lecture Notes in Computer Science, Springer–Verlag,
pp. 446–465. Full version available from http://www.cryptosavvy.com/.
19. LiDIA — a c++ library for computational number theory.
http://www.informatik.tu-darmstadt.de/TI/LiDIA/. The√LiDIA Group.
20. Littlewood, J. E. On the class number of the corpus p( −k). Proceedings of
the London Mathematical Society, 2nd series 27 (1928), 358–372.
21. Odlyzko, A. M. The future of integer factorization. CryptoBytes 1, 2 (1995).
http://www.rsa.com/rsalabs/pubs/cryptobytes/.
22. Poupard, G., and Stern, J. Security analysis of a practical “on the fly” authentication 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.
23. Rose, H. E. A Course in Number Theory, 2 ed. Oxford University Press, 1994.
24. Rosser, J. B., and Schoenfeld, L. Sharper bounds for the chebyshev functions
θ(x) and ψ(x). Mathematics of Computation 29, 129 (1975), 243–269.
25. Schnorr, C. P., and Lenstra, Jr., H. W. A monte carlo factoring algorithmwith linear storage. Mathematics of Computation 43, 167 (1984), 289–311.
26. Schoenfeld, L. Sharper bounds for the chebyshev functions θ(x) and ψ(x), ii.
Mathematics of Computation 30, 134 (1976), 337–360.
27. Silverman, R. D. Exposing the mythical mips year. IEEE Computer 32, 8 (1999),
22–26.
28. te Riele, H. J. J. Factorization of a 512-bits rsa key using the number fieldsieve. Announcment on the Number Theory List (NMBRTHRY@listserv.nodak.edu),
August 1999.
29. van Oorschot, P. C., and Wiener, M. J. Parallel collusion search with cryptanalytic applications. Journal of Cryptology 12, 1 (1999), 1–28.
30. Vollmer, U. Asymptotically fast discrete logarithms in quadratic number fields.
In Algorithmic Number Theory, ANTS IV (2000), W. Bosma, Ed., vol. 1838 of
Lecture Notes in Computer Science, Springer–Verlag, pp. 581–594.

14

Addendum1
Section 3.1 on page 4 misses a possibility for selecting a fundamental discriminant: another one of the simplest cases is ∆ = −pq where p and q are primes
such that pq ≡ 3 (mod 4) and (p/q) = −1. In this case, the even part of h(∆) isexactly 2.

1

Does not appear in ASIACRYPT 2000 proceedings.

15