Technical Report No. TI-5/00, 6th June 2000

CRYPTOGRAPHY BASED ON NUMBER FIELDS WITH LARGEREGULATORJOHANNES BUCHMANN, MARKUS MAURER, AND BODO MÖLLER

Abstract. We explain a variant of the Fiat-Shamir identification and signature protocol which is based on the intractability of computing generatorsof principal ideals in algebraic number fields. We also show how to use theCohen-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 of computational 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 [23]). However, there is currently 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 guaranteethat public key cryptography is possible even if the currently used systems are broken, it is necessary to identify alternative computational problems which can beused as the basis of public key schemes.
In this paper, we consider the principal ideal problem (PIP): Let O be an orderof an algebraic number field F . Given a principal O-ideal I, find a generatorof that ideal, i.e. an element α ∈ F such that I = αO. We show how to use theheuristics of Cohen, Lenstra, and Martinet ([13], [14], [15], and [16]) for class groupsof algebraic number fields to generate orders for which PIP is intractable, and we
present PIP-FS, a variant of the Fiat-Shamir identification and signature scheme[17] whose security is based on PIP. We describe an implementation of PIP-FS in
real quadratic fields, we show that it is secure, and we present timings which showthat PIP-FS has the potential to become practical.
PIP is a special case of the number field discrete logarithm problem (NFDL),
which was introduced in [6]. There, it has been suggested to develop cryptographic
primitives based on NFDL. For number fields with large class number, this has been
done in [2]. Here, we present first schemes for number fields with large regulators,
and we show how to generate such fields.
This paper is organized as follows: In Section 2, we present a general versionof the Fiat-Shamir protocols (FS). In Section 3, we explain PIP-FS, a 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], seealso [11] and [10].)
1

2

JOHANNES BUCHMANN, MARKUS MAURER, AND BODO MÖLLER

The goal of the FS protocol is that one party, called the prover, convinces theother party, called the verifier, of his knowledge of a secret key without revealing
any relevant information concerning that secret key. We will also explain how adigital signature scheme can be obtained from this protocol.
In the setup phase of the protocol, the prover and the verifier agree on two abeliangroups 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.
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 theverifier.
2. (Challenge) The verifier selects a challenge e ∈ {0, 1}k and sends it to theprover.
Qk
3. (Response) The prover computes the response r = g i=1 giei and sends it to
the verifier.
Qk
4. (Verification) The verifier checks whether h i=1 hei i = ϕ(r).
Clearly, a prover who knows the secret key can convince the verifier of his identity.
Assume that ϕ has the following one way property: Without knowledge of thesecret key, it is intractable to compute, given (f1 , . . ., fk ) ∈ {0, ±1}k where at least
Qk
one fi is not 0, an s with ϕ(s) = i=1 hfi i . We show that the probability to detectthat a prover does not know the secret key is at least 1 − 1/2k . To increase theprobability, the basic protocol can be repeated several times.
If the prover is able to give the correct answer for two different challenges
Qk(e1 , . . ., ek ) and (e01 , . . . , e0k ), then he knows r, r0 ∈ G such that ϕ(r) = h i=1 hei i0Qekand ϕ(r0 ) = h i=1 hi i . This implies that he can compute s = r0 r−1 such that
0
Qk
e −e
ϕ(s) = i=1 hi i i . Note that e0i − ei ∈ {0, ±1}. By assumption, computing s
without the knowledge of the secret key is intractable. Therefore, a cheating provercannot 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 show that theverifier or an observer are not able to derive the secret key from information 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 be computed 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 cryptograpic hash function f (see [23]). He computesf (d ◦ h) where ◦ is concatenation and d, h are identified with the bit strings bywhich they are represented. The challenge is the sequence of the first k bits of
the hash value. The signature consists of the witness and the reply. The verifiercomputes the challenge from the witness and the document and proceeds as in the
FS protocol.

CRYPTOGRAPHY BASED ON NUMBER FIELDS WITH LARGE REGULATOR

3

3. PIP-FS
We explain PIP-FS, our FS variant which is based on the intractability of solving
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 multiplicative group
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 described in theprevious 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 difficultyof this PIP. The two most efficient methods known for solving the principal ideal
problem are the babystep-giantstep algorithm [5] [1] and the index calculus method[26] [4]. The running time of the babystep-giantstep algorithm is nO(n) R1/2 |∆|o(1)where n is the degree of F , ∆ is the discriminant of O, and R is the regulatorof O. More precisely, the following is true. Let I be a principal O-ideal. Let α
be a generator of I such that the euclidean length of the logarithmic embeddingof α (see [3]) 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 isexp(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 [23]) 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 class number
formula [3] 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 handpthe regulator R of the algebraic number field F is asymptotically proportionalto |∆| where ∆ is the discriminant of F . The heuristics of Cohen, Lenstra, andMartinet predict when the class number is small with very high probability. Thus,
if we choose the number field F
1. with sufficiently large discriminant in order to make index calculus attack
infeasable and2. with small class number (using the heuristics of Cohen, Lenstra, and Martinet),
then the principal ideal problem appears to be intractable.
Next, we must answer the question how the keys, commitment, witness, challenge, and respose are selected or computed. The idea is to use reduced principal
O-ideals and their generators. We will explain this in detail for the case of real
quadratic orders. The methods explained for these orders can be generalized togeneral 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 quadratic orderin which the principal ideal problem is intractable. In particular, we explain

4

JOHANNES BUCHMANN, MARKUS MAURER, AND BODO MÖLLER

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 and represented, and
4. how the verification is performed.
We let O be a real quadratic order of discriminant ∆, class number h, andregulator 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 suchthat 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 [20]. Extrapolating experiments with Jacobson’s algorithm,
Hamdy [18] found that the difficulty of applying the index calculus algorithm in anorder with a 687 bit discriminant is the same as 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.
Factoring PIP-FS
1024
687
1536
958
2048
1208
3072
1665
4096
2084
Table 1. Comparison of factoring with the number field sieveand solving PIP-FS with index calculus.

To make the babystep-giantstep attack impossible, we choose the order such that(2)

R > 2k1 ln ∆,where k1 ≥ 160 is a security parameter. The reason for this choice is given in
Section 4.5.
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 Cohen-Lenstra heuristics[13] and the extended Riemann hypothesis, condition (2) is satisfied with probability
1 − 2−k2 , k2 ∈ N, if√∆(3)> 2k1 +k2 +1 .
ln ∆ ln ln ∆For example, if k1 + k2 = 240, we obtain that ∆ should be larger than 2504 . 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 to solve PIP for
arbitrary reduced principal ideals implies being able to factor the discriminant ([8],[25]). Thus in this case PIP is provably at least as hard as breaking RSA and othercrypto-systems based on factoring integers.

CRYPTOGRAPHY BASED ON NUMBER FIELDS WITH LARGE REGULATOR

5

So let us explain why it suffices to choose ∆ according to (3). Since ∆ is squarefree, O is a maximal order. We can relate the regulator R to the class√ numberh by using the analytic class number formula [3]: We have 2hR = ∆ · L(1, χ)−1Qwhere L(1, χ) = p prime 1 − χ(p)/pis the value 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−1
Littlewood [22], that L(1, χ) > (1+o(1)) (12eγ /π 2 ) ln ln ∆where γ = 0.5772 . . .
is Euler’s constant (cf. [24], where it is also discussed how 1 + o(1) can be replacedby explicit bounds). As 12eγ /π 2 < 4, certainly L(1, χ) > 14 (1 + o(1))(ln ln ∆)−1 ,and from this we obtain the new condition√(1 + o(1)) ∆(4)> 2k1 +1 .
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 [19]: Since ∆ is the product of two
primes p1 , p2 ≡ 3 (mod 4), the class number h is always odd. For estimating theodd 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 thestatistical behaviour of the odd part of the class number. Then the probability
that h > x is asymptotic to 1/(2x) (cf. [13], § 9, (C12) a). With probability at least1 − 2−k2 , we have h ≤ 2k2 . By substituting this into (4), we obtain the condition√(1 + o(1)) ∆> 2k1 +1 .
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 O-ideals,
which we describe in this section. For more details on reduced ideals, we refer to[9], [12], and [1].
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
b is unique modulo 2a.
√ q and a are uniquely determined. The integer √For a√> ∆, we choose
b
such
that
−a
<
b
≤
a;
for
a
<
∆, we choose b such√that ∆ − 2a < b < ∆. We represent I by (q, a, b, c) where c = (b2 − ∆)/(4a). 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 that the number of reduced
O-ideals is finite. For example, the order O itself is a 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)6

JOHANNES BUCHMANN, MARKUS MAURER, AND BODO MÖLLER

with
(6)

 b

 b 2a ct=j √ k b+b ∆c2afor |a| >for |a| <

√

√

∆

∆.

We can also write this as√−b + 2at + ∆(7)
ρ(I) = α(I)I, α(I) =.
2aq
If I is not reduced, then a reduced ideal J that is equivalent to I and an elementγ ∈ F ∗ with J = γI can be computed as follows.
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 thefollowing theorem, which shows that using only reduced O-ideals does not harmthe 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 isprincipal 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, thereduction operator ρ is a transitive permutation. This implies that there is a positive
integer p such that the set of reduced principal ideals is {ρ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
−1
ρ (I) = (|c|, −b + 2s|c|, a + bs + cs), s =
(8)
,
2|c|
which can also be written as
(9)

−1

ρ

1
(I) =
I,
β(I)

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

We also have(10)

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

and
(11)

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

From (10) and (11), we obtain the following lemma, which is used in the construction of the secret and public key and the committment and witness.
Lemma 4.2. Let r be a real number. Then there is a reduced O-ideal which has apositive generator α with |ln α − r| < (ln ∆)/4.
Proof. Let r > 0. Set I0 = O, α0 = 1, Ii+1 = ρ(Ii ), αi+1 = αi α(Ii ). Then Ii is areduced O-ideal with generator αi , αi > 0, 0 < ln αi+1 − ln αi = ln α(Ii ) < (ln ∆)/2by (10) and (11), 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

7

4.3. Secret key, commitment, public key, and witness. Assume that ∆ ischosen as described in Section 4.1.
The secret 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 thanfor reduced O-ideals. Therefore, we may limit ourselves to generators of reduced Oideals when choosing the secret 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 of thatfunction:
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 polynomialtime.
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 secret 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, we need two more security
parameters k2 , k3 ∈ N. The integer k2 is chosen such that an event that happens
with probability 1/2k2 is considered practically impossible. Parameter k3 is chosensuch that 2k3 is an upper bound for 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 for more than 30 years. The commitment is a random integern ∈ [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.1. 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 the challenge. Then the response isPk
r = n + i=1 ei ni . Using r, the verifier is able to verify that there is a generator
Qkof I i=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 [0, . . ., 2k1 − 1], it is
impossible to tabulate the elements of P1 with generators or to guess a secret key
yielding the same public key. We analyze the time required to compute a generatorof an element I of P1 . Let I = close(n) with n ∈ [0, 2k1 − 1]. Since by (2) we haveR ≥ c · 2k1 , it follows that the logarithm of the smallest positive generator of I isapproximately 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 compute a
generator of I this way. Also, by choice of ∆, determining a generator of I by theindex 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 on intervals [0, . . ., b] where b ≥ 2k1 .

8

JOHANNES BUCHMANN, MARKUS MAURER, AND BODO MÖLLER

Now we show that knowledge of values of r, collected from up to 2k3 executionsof 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 most easily done by always using thechallenge (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], sor 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 chosenn ∈ [0, 2` − 1], the probability is less than 2 · 2k1 −` . Combined over 2k3 iterations
k3of the protocol, the probability still is less than 1 − (1 − 2 · 2k1 −` )2 , i.e. under2 · 2k1 −` · 2k3 = 2−k2 , which by choice of k2 ist 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 Oideals. We will show that this function restricted to any interval of 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 where(12)c = d(ln ∆)/2 + 2e.

This function is used for the generation of the public key, the computation of thewitness, and in the verification.
Let n ∈ N. The algorithm computes b = blog2 nc + 1, i.e. the binary length ofn, 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).
To initialize the recursion, an O-ideal I0 is computed which 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 t) 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 iscomputed 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, the ideal 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 . Note that αi+1 is a generator of the reduced principal ideal Ii+1 .

CRYPTOGRAPHY BASED ON NUMBER FIELDS WITH LARGE REGULATOR

9

Because 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 thelogarithms and modify the algorithm from above as follows: If, after reduction,
the approximation to the logarithm γi+1 is too small, we start with β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 of ln βj−1 , but smaller than theapproximation 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.
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; replace j 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 at the endof 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 follows. EachQi
i−jgenerator is of the form αi = j=0 γj2 . After γj has been computed by the procedure above, we approximate its logarithm by cj such that |cj − ln γj | < 2−n+j−b−3 .
We set a0 = c0 and ai+1 = 2ai + ci+1 . Then ai satisfies (15) for 0 ≤ i ≤ b.

10

JOHANNES BUCHMANN, MARKUS MAURER, AND BODO MÖLLER

4.7. Implementing the verification. In the verification step, the verifier knows
the positive integer r, the principal O-ideals I, I1 , . . ., Ik , and the exponents e1 , . . ., ek ∈Qk{0, 1}. He wants to verify that the principal O-ideal I i=1 Iiei has a positive generator α such that ln α is close to rc, where c is defined according to (12).
The verifier uses the reduction algorithm from Section 4.2 to compute a reduced
Qk
O-ideal J and γ ∈ F ∗ with J = γI i=1 Iiei . This is done as follows:
1. Set J = I, γ = 1.
2. For i = 1, . . ., k: If ei = 1, then replace γ by γγ(JIi ) and J by reduce(JIi ).
Qk
Qk
If α is a generator of I i=1 Iiei , then αγ is a generator of J. Since I i=1 Iiei
has a positive generator whose logarithm is close to r and since ln γ is small, it
follows that the reduced O-ideal J has a generator whose logarithm is close to r.
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 ), and Kl by
ρ−1 (Kl ).
In the next theorem, we give an upper bound on the number of steps that arenecessary for the verfication to succeed.
Theorem 4.4. If r is chosen according to the protocol, then the verfication succeeds
after at most n = d2(x + (ln ∆)/4 + 1)/ ln 2e iterations, where x = ((ln ∆)/4 +Pk
Pk
1) i=1 ei + ln ∆ i=1 ei .
Proof. Let Ji−1 denote the value of J before the i-th iteration of the for-loop usedQk
in the reduction of I i=1 Iiei . Then 0 ≤ ln γ(Ji−1 Ii ) ≤ ln ∆ holds for each i (see[7]). This implies(17)|ln γ| ≤ ln ∆

k
X

ei .

i=1

Assume that the response is correct, i.e., there exists a positive generator α ∈ F ∗Qk
Pkwith I i=1 Iiei = αO and |ln α − rc| < ((ln ∆)/4 + 1)(1 + i=1 ei ). It follows from(17) that there is a generator β = αγ of J with |ln β − rc| < x. By (13), we have|close(rc) − rc| < (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, and using the LiDIA-2.0 library [21]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}, we choose
several discriminants with m bits, run the protocol, including order and key generation, and measure the average time per discriminant. We have run the tests withk = 30, i.e., the probability that a cheating prover is detected is at least 1 − 1/230
As challenge, we choose a bit string with 15 bits set to 1. Furthermore, the security
parameters are chosen as k1 = 160, k2 = 80, and k3 = 30 (see Section 4.3).

CRYPTOGRAPHY BASED ON NUMBER FIELDS WITH LARGE REGULATOR

11

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 and J. Buchmann, Algorithms for quadratic orders, Proceedings of Symposia in Applied Math. 48 (1994), 425–449.
2. I. Biehl, J. Buchmann, S. Hamdy, and A. Meyer, A signature scheme based on the intractabilityof computing roots, Tech. Report TI-3/00, Fachbereich Informatik, TU Darmstadt, 2000,
Submitted to CRYPTO 2000.
3. Z. I. Borevich and I. R. Shafarevich, Number theory, Academic Press, New York, 1966.
4. J. Buchmann, On the computation of units and class numbers by a generalization of lagrange’s
algorithm, J. Number Theory 26 (1987), 8–30.
5.
, Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer
Zahlkörper, 1987, Habilitationsschrift.
6. J. Buchmann and S. Paulus, A one way function based on ideal arithmetic in number fields,
Advances in Cryptology – CRYPTO ’97 (B. Kaliski, ed.), Lecture Notes in Computer Science,
vol. 1294, Springer-Verlag, 1997, pp. 385–394.
7. J. Buchmann, C. Thiel, and H. C. Williams, Short representation of quadratic integers, Computational algebra and number theory, 1992, pp. 159–185.
8. J. Buchmann and H. C. Williams, A key-exchange system based on real quadratic fields, Advances in Cryptology – CRYPTO ’89 (G. Brassard, ed.), Lecture Notes in Computer Science,
vol. 435, Springer-Verlag, 1989, pp. 335–343.
9. D.A. Buell, Binary quadratic forms, Springer, New York, 1989.
10. M. V. D. Burmester, Y. Desmedt, F. Piper, and M. Walker, A general zero-knowledge scheme,
Advances in Cryptology - EuroCrypt ’89 (J.-J. Quisquater and J. Vandewalle, eds.), Lecture
Notes in Computer Science, vol. 434, Springer-Verlag, 1989, pp. 122–133.
11. D. Chaum, J.-H. Evertse, and J. van de Graaf, An improved protocol for demonstrating
posession of discrete logarithms and some generalizations, Advances in Cryptology – EUROCRYPT ’87 (D. Chaum and W.L. Price, eds.), Lecture Notes in Computer Science, vol. 304,
Springer-Verlag, 1987, pp. 127–142.
12. H. Cohen, A course in computational algebraic number theory, Springer, Heidelberg, 1995.
13. H. Cohen and H.W. Lenstra, Heuristics on class groups of number fields, Number Theory(A. Dold and B. Eckmann, eds.), Lecture Notes in Mathematics, vol. 1068, Springer-Verlag,
1983, pp. 33–62.
14. H. Cohen and J. Martinet, Class groups of number fields: numerical heuristics, Math. Comp.
48 (1987), 123–137.
15.
, Étude heuristique des groupes de classes des corps de nombres, J. reine angew. Math.
404 (1990), 39–76.
16.
, Heuristics on class groups: some good primes are not too good, Math. Comp. 63(1994), 329–334.
17. A. Fiat and A. Shamir, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology – CRYPTO ’86 (A.M. Odlyzko, ed.), Lecture Notes
in Computer Science, vol. 263, Springer-Verlag, 1986, pp. 186–194.
18. S. Hamdy, Performance and security of cryptosystems based on class groups of imaginary
quadratic orders, Manuscript, 2000.
19. E. Hecke, Vorlesungen über die Theorie der Algebraischen Zahlen, Leipzig, 1923.
20. M. J. Jacobson, Jr., Subexponential class group computations in quadratic orders, Shaker
Verlag, 1999.
21. LiDIA, LiDIA 2.0 – a library for computational number theory, Technische Universität Darmstadt, 2000, Available via anonymous FTP from ftp://ftp.informatik.tu-darmstadt.de/
pub/TI/systems/LiDIA/ or via WWW from http://www.informatik.tu-darmstadt.de/TI/
LiDIA/.

12

JOHANNES BUCHMANN, MARKUS MAURER, AND BODO MÖLLER√
22. J.E. Littlewood, On the class-number of the corpus P ( −k), Proc. London Math. Soc., 2ndseries [ISSN 0024-6115] 27 (1928), 358–372.
23. A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of applied cryptography,
CRC Press, 1997.
24. R. A. Mollin and H. C. Williams, Computation of the class number of a real quadratic field,
Util. Math. 41 (1992), 59–308.
25. R. Scheidler, J. Buchmann, and H. C. Williams., A key exchange protocol using real quadratic
fields, Journal of Cryptology 7 (1994), 171–199.
26. U. Vollmer, Asymptotically fast discrete logarithms in quadratic number fields, ANTS IV,
2000, To appear.
Technische Universität Darmstadt, Fachbereich Informatik, Alexanderstr. 10, 64283
Darmstadt, Germany
E-mail address: {buchmann,mmaurer,moeller}@cdc.informatik.tu-darmstadt.de