Journal de Théorie des Nombresde Bordeaux 12 (2000), 293–307

Cryptography based on number fields
with large regulator
par Johannes BUCHMANN, Markus MAURER
et Bodo MÖLLER
Résumé. Nous introduisons une variante du protocole de signature et d’identification de Fiat-Shamir, basée sur la difficulté pratique qu’il y a à calculer des générateurs des idéaux principaux
dans les corps de nombres. Nous montrons en outre comment
utiliser les heuristiques de Cohen-Lenstra-Martinet pour les groupes de classes dans le but de construire des corps de nombres danslesquels le calcul de générateurs des idéaux principaux est encore
hors d’atteinte.
Abstract. We explain a variant of the Fiat-Shamir identificationand signature protocol that is based on the intractability of computing generators of principal ideals in algebraic number fields.
We also show how to use the Cohen-Lenstra-Martinet heuristics
for class groups to construct number fields in which computing
generators of principal ideals is intractable.

1. Introduction
The security of public key cryptosystems is based on the intractability ofcomputational problems in mathematics and in particular in number theory. Examples are the problems of factoring integers or computing discrete
logarithms in certain finite abelian groups (see [24]). However, there iscurrently no such problem whose computational difficulty can be proved.
On the contrary: Experience with the factoring problem shows that unexpected breakthroughs are always possible. To guarantee that public key
cryptography is possible even if the currently used systems are broken, it isnecessary to identify alternative computational problems that can be usedas the basis of public key schemes.
In this paper, we consider the principal ideal problem (PIP): Let O bean order of an algebraic number field F . Given a principal O-ideal I, finda generator of that ideal, i.e. an element α ∈ F such that I = αO. We
Manuscrit reçu le 17 avril 2000.

294

J. Buchmann, M. Maurer, B. Möller

show how to use the heuristics of Cohen, Lenstra, and Martinet ([13], [14],[15], and [16]) for class groups of algebraic number fields to generate orders
for which PIP is intractable, and we present PIP-FS, a variant of the FiatShamir identification and signature scheme [17] whose security is based on
PIP. We describe an implementation of PIP-FS in real quadratic fields, we
discuss its security, and we present timings that show that PIP-FS has thepotential to become practical.
PIP is a special case of the number field discrete logarithm problem(NFDL), which was introduced in [8]. There, it has been suggested todevelop cryptographic primitives based on NFDL. For number fields withlarge class number, a new scheme has been presented in [2]; also some previously known cryptographic schemes such as [18] and [26] can be adopted
to the class group of a number field since they do not require knowledgeof the group order (cf. [2] and [19]). A bit commitment and an oblivioustransfer scheme for real-quadratic number fields have been described in [3].
Here, we present first identification and signature schemes for number fields
with large regulators. We show how to generate such fields that are suitablefor cryptographic applications.
This paper is organized as follows: In Section 2, we present a generalversion of the Fiat-Shamir protocol (FS). In Section 3, we explain PIP-FS,
an FS variant based on PIP in number fields. A detailed description of
the implementation of PIP-FS in real quadratic number fields is given in
Section 4.
2. Fiat-Shamir identification
In this section, we present a fairly general version of the Fiat-Shamir
identification protocol (FS). (For generalizations of the original Fiat-Shamir
scheme [17], see also [12] and [11].)
The goal of the FS protocol is that one party, called the prover, convinces
the other party, called the verifier, of his knowledge of a private key without
revealing any relevant information concerning that private key. We will also
explain how a digital signature scheme can be obtained from this protocol.
In the setup phase of the protocol, the prover and the verifier agree on
two abelian groups G and H, on a homomorphism ϕ : G → H, and on a
positive integer k. The prover selects k group elements gi ∈ G, 1 ≤ i ≤ k.
The sequence (g1 , . . ., gk ) is his private key. He then computes hi = ϕ(gi ),1 ≤ i ≤ k. The sequence (h1 , . . ., hk ) is his public key.
(In the original Fiat-Shamir protocol, a key issuing center is responsible
for selecting G, H, and ϕ such that the center can efficiently invert ϕusing certain additional information, which must be kept secret. Then thecomponents of any prover’s public key can be derived from a descriptionof the prover containing, for example, name and address information byCryptography based on number fields with large regulator

295

applying a hash function; the key issuing center can compute an appropriate
private key and pass it to the prover. We note that our variant of the FiatShamir protocol does not have this property. Instead, public keys must be
explicitly given, as e.g. in Schnorr’s identification scheme [28].)
The FS identification protocol works as follows:
1. (Commitment and Witness) The prover randomly selects a commitment g ∈ G and computes the witness h = ϕ(g) . The prover sends
the witness h to the verifier.
2. (Challenge) The verifier selects a challenge e ∈ {0, 1}k and sends it to
the prover.
Q
3. (Response) The prover computes the response r = g ki=1 giei andsends it to the verifier.
Q
4. (Verification) The verifier checks whether h ki=1 hei i = ϕ(r).
Clearly, a prover who knows the private key can convince the verifier of
his identity.
Assume that ϕ has the following one way property: Without knowledgeof the private key, it is intractable to compute, given (f1 , . . ., fk ) ∈ {0, ±1}kQ
where at least one fi is not 0, an s with ϕ(s) = ki=1 hfi i . We show that theprobability to detect that a prover does not know the private key is at least
1 − 1/2k . To increase the probability, the basic protocol can be repeatedseveral times.
If the prover is able to give the correct answer for two different challenges (e1 , . . ., ek ) and (e01 , . . . , e0k ), then he knows r, r0 ∈ G such thatQQ
e0
ϕ(r) = h ki=1 hei i and ϕ(r0 ) = h ki=1 hi i . This implies that he can comQe0 −epute s = r0 r−1 such that ϕ(s) = ki=1 hi i i . Note that e0i − ei ∈ {0, ±1}.
By assumption, computing s without the knowledge of the private key isintractable. Therefore, a cheating prover cannot know the correct answer
for two different challenges, and the probability for him to be detected is
at least 1 − 1/2k .
When we explain our variant PIP-FS in Section 3, we will also showthat the verifier or an observer are not able to derive the private key frominformation transmitted during the protocol.
The FS identification protocol is efficient if multiplication in the groups
G and H can be performed efficiently and if the homomorphism ϕ can becomputed efficiently.
In the following way, the FS identification protocol can be transformed
into a signature protocol. Suppose a document d is to be signed. The
signer selects a commitment g and computes the witness h as in the above
protocol. To generate the challenge, the signer uses a cryptographic hashfunction f (see [24]). He computes f (d ◦ h) where ◦ is concatenation andd, h are identified with the bit strings by which they are represented. The

296

J. Buchmann, M. Maurer, B. Möller

challenge is the sequence of the first k bits of the hash value. The signature consists of the witness and the response. The verifier computes thechallenge from the witness and the document and proceeds as in the FS
protocol.
3. PIP-FS
We explain PIP-FS, our FS variant that is based on the intractability ofsolving the principal ideal problem in number fields. Let F be an algebraic
number field and let O be an order of F . In the Fiat-Shamir protocol, we use
the multiplicative group F ∗ of all non-zero elements in F , the multiplicativegroup
P = {αO : α ∈ F ∗ },of principal fractional O-ideals, and the homomorphism
ϕ : F ∗ → P,

α 7→ αO.

With this choice of G, H, and ϕ, the general Fiat-Shamir protocol describedin the previous section can be implemented. We call the resulting protocol
PIP-FS.
In order for PIP-FS to be secure, inverting ϕ must be intractable. Inverting ϕ means solving the principal ideal problem for O-ideals. We discuss
the difficulty of this PIP. The two most efficient methods known for solving the principal ideal problem are the babystep-giantstep algorithm [7] [1]and the index calculus method [29] [6]. The running time of the babystepgiantstep algorithm is nO(n) R1/2 |∆|o(1) where n is the degree of F , ∆ isthe discriminant of O, and R is the regulator of O. More precisely, thefollowing is true. Let I be a principal O-ideal. Let α be a generator of
I such that the euclidean length of the logarithmic embedding of α (see[4]) is minimal, and let a be that length. Then α can be computed intime nO(n) min{a, R}1/2 |∆|o(1) . The running time of the index calculus
algorithm is exp(O(n log n)(log ∆ log log(∆))1/2 ). Thus, in order for the
principal ideal problem to be intractable, the discriminant, the regulator,
and the minimal logarithmic length of the generators must be sufficiently
large. We note that no Pohlig-Hellman attack (see [24]) is known for PIP.
Therefore, no further condition for the order O appears to be necessary.
For the appropriate choice of the order O, we use the analytic classnumber formula [4] and the heuristics of Cohen, Lenstra, and Martinet([13], [14], [15], [16]). The analytic class number formula tells us that the
product of the class number h and the regulator
R of the algebraic numberpfield F is asymptotically proportional to |∆| where ∆ is the discriminantof F . The heuristics of Cohen, Lenstra, and Martinet predict when theclass number is small with very high probability. Thus, if we choose thenumber field FCryptography based on number fields with large regulator

297

1. with sufficiently large discriminant in order to make index calculus
attack infeasible and2. with small class number (using the heuristics of Cohen, Lenstra, andMartinet),
then the principal ideal problem appears to be intractable.
Next, we must answer the question how the keys, commitment, witness,challenge, and response are selected or computed. The idea is to use reduced
principal O-ideals and their generators. We will explain this in detail for thecase of real quadratic orders. The methods explained for these orders canbe generalized to general orders. This will be explained in a forthcoming
paper.
4. PIP-FS in real quadratic fields
In this section, we show how to implement PIP-FS using a real quadraticorder in which the principal ideal problem is intractable. In particular, we
explain
1. how the order O is selected,
2. how the private key and the commitment are selected and represented,
3. how the public key, the witness, and the response are computed andrepresented, and
4. how the verification is performed.
We let O be a real quadratic order of discriminant ∆, class number h,and regulator R. By F we denote the field of fractions of O.
4.1. The order. As explained in Section 3, we have to choose the order
O such that both the index calculus algorithm and the babystep-giantstep
algorithm cannot be used to solve the principal ideal problem in O. We
will, in fact, choose O as a maximal order.
The most efficient variant of the index calculus algorithm that is currently known is due to Jacobson [21]. Extrapolating experiments with
Jacobson’s algorithm, Hamdy [19] found that the difficulty of applying theindex calculus algorithm in an order with a 687 bit discriminant is the sameas the difficulty of factoring a 1024 bit number with the number field sieve.
Therefore, we require that(1)

∆ > 2687

Further comparisons can be found in Table 1.
To make the babystep-giantstep attack impossible, we choose the ordersuch that(2)

R > 2k1 ln ∆,where k1 ≥ 160 is a security parameter. The reason for this choice is given
in Section 4.5.

298

J. Buchmann, M. Maurer, B. Möller

Factoring PIP-FS
1024
687
1536
958
2048
1208
3072
1665
4096
2084
Table 1. Comparison of factoring with the number fieldsieve and solving PIP-FS with index calculus.

To satisfy requirement (2), we choose ∆ to be the product of two random
primes p1 , p2 ≡ 3 mod 4. We will show below that, assuming the CohenLenstra heuristics [13] and the extended Riemann hypothesis, condition (2)is satisfied with probability 1 − 2−k2 , k2 ∈ N, if√∆(3)> 2k1 +k2 +3 .
ln ∆ ln ln ∆For example, if k1 + k2 = 240, we obtain that ∆ > 2509 is sufficient. So if(1) holds, then (2) is satisfied. Choosing ∆ to be the product of two primes
has additional appeal when these primes are not disclosed. Being able tosolve PIP for arbitrary reduced principal ideals implies being able to factor
the discriminant ([9], [27]). Thus in this case PIP is provably at least as
hard as breaking cryptosystems such as RSA that rely on the assumptionthat factoring integers of this form is intractable.
So let us explain why it suffices to choose ∆ according to (3). Since∆ is square-free, O is a maximal order. We can relate the regulator R to
the class number h by using the analytic class number formula [4]: We√
−1Qhave 2hR = ∆ · L(1, χ) where L(1, χ) = p prime 1 − χ(p)/pis thevalue at 1 of the Dedekind L-series for the Kronecker symbol χ = ∆· .
√So our initial condition (2) translates to ∆ · L(1, χ)/(h ln ∆) > 2k1 +1 .
Assuming the ERH, we have, by a result of Littlewood [23], that L(1, χ) >−1
(1 + o(1)) (12eγ /π 2 ) ln ln ∆where γ = 0.5772 . . . is Euler’s constant(cf. [25], where it is also discussed how 1 + o(1) can be replaced by explicit
bounds). As 12eγ /π 2 < 4, certainly L(1, χ) > 14 (1 + o(1))(ln ln ∆)−1 , andfrom this we obtain the new condition√(1 + o(1)) ∆(4)> 2k1 +3 .
h ln ∆ ln ln ∆We now examine the class number h in more detail. For the even part of h,
we can use well-known theorems from genus theory [20]: Since ∆ is the
product of two primes p1 , p2 ≡ 3 (mod 4), the class number h is always odd.

Cryptography based on number fields with large regulator299

For estimating the odd part of the class number, we apply the heuristics
of Cohen and Lenstra [13] with the assumption that our restriction on the
choice of ∆ does not affect the statistical behaviour of the odd part of theclass number. Then the probability that h > x is asymptotic to 1/(2x)(cf. [13], § 9, (C12) a). With probability at least 1 − 2−k2 , we have h ≤ 2k2 .
By substituting this into (4), we obtain the condition√(1 + o(1)) ∆> 2k1 +3 .
2k2 ln ∆ ln ln ∆Assuming that ∆ is large enough such that 1 + o(1) can be omitted, we
arrive at (3).
4.2. Reduced O-ideals. To implement PIP-FS in O, we use reduced Oideals, which we describe in this section. For more details on reduced ideals,
we refer to [27] and [30].
Every fractional O-ideal I has a representation!
√b+ ∆q aZ +
Z
2
where q is a positive rational number, a is a positive integer, and b is an
integer. The numbers q and √a are uniquely determined. The integer b isuniquemodulo2a.
Fora>∆,√we choose b such√√ that −a < b ≤ a; fora < ∆, we choose b such that ∆ − 2a < b < ∆. We represent I by
(q, a, b, c) where c = (b2 − ∆)/(4a) ∈ Z. If q = 1, then√ we write I = (a,√ b, c).
The O-ideal I = (a, b, c) is called reduced if | ∆
−
2a|
<
b
<
∆. If
√
I = (a, b, c) is a reduced O-ideal, then |a| + |c| < ∆. This implies thatthe number of reduced O-ideals is finite. For example, the order O itself isa reduced principal O-ideal.
We explain the reduction operator ρ, which is the basic algorithmic primitive in reduction theory of O-ideals. If I = (q, a, b, c) is an O-ideal, then(5)ρ(I) = (−at2 + bt − c, −b + 2at, −a)

with
(6)

 b

 b 2a ct=j √ k b+b ∆c2a

for a >
for a <√√∆∆.

We can also write this as(7)

ρ(I) = α(I)I,−b + 2at +α(I) =
2aq

√

∆

.

If I is not reduced, then a reduced ideal J that is equivalent to I and anelement γ ∈ F ∗ with J = γI can be computed as follows.

300

J. Buchmann, M. Maurer, B. Möller

1. Set γ = 1 and J = I.
2. While J is not reduced, replace γ by γα(J) and J by ρ(J).
This algorithm terminates with the correct result in quadratic time. We
write γ = γ(I) and J = reduce(I).
The fact that reduction of O-ideals is possible in polynomial time implies
the following theorem, which shows that using only reduced O-ideals does
not harm the security of PIP-FS.
Theorem 4.1. There is a polynomial time reduction from PIP for O-ideals
to PIP for reduced O-ideals.
Proof. Let I be a fractional O-ideal. Instead of solving PIP for I, we solve
PIP for J = reduce(I) = γ(I)I. If J is not principal, then I is not principal.
If J is principal and J = αO, then I is principal and I = α/γ(I)O.
Restricted to the set of reduced ideals in an equivalence class of O-ideals,
the reduction operator ρ is a transitive permutation. This implies that
there is a positive integer p such that the set of reduced principal idealsis {ρi (O) : 0 ≤ i < p} and ρi (O) = ρj (O) if and only if i ≡ j mod p. If
I = (a, b, c) is reduced, then
$√
%
∆
+
b
(8)
ρ−1 (I) = (|c|, −b + 2s|c|, a + bs + cs2 ), s =,2|c|which can also be written as
(9)

ρ

−1

1
I,
(I) =
β(I)

√
b+ ∆
β(I) =.
2|c|

We also have (see [27, Lemma 3.2]
(10)

0 < ln α(I) < (ln ∆)/2

and
(11)

ln α(I) + ln α(ρ(I)) ≥ ln 2

for reduced I.
From (10) and (11), we obtain the following lemma, which is used in
the construction of the private and public key and the commitment andwitness.
Lemma 4.2. Let r be a real number. Then there is a reduced O-ideal thathas a positive generator α with |ln α − r| < (ln ∆)/4.
Proof. Let r > 0. Set I0 = O, α0 = 1, Ii+1 = ρ(Ii ), αi+1 = αi α(Ii ). ThenIi is a reduced O-ideal with generator αi , αi > 0, 0 < ln αi+1 − ln αi =ln α(Ii ) < (ln ∆)/2 by (10), and limi→∞ ln αi = ∞ by (11). This implies
the assertion. For r < 0, the proof is analogous and uses ρ−1 .

Cryptography based on number fields with large regulator

301

4.3. Private key, commitment, public key, and witness. Assume
that ∆ is chosen as described in Section 4.1.
The private key and the commitment are chosen such that the corresponding principal ideal problems are difficult. We now explain how we
can choose them as generators of reduced principal ideals.
It follows from Theorem 4.1 that is is not harder to solve PIP for O-ideals
than for reduced O-ideals. Therefore, we may limit ourselves to generatorsof reduced O-ideals when choosing the private key and the commitment.
We denote the set of all reduced principal O-ideals by P0 . The public key
and the witnesses are computed using the function
close : N → P0 ,which is described in Section 4.6. Here, we use the following properties ofthat function:
1. Given n ∈ N, the value close(n) can be computed in polynomial time.
2. For every n ∈ N, there is a positive generator α of close(n) with|ln α − cn| < (ln ∆)/4 + 1, where c = d(ln ∆)/2 + 2e. It can be computed in polynomial time.
3. The restriction of close to any interval of 2k1 consecutive integers is
injective, where k1 ≥ 160 is chosen as in Section 4.1.
To generate the private key, the prover randomly chooses k integers
n1 , . . ., nk in [0, 2k1 − 1]. The corresponding public key is (I1 , . . ., Ik ) with
Ii = close(ni ), 1 ≤ i ≤ k. For the generation of the commitment, weneed two more security parameters k2 , k3 ∈ N. The integer k2 is chosensuch that an event that happens with probability 1/2k2 is considered practically impossible. Parameter k3 is chosen such that 2k3 is an upper boundfor the number of applications of the PIP-FS protocol with one key pair.
For example, k3 = 30 allows to use the same key pair every second formore than 30 years. The commitment is a random integer n ∈ [0, 2` − 1],` = k1 + k2 + k3 + 1. The witness is I = close(n).
4.4. Response and verification. Let ∆ and c be as in Section 4.3. Let(n1 , . . ., nk ) be the private key and (I1 , . . ., Ik ) the corresponding public key,both chosen as in the previous section. Assume that n is a commitment,
I = close(n) is the corresponding witness, and (e1 , . . ., ek ) ∈ [0, 1]k is thePchallenge. Then the response is r = n + ki=1 ei ni . Using r, the verifierQ
is able to verify that there is a generator of I ki=1 Iiei that is close to cr.
This is explained in Section 4.7.
4.5. Security. We explain why PIP-FS as described is secure. Let P1 ={close(n) : n ∈ [0, . . ., 2k1 − 1]}. As close is injective on the interval

302

J. Buchmann, M. Maurer, B. Möller[0, . . ., 2k1 − 1], it is impossible to tabulate the elements of P1 with generators or to guess a private key yielding the same public key. We analyze the time required to compute a generator of an element I of P1 . Let
I = close(n) with n ∈ [0, 2k1 −1]. Since by (2) we have R ≥ c·2k1 , it follows
that the logarithm of the smallest positive generator of I is approximately
cn. Therefore, the babystep-giantstep algorithm [1] for computing a generator of I takes 2k1 /2 ∆o(1) bit operations. So it is impossible to computea generator of I this way. Also, by choice of ∆, determining a generatorof I by the index calculus algorithm is impossible. Hence, computing generators for elements of P1 is intractable. Similar arguments apply to close
restricted to any other interval [m, . . ., m + 2k1 − 1], and hence to close onintervals [0, . . ., b] where b ≥ 2k1 .
Now we show that knowledge of values of r, collected from up to 2k3
executions of the protocol, with overwhelming probability does not allow
the verifier or an observer to deduce any sub-sum of the secrets n1 , . . ., nk .
For simplicity, assume that an attacker targets only n1 , which is mosteasily done by always using the challenge (1, 0, . . ., 0), so that r = n + n1 .
As n ∈ [0, 2` − 1], this response r only reveals that n1 ∈ [r − 2` + 1, r]. It is
known beforehand that n1 ∈ [0, 2k1 − 1], so r is helpful for determining n1
only if r − 2` + 1 > 0 or r < 2k1 − 1, which implies that n + 2k1 − 2` > 0
or n < 2k1 − 1, respectively. Thus, for uniformly chosen n ∈ [0, 2` − 1],
the probability is less than 2 · 2k1 −` . Combined over 2k3 iterations of thekprotocol, the probability still is less than 1 − (1 − 2 · 2k1 −` )2 3 , i.e. under2 · 2k1 −` · 2k3 = 2−k2 , which by choice of k2 is considered negligible.
4.6. The function close. Let k1 , k2 , k3 , `, k, O, F , ∆, and R be as in
Section 4.3. We explain the implementation of a function
close : N → P0 ,with the properties from Section 4.3 where P0 is the set of all reduced
principal O-ideals. We will show that this function restricted to any intervalof 2k1 consecutive integers is injective, and that for any n ∈ N the ideal
close(n) has a positive generator α with |ln α − cn| < (ln ∆)/4 + 1 wherec = d(ln ∆)/2 + 2e.

(12)This function is used for the generation of the public key, the computationof the witness, and in the verification.
Let n ∈ N. The algorithm computes b = blog2 nc + 1, i.e. the binarylength of n, and t = cn/2b . Then it recursively computes, for 0 ≤ i ≤ b,
reduced O-ideals Ii that have positive generators αi with(13)

|ln αi − 2i t| < (ln ∆)/4 + 1,

and returns Ib = close(n).

Cryptography based on number fields with large regulator

303

To initialize the recursion, an O-ideal I0 is computed that has a positive
generator α0 with |ln α0 − t| < (ln ∆)/4 + 1. This is done by the following
procedure:
1. Set I0 = O, α0 = 1.
2. While |ln α0 − t| ≥ (ln ∆)/4, set α0 = α0 α(I0 ) and I0 = ρ(I0 ).
It follows from (10) and (11) that the algorithm terminates with the correct
result after O(ln ∆) iterations of the while loop. Since the implementation
uses rational approximations to the logarithms, it can only guarantee that|ln α0 − t| < (ln ∆)/4+1 when the while-condition is found to be false. The
details are explained below.
Next we explain the recursion. When Ii has been found, i < b, then Ii+1
is computed as follows. First, the ideal Ii2 is determined. This is a principal
O-ideal with generator αi2 . Note that(14)|ln αi2 − 2i+1 t| = 2|ln αi2 − 2i t| < 2(ln ∆)/4 + 2.

So ln αi2 is pretty close to 2i+1 t, but (13) may not be satisfied. Also, theideal Ii2 is, in general, not reduced. To make Ii2 reduced, the reduction
algorithm explained above is applied. It yields a reduced principal O-ideal
Ii+1 and an element γi+1 ∈ F ∗ such that Ii+1 = γi+1 Ii2 . If ln γi+1 is too
small, then we replace γi+1 by γi+1 α(Ii+1 ) and Ii+1 by ρ(Ii+1 ) until (13)holds for αi+1 = γi+1 αi2 . If ln γi+1 is too large, then we replace γi+1 by
γi+1 /β(Ii+1 ) and Ii+1 by ρ−1 (Ii+1 ) until (13) holds for αi+1 = γi+1 αi2 . Notethat αi+1 is a generator of the reduced principal ideal Ii+1 .
As we can only work with approximations to the logarithms, things are
somewhat more difficult. We explain the details. To obtain (13), we approximate ln αi by a rational number ai with(15)

|ln αi − ai | < 1/4

for 0 ≤ i ≤ b, and each γi+1 is chosen such that(16)|ln γi+1 − 2i+1 t + 2ai | < (ln ∆)/4 + 1/2.

Then αi+1 = γi+1 αi2 satisfies (13).
To find γi+1 such that (16) holds, we work with rational approximations
to the logarithms and modify the algorithm from above as follows: If, after
reduction, the approximation to the logarithm γi+1 is too small, we startwith β0 = γi+1 and determine ideals Jj = βj Ii2 by iterative application of
ρ, such that 2i+1 t − 2ai is larger than or equal to the approximation ofln βj−1 , but smaller than the approximation of ln βj . If the logarithm of
γi+1 is too large, we use ρ−1 instead. At the end, γi+1 is replaced by βj−1
or βj , depending of which logarithm approximation is closer to 2i+1 t − 2ai .
This is done by the following procedure.
1. J0 = reduce(Ii2 ), β0 = γ(Ii2 ), |b0 − ln β0 | < 1/4.

304

J. Buchmann, M. Maurer, B. Möller

2. Set T = 2i+1 t − 2ai .
3. If b0 ≤ T , do the following: Set j = 0. While bj ≤ T , set Jj+1 = ρ(Jj ),βj+1 = α(Jj )βj , and compute bj+1 with |bj+1 −ln βj+1 | < 1/4; replacej by j + 1.
Otherwise: Set j = 1. While bj−1 > T , replace j by j − 1; set
Jj−1 = ρ−1 (Jj ), βj−1 = βj /β(Jj ), and compute bj−1 with |bj−1 −ln βj−1 | < 1/4.
4. If T −bj−1 ≤ bj −T , then set Ii+1 = Jj−1 and γi+1 = βj−1 . Otherwise,
set Ii+1 = Jj and γi+1 = βj .
We prove that this procedure is correct.
Theorem 4.3. γi+1 determined by the procedure satisfies (16).
Proof. Let T , βj , bj be as in the procedure and let j be with the value atthe end of the procedure. It is
bj−1 ≤ T < bj .
If T − bj−1 ≤ bj − T , set c = bj−1 . Otherwise, set c = bj .
First, we examine the case ln βj−1 ≤ T < ln βj . It is |ln γi+1 − T | <|c − T | + 1/4 ≤ min{|ln βj−1 − T |, |ln βj − T |} + 1/2. So, (10) implies|ln γi+1 − T | < (ln ∆)/4 + 1/2.
The second case is ln βj ≤ T . It is |ln γi+1 − T | < |c − T | + 1/4 ≤ |bj −T |+1/4 = bj −T +1/4 = bj −ln βj +ln βj −T +1/4 ≤ |bj −ln βj |+1/4 < 1/2.
We can use the same arguments for the third case T < ln βj−1 .
The initial value α0 is computed by executing the procedure with i = −1,
I−1 = O, and a−1 = 0. Then the procedure determines γ0 , and we set
α0 = γ0 .
Finally, we remark that the approximations ai can be computed as folQ
i−jlows. Each generator is of the form αi = ij=0 γj2 . After γj has been
computed by the procedure above, we approximate its logarithm by cj suchthat |cj − ln γj | < 2−n+j−b−3 . We set a0 = c0 and ai+1 = 2ai + ci+1 . Thenai satisfies (15) for 0 ≤ i ≤ b.
4.7. Implementing the verification. In the verification step, the verifier knows the positive integer r, the principal O-ideals I, I1 , . . ., Ik , and theexponents e1 , . . ., ek ∈ {0, 1}. He wants to verify that the principal O-idealQ
I ki=1 Iiei has a positive generator α such that ln α is close to cr, where cis defined according to (12).
The verifier uses the reduction algorithm from Section 4.2 to computeQ
a reduced O-ideal J and γ ∈ F ∗ with J = γI ki=1 Iiei . This is done asfollows:
1. Set J = I, γ = 1.

Cryptography based on number fields with large regulator

305

2. For i = 1, . . ., k: If ei = 1, then replace γ by γγ(JIi ) and J by
reduce(JIi ).
Q
If α is a generator of I ki=1 Iiei , then αγ is a generator of J. SinceQ
I ki=1 Iiei has a positive generator whose logarithm is close to cr and sinceln γ is small, it follows that the reduced O-ideal J has a generator whose
logarithm is close to cr. The verifier can verify this by computing K =close(r) and by searching for J in the neighborhood of K. More precisely,
he applies the following algorithm where n is chosen according to Theorem
4.4:
1. Compute K = close(r). Set Kr = Kl = K and i = 0.
2. While i < n, J 6= Kl and J 6= Kr replace i by i + 1, Kr by ρ(Kr ), andKl by ρ−1 (Kl ).
In the next theorem, we give an upper bound on the number of steps
that are necessary for the verification to succeed.
Theorem 4.4. If r is chosen according to the protocol, then the verification
succeeds after at most n = d2(x + (ln ∆)/4 + 1)/ ln 2e iterations, wherePP
x = ((ln ∆)/4 + 1) ki=1 ei + ln(32∆) ki=1 ei .
Proof. Let Ji−1 denote the value of J before the i-th iteration of the forQ
loop used in the reduction of I ki=1 Iiei . Then |ln γ(Ji−1 Ii )| ≤ ln(32∆)
holds for each i (see [30, Theorem 5.2]). This implies(17)|ln γ| ≤ ln(32∆)

k
X

ei .

i=1

Assume that the response is correct, i.e., there exists a positive generatorPQα ∈ F ∗ with I ki=1 Iiei = αO and |ln α − cr| < ((ln ∆)/4 + 1)(1 + ki=1 ei ).
It follows from (17) that there is a generator β = αγ of J with |ln β − cr| <x. By (13), we have |close(cr) − cr| < (ln ∆)/4 + 1. Since we apply ρ andρ−1 to find J and since by (11) the step width of two such applications is
at least ln 2, we obtain the assertion.
4.8. Timings. We have implemented the real quadratic order PIP-FS
identification protocol in C++. The running times given in this section has
been measured on a Pentium II, 300 MHz, 64 MB main memory, running
SuSe Linux 2.0.35, using the compiler egcs-2.91.57 with option -O2, andusing the LiDIA-2.0 library [22] with libI as underlying kernel arithmetic.
All timings are given in seconds.
The setup is as follows. For each m ∈ {687, 968, 1208, 1665, 2084}, wechoose several discriminants with m bits, run the protocol, including orderand key generation, and measure the average time per discriminant. We
have run the tests with k = 30, i.e., the probability that a cheating proveris detected is at least 1 − 1/230 As challenge, we choose a bit string with 15

306

J. Buchmann, M. Maurer, B. Möller

bits set to 1. Furthermore, the security parameters are chosen as k1 = 160,
k2 = 80, and k3 = 30 (see Section 4.3).
m
687
968
1208 1665 2084
Order
0.98 3.96 13.25 16.16 63.42
Key pair
54.87 84.56 122.74 196.4 291.76
Witness
3.23 4.86
7.03
10.7 16.03
Response00
0
00
Verification 3.28 4.96
7.15 11.04 16.45

References[1] I. Biehl, J. Buchmann, Algorithms for quadratic orders. In: Mathematics of Computation
1943–1993: a half-century of computational mathematics, Vancouver 1993, W. Gautschi,Ed., vol. 48 of Proceedings of Symposia in Applied Mathematics, American MathematicalSociety (1995), pp. 425–449.
[2] I. Biehl, J. Buchmann, S. Hamdy, A. Meyer, 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/.
[3] I. Biehl, B. Meyer, C. Thiel, Cryptographic protocols based on real-quadratic A-fields (extended abstract). In Advances in Cryptology – ASIACRYPT ’96, K. Kim and T. Matsumoto,Eds., vol. 1163 of Lecture Notes in Computer Science, Springer-Verlag (1996), pp. 15–25.
[4] Z. I. Borevich, I. R. Shafarevich, Number theory. Academic Press, New York (1966).
[5] G. Brassard, Ed., Advances in Cryptology – CRYPTO ’89 , vol. 435 of Lecture Notes in
Computer Science, Springer-Verlag (1990).
[6] J. Buchmann, On the computation of units and class numbers by a generalization of Lagrange’s algorithm. Journal of Number Theory 26 (1987), 8–30.
[7] J. Buchmann, it Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift (1987).
[8] J. Buchmann, S. Paulus, A one way function based on ideal arithmetic in number fields.
In: Advances in Cryptology – CRYPTO ’97, B. S. Kaliski, Ed., vol. 1294 of Lecture Notes
in Computer Science, Springer-Verlag (1997), pp. 385–394.
[9] J. Buchmann, H. C. Williams, A key exchange system based on real quadratic fields. In
Brassard [5], pp. 335–343.
[10] D. A. Buell, Binary quadratic forms. Springer-Verlag, New York (1989).
[11] M. V. D. Burmester, Y. Desmedt, F. Piper, M. Walker, A general zero-knowledge
scheme. In: Advances in Cryptology – EUROCRYPT ’89, J.-J. Quisquater and J. Vandewalle, Eds., vol. 434 of Lecture Notes in Computer Science, Springer-Verlag (1990), pp. 122–133.
[12] D. Chaum, J.-H. Evertse, J. van de Graaf, An improved protocol for demonstrating
posession of discrete logarithms and some generalizations. In: Advances in Cryptology –EUROCRYPT ’87 , D. Chaum and W. L. Price, Eds., vol. 304 of Lecture Notes in Computer
Science, Springer-Verlag (1988), pp. 127–142.
[13] H. Cohen, J. W. Lenstra, Jr., Heuristics on class groups of number fields. In: Number
Theory, Noordwijkerhout 1983, H. Jager, Ed., vol. 1068 of Lecture Notes in Mathematics.
Springer-Verlag (1984), pp. 33–62.
[14] H. Cohen, J. Martinet, Class groups of number fields: numerical heuristics. Mathematics
of Computation 48 (1987), 123–137.
[15] H. Cohen, J. Martinet, Étude heuristique des groupes de classes des corps de nombres.
Journal für die reine und angewandte Mathematik 404 (1990), 39–76.
[16] H. Cohen, J. Martinet, Heuristics on class groups: Some good primes are not too good.
Mathematics of Computation 63 (1994), 329–334.

Cryptography based on number fields with large regulator

307[17] A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems. In: Advances in Cryptology – CRYPTO ’86 (1987), A. M. Odlyzko, Ed.,
vol. 263 of Lecture Notes in Computer Science, Springer-Verlag, pp. 186–194.
[18] L. C. Guillou, J.-J. Quisquater, 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.
[19] S. Hamdy, B. Möller, Security of cryptosystems based on class groups of imaginary quadratic orders. In: Advances in Cryptology – ASIACRYPT 2000 (2000), T. Matsumoto, Ed.,
Lecture Notes in Computer Science, Springer-Verlag. To appear.
[20] E. Hecke, Vorlesungen über die Theorie der Algebraischen Zahlen. Leipzig (1923).
[21] M. J. Jacobson, Jr., Subexponential Class Group Computation in Quadratic Orders. PhD
thesis, Technische Universität Darmstadt, Fachbereich Informatik, Darmstadt, Germany,
1999.
[22] LiDIA – a C++ library for computational number theory. http://www.informatik.
tu-darmstadt.de/TI/LiDIA/. The LiDIA Group.
√[23] J. E. Littlewood, On the class number of the corpus P ( −k). Proceedings of the London
Mathematical Society 2nd series 27 (1928), 358–372.
[24] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography.
CRC Press (1997).
[25] R. A. Mollin, H. C. Williams, Computation of the class number of a real quadratic field.
Utilitas Mathematica 41 (1992), 59–308.
[26] G. Poupard, J. Stern, Security analysis of a practical “on the fly” authentication andsiganture generation. In: Advances in Cryptology – EUROCRYPT ’98 (1998), K. Nyberg,
Ed., vol. 1403 of Lecture Notes in Computer Science, Springer-Verlag, pp. 422–436.
[27] R. Scheidler, J. Buchmann, H. C. Williams, A key-exchange protocol using real quadratic
fields. Journal of Cryptology 7 (1994), 171–199.
[28] C. P. Schnorr, Efficient identification and signatures for smart cards. In: Brassard [5],pp. 239–252.
[29] U. Vollmer, 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.
[30] H.C. Williams, M.C. Wunderlich, On the parallel generation of the residues for thecontinued fraction factoring algorithm. Mathematics of Computation 48 (1987), 405–423.
Johannes Buchmann, Markus Maurer, Bodo Möller
Technische Universität Darmstadt
Fachbereich Informatik
Alexanderstr. 1064283 Darmstadt
Germany
E-mail : {buchmann,mmaurer,moeller}@cdc.informatik.tu-darmstadt.de