Cryptography in Quadratic Function Fields.
We describe several  cryptographic schemes in quadratic function fields of odd characteristic.  In both the real and the imaginary representation of such a field,  we present a Diffie-Hellman-like key exchange protocol as well  as a public-key cryptosystem and a signature scheme of ElGamal  type. Several of these schemes are improvements of systems previously  found in the literature, while others are new. All systems are  based on an appropriate discrete logarithm problem. In the imaginary  setting, this is the discrete logarithm problem in the ideal  class group of the field, or equivalently, in the Jacobian of  the curve defining the function field. In the real case, the  problem in question is the task of computing distances in the  set of reduced principal ideals, which is a monoid under a suitable  operation. Currently, the best general algorithms for solving  both discrete logarithm problems are exponential (subexponential  only in fields of high genus), resulting in a possibly higher  level of security than that of conventional discrete logarithm  based schemes.
Introduction
Since the introduction of the well-known Diffie-Hellman key exchange protocol [16], many cryptographic
schemes based on discrete logarithms in a variety of groups (and even semi-groups) have been developed.
Among them, the signature scheme due to ElGamal [17], now the basis of the U.S. Digital Signature Standard
[28], is notable. ElGamal also presented a discrete logarithm based public-key cryptosystem in [17].
Any finite group or semi-group G with a fast operation and a sufficiently difficult discrete logarithm problem
(DLP) lends itself to the use of discrete logarithm based cryptography. Diffie and Hellman as well as ElGamal
used
, the multiplicative group of a finite prime field. Buchmann et al. based a key exchange protocol
on discrete logarithms in the ideal class group of an imaginary quadratic number field [10, 9]. The first
example of a non-group underlying a discrete logarithm based system was the set R of reduced principal
ideals of a real quadratic number field, which admits a structure first explored by Shanks [35] and termed
infrastructure by him. A key exchange protocol using elements of R as keys was introduced in [11] and
Research supported by NSF grant DMS-9631647
implemented in [33]. A signature scheme using the same set was briefly mentioned in [8]. These ideas were
subsequently adapted to real quadratic function fields over finite fields, where the set of reduced principal
ideals exhibits an analogous infrastructure. The first discrete logarithm based system in real quadratic
function fields of odd characteristic was the key exchange protocol of [34], followed by a signature scheme
in [32], and both a key exchange and a signature algorithm for even characteristic in [27]. Other schemes
for real quadratic function fields and number fields, such as an oblivious transfer protocol, were discussed in
[7]. The function field schemes are faster, simpler, and easier to implement than the corresponding number
field systems. They use finite field arithmetic, thereby eliminating the problem of rational approximations,
and their underlying DLP can currently only be solved in exponential time, whereas for the corresponding
problem in number fields, a subexponential algorithm is known. Thus, these fields seem to represent a
promising setting for cryptography.
This paper considers a variety of discrete logarithm based cryptographic schemes in quadratic function fields
of odd characteristic. We present Diffie-Hellman-like key exchange protocols as well as ElGamal-like signature
schemes and public key systems in both the real and the imaginary model of such a field. Implementations
of hyperelliptic systems (see [24]) using the ideal class group of an imaginary quadratic function field are
discussed. For the real setting of a quadratic function field, we simplify the key exchange algorithm of [34].
We also improve on the signature schemes of [32] and [27] by shortening the signatures. Finally, we provide
a more rigorous and meaningful complexity analysis of these systems than [34, 32, 27] and investigate their
security and its relationship to the relevant discrete logarithm problems.
The fields we are considering are function fields k(C) of an elliptic or hyperelliptic curve C of genus g over
a finite field k of odd characteristic. If we write C in the form y is a polynomial
with coefficients in k, then (imaginary case) or 2g+2 (real case). While it is simple to
convert an imaginary representation to a real one (for example, by replacing D(t) by D(t \Gamma1 )t 2g+2 , noting
that k(t the reverse is only possible if D(t) has a root a 2 k (corresponding to a ramified rational
prime divisor of K=k(t); we then replace D(t) by D(t [29]). Hence the real setting is more
general. A preliminary investigation [30] suggests that the arithmetic underlying our cryptographic schemes
has approximately the same complexity and shows roughly equal practical performance in both the real and
the imaginary model. A choice of setting for conducting cryptography (real versus imaginary) would depend
on the performance issue as well as the question of how difficult the DLP is in either model. Currently, the
best known general algorithms for solving this problem are exponential in both cases.
In the next section, we summarize the necessary basics about quadratic function fields. All the required
algorithms and their complexities are stated in section 3. We present our cryptographic schemes in section
4 and analyze their security in section 5.
Quadratic Function Fields
For an introduction to function fields, we refer the reader to [39]. Quadratic function fields are discussed
in considerable detail in [6]. Let be a finite field of odd characteristic with q elements. A quadratic
function field is a quadratic extension K of the rational function field k(t) over k in the variable t. More
specifically, a polynomial in t
with coefficients in k which we may assume to be squarefree. K is (a) real (quadratic function field) if
degree deg(D) of D is even and the leading coefficient sgn(D) of D is a square in k. K is (an) imaginary
(quadratic function field) otherwise; that is, K is imaginary if deg(D) is odd or deg(D) is even and sgn(D)
is not a square in k. In the latter case, K is real quadratic over a quadratic extension of k, so we will
henceforth exclude this case. Elements in K have the form ff k(t). The conjugate of ff
is
If g denotes the genus of K, then K is an elliptic function field if a hyperelliptic function field if
? 1. Then imaginary. If K is real, then we can
"extract" a fixed square root
D of D in the field k((1=t)) of Puisseux series over k, so K  k((1=t)). In
this case, every nonzero element ff 2 K has a representation
and am 6= 0. We set
Denote by k[t] the ring of polynomials with coefficients in k in the variable t and let O = k[t] be the integral
closure of k[t] in K. Then O is a k[t]-module of rank 2 with basis f1;
Dg. An (integral O-)ideal a is a
subset of O such that for any ff; fi 2 a and ' 2 O, ff a and 'ff 2 a. A fractional (O-)ideal a is a subset
of K such that da is an integral ideal for some nonzero d 2 k[t]. Every fractional ideal a is an O-submodule
of K. If the O-rank of a is 1, i.e. there exists ff 2 K such that a = f'ff j ' 2 Og, then a is principal and ff
is a generator of a; write a = (ff).
Henceforth, all ideals (fractional and integral) are assumed to be nonzero, so the term "ideal" will always
be synonymous with "nonzero ideal". Then every integral ideal a is a k[t]-module of rank 2 with a k[t]-basis
Dg where We may assume
that S and Q are monic and, after subtracting a suitable multiple of Q from P , that deg(P
S, Q, and P are unique. a is primitive if primitive with Q monic and deg(P
then the pair (Q; P ) is the standard representation of a (see [30]; [36, 37] also use the term adapted basis),
and a is said to be in standard form. In practice, we will require the degree inequality deg(P
we will not insist on Q being monic. A primitive ideal a reduced if deg(Q)  g, the genus of K.
Hence every reduced ideal can be uniquely represented by a pair of polynomials
divides g. This "small" representation makes reduced ideals very suitable
for computation.
On the set I of (nonzero) fractional ideals of K, a multiplication is defined as follows. If a and b are fractional
ideals, then the product ab consists of all finite sums of products of the form fffi with ff 2 a and fi 2 b.
Under this multiplication, I is an infinite Abelian group with identity O. The set P of (nonzero) fractional
principal ideals is an infinite subgroup of I of finite index h 0 , the ideal class number of K. The factor group
is the ideal class group of K. Note also that the set of integral ideals is a sub-monoid of I. Two
fractional ideals a and b are equivalent if they lie in the same coset of C, i.e. a = (')b for some ' 2 K   .
The element ' is a relative generator of a with respect to b. Write a  b. Every equivalence class of ideals
contains at least one and at most finitely many reduced ideals. If K is imaginary, then each class has a
unique reduced representative [6]; however, if K is real, then there can be many reduced representatives in
each ideal class, in fact, as many as O(q g ) reduced ideals.
In the imaginary case, we base our cryptographic schemes on the arithmetic in the ideal class group C of K.
Each ideal class is represented by its reduced representative. The product of two reduced ideals is generally
not reduced; however, one can compute the reduced representative in the class of the product ideal quickly.
Thus, the set of reduced ideals is a monoid under the following operation   : given two reduced ideals a and
b, let a   b be the reduced ideal in the class of ab. The underlying discrete logarithm problem is the DLP in
the class group C: given reduced ideals d and g with d  g
Unfortunately, this approach fails in the real quadratic setting, due to the fact that there are many reduced
representatives in each ideal class. Here, we restrict ourselves to the finite subset R of P of reduced principal
ideals. More exactly, we define the distance ffi (a) of a reduced principal ideal a to be the degree of a generator
of minimal nonnegative degree. For n 2 N0, we call a the reduced principal ideal below n if
minimal. Then R is a monoid under the following operation: given two reduced principal ideals a and b, let
a   b be the ideal below (b). Here, the underlying DLP is the the following: given reduced principal
ideals d and g so that d is the reduced principal ideal below xffi(g), find x (mod R) where R is the maximal
distance or the regulator of K. We will see that this problem is polynomially equivalent to the problem of
finding the distance of a reduced principal ideal.
In both the imaginary and the real case, we require efficient algorithms for the following tasks:
ffl Given two reduced ideals in standard form, compute a standard representation of the product ideal.
ffl Given this product ideal, compute a reduced representative in its class.
In the real setting, we need to solve the additional problem:
ffl Given n 2 N, compute the reduced principal ideal below n.
Algorithms
In both the real and the imaginary models, the composition operation  , its implementation, and its complexity
have previously been studied in considerable detail. For the imaginary setting, we refer the reader
to [12], [29], and [30]. The real case is discussed in [36], [34], [32], and again [30]. A detailed complexity
analysis with explicit O constants can be found in [30]. To make this paper somewhat self-contained, we
restate the composition procedures here, but we only sketch proofs of correctness or performance.
Algorithms pertaining to just the imaginary setting have the prefix "I" in their name. Analogously, algorithms
that only apply to the real case begin with the letter "R". We use the complexity model of [30]; that is,
all complexity estimates will be stated in terms of elementary field operations of quadratic complexity,
such as multiplication and inversion of field elements. Here, we assume standard complexity estimates for
polynomial arithmetic as described for example on pp. 109f. of [13]; in particular, multiplication of two
polynomials of respective degrees m and n (m  n) requires O(mn) field operations, division with remainder
uses O(n(m field operations, and computation of extended gcd's takes O(m 2 ) field operations (see
also [30] for the last result).
Our first algorithm computes the product of two primitive ideals. It is valid in both the real and the
imaginary setting and the output will be in standard form.
Algorithm MULT (ideal multiplication, real and imaginary case)
Input: (Q a ; P a are two reduced ideals (the ideals are principal
in the real case).
primitive ideal in standard form (principal in the real case),
ab. In the imaginary case, S need not be output.
Algorithm:
1. T / gcd(Q a
2. If
else
3. Q c /
Proposition 3.1 The parameters c and S computed by Algorithm MULT satisfy
and the algorithm performs O(g 2 ) field operations.
Proof: The correctness of the algorithm is proved in Section II:2 of [36] for the real case and follows from [12]
for the imaginary case. The degree bounds follow from the fact that a and b are reduced and in standard
form. For the complexity result, see Proposition 5 of [30]. 2
Henceforth, we need to treat the imaginary and real settings separately. We begin with the imaginary
situation and first describe the composition operation   which computes the unique reduced representative
in the class of the product ideal ab, where a and b are two reduced ideals. The procedure uses two different
types of reduction steps. The first step is only used once at the beginning of the reduction process. If this
does not produce a reduced ideal, the second step, which is computationally more efficient than the first
step, is used subsequently, until a reduced ideal is obtained.
Algorithm I-RED-STEP1 (initial reduction step, imaginary case)
primitive ideal in standard form.
is an ideal equivalent to a in standard form and a =
Algorithm: Q+ / (D \Gamma P 2 )=Q; a /
\GammaP
Algorithm I-RED-STEP2 (subsequent reduction step, imaginary case)
Input: The output (Q; 2.
is an ideal equivalent to a in standard form and a =
Algorithm: Q+ /
\GammaP
(so again
We observe that for both reduction steps, deg(Q+ )
Algorithm I-COMPOSITION (ideal composition, imaginary case)
Input: (Q a ; P a are two reduced ideals in standard form.
is the reduced ideal equivalent to ab in standard form.
Algorithm:
1.
2. If deg(Q c ) ? g then
2.1
2.2
2.3 While deg(Q c ) ? g
2.3.1
Proposition 3.2 The ideal c computed by Algorithm I-COMPOSITION is the reduced ideal equivalent to
ab in standard form. Furthermore, the algorithm performs O(g 2 ) field operations.
Proof: For the correctness of the algorithm, see [12]. By Theorem 1 of [30], the complexity of the procedure
is
For our cryptographic schemes, we require an algorithm for "exponentiation" of reduced ideals. This method
is based on the standard repated squaring and multiplying technique used for ordinary exponentiation (see
for example Algorithm 1.2.3, p. 9, of [13]).
Algorithm I-EXP (exponentiation, imaginary case)
Input: (Q a ; P a ; n) where a = (Q a ; P a ) is a reduced ideal in standard form and n 2 N 0 .
is the reduced ideal equivalent to a
n in standard form.
Algorithm:
1. If
1.1
else
1.2 Compute the binary representation
1.3
1.4 For i / 1 to l do
1.4.2 If b
Proposition 3.3 The ideal computed by Algorithm I-EXP is the reduced ideal equivalent to a
n and the
algorithm performs O(maxf1; g 2 log ng) field operations.
We now proceed with the real setting. For brevity, we set
Dc, i.e. d is the polynomial part of a
(fixed) square root of D as defined in Section 2. As in the imaginary model, we will have two reduction
steps; the first one is to be applied immediately after ideal multiplication, while the second, more efficient
one is for subsequent use. Here the output ideal will not be in standard form, even if the input ideal is.
Recall that the reduced principal ideals form a finite set g. The reduction steps can
also be used to move from any ideal r i 2 R to the next reduced principal ideal r i+1 (1  applying
reduction to r m yields r 1 , so the movement through R is periodic.
If fQ represents a basis of a reduced ideal r i , then both reduction steps produce a reduced
representation of the next ideal r i+1 ; that is, deg(P
fact d and P i agree in their two highest coefficients [36].
In the real setting, all the reduced ideals produced by our algorithms are in reduced form. If a user prefers
ideals in standard form, he or she can easily convert the reduced representation (Q; P ) to a standard representation
by replacing P by P (mod Q), deg(P
Algorithm R-RED-STEP1 (initial reduction step, real case)
primitive principal ideal.
primitive principal ideal and P
Algorithm:
1. a /
2. P+ / d \Gamma
Algorithm R-RED-STEP2 (subsequent reduction step, real case)
Input: The output (Q; 2.
primitive principal ideal and P
Algorithm:
1. a /
2. P+ / d \Gamma
For both reduction steps, we have deg(Q+ ideal is not reduced.
So in this case, we again have deg(Q+ 2. If the input ideal is reduced, then the output ideal is
also reduced and in reduced representation; in particular deg(Q+
Let a 1 ; a be a sequence of primitive principal ideals where a i+1 is obtained by applying one of the
reduction steps to a i (i 2 N). For i  0, we associate with each ideal a
K. If we set
Y
then a is the conjugate of ' i . Since ff i ff
and hence for i 2
Our next algorithm shows how to obtain from any primitive principal ideal a reduced one. If the input ideal
is not reduced, then we simply apply reduction steps until we obtain a reduced ideal (Q; P ), i.e. deg(Q)  g.
Since each reduction step reduces the degree of Q by at least 2, this must eventually happen.
Algorithm R-REDUCE (ideal reduction, real case)
Input: (Q a ; P a ) where a = (Q a ; P a ) is a primitive principal ideal.
reduced principal ideal in reduced form and ffl is the degree of a
relative generator of b with respect to a.
Algorithm:
1.
2. If deg(Q b ) ? g, then
2.1 Q / Q a .
2.2
2.3 While deg(Q b ) ? g do
2.3.1
2.3.2 ffl
2.4 a /
Proposition 3.4 The ideal b computed by Algorithm R-REDUCE is a reduced principal ideal in reduced
form, and ffl is the degree of a relative generator of b with respect to a.
Proof: For the proof that b is a reduced principal ideal in reduced form, see [36]. Suppose the reduction
steps in the algorithm generate ideals a
i is minimal with deg(Q i )  g, so a i+1 is the first reduced ideal in the sequence. Then we have
at the end of the while loop, where ff At the end of the algorithm,
which is correct by (3.1). 2
be a sequence of reduced principal ideals, where as before, r i+1 is obtained by applying a
reduction step to r i (i 2 N). The relative distance from r i to r 1 is
. Then the relative distance ffi i;1 is a nonnegative function on the set R of reduced principal
ideals which strictly increases with i. Since deg(a
reduced representation of r i , (3.1) implies for
In particular, if r is a generator of minimal degree of r i . In this case, ffi simply
called the distance of r i and is denoted by ffi (r Hence, in general, we have
reduction steps, starting with r yield all of R.
is the regulator of K.
R. The reduced principal ideal below k is the unique reduced principal ideal r i with
then the ideal a   b is the reduced principal ideal below We point out
that the computation of a   b does not require knowledge of ffi (a) or ffi (b).
We will oftentimes need to advance from a reduced principal ideal a certain specified length in R. For
example, if we multiply two reduced principal ideals a and b using MULT and reduce the result using
R-REDUCE, then we still need to perform reduction steps until we actually reach the ideal a   b below
The next five algorithms give as output a reduced principal ideal together with its 'error' ffl in distance from
the input; that is, the difference between the distances of the input and the output ideals. This error will
always be an integer between \Gammag and 0. Note, however, that the ideal distances themselves are never used.
Algorithm R-ADVANCE (advancement in R, real case)
Input: (Q a ; P a ; a ) is a reduced principal ideal in reduced form and k 2 N 0 .
is the reduced principal ideal below reduced form and
Algorithm:
1.
2. If ffi  k, then
2.1
2.2 While ffi  k do
2.2.1
2.2.2
2.3 ffl
Proposition 3.5 The quantities b and ffl computed by Algorithm R-ADVANCE are, respectively, the reduced
principal ideal below ffi (a)+k and the value of ffi (b; a)\Gammak. Furthermore, the algorithm performs O(g \Delta maxfk; gg)
field operations.
Proof: In each step, the value of ffi is the relative distance from the ideal with basis (Q to a by (3.2).
So the final ideal b has maximal distance such that ffi (b; a)  k and is thus the reduced principal ideal below
Now the degrees of P a , Q a , and d are all bounded by g + 1, so step 2.1 requires O(g 2 ) field operations. Since
by (3.2), each reduction step advances the value of ffi by at least 1, the loop in step 2.2 is executed at most
k times (provided k ? 0). Each reduction step in step 2.2.1 performs O(g deg(a)) operations. By (3.2), the
sum of the degrees of all the a values is O(ffi(b; O(k). So the total number of operations performed in
step 2 is O(gk). 2
We note that one could slightly improve algorithm R-ADVANCE by replacing the reduction step in step
2.2.1 by a call of R-RED-STEP2 and adding the appropriate inputs to the algorithm. We avoided this here
in order to keep the description of the algorithm simpler and more transparent.
Algorithm R-COMPOSITION (ideal composition, real case)
Input: (Q a ; P a are two reduced principal ideals.
is in reduced form and
Algorithm:
1.
2.
3.
Proposition 3.6 Algorithm R-COMPOSITION computes the reduced principal ideal a   b below
and the quantity (b). Furthermore, the algorithm performs O(g 2 ) field operations.
Proof: Let ~ c be the ideal generated by step 2. Then computes the ideal
below ffi (~ c) which is a   b, and the correct value of ffl. Since 0
(see [36]), step 3 performs at most 2g reduction steps by (3.2). In fact, according to [30], the algorithm
performs 21g 2 +O(g) field operations. 2
The complexity results in the proofs of Propositions 3.2 and 3.6 show that composition in the real and the
imaginary model perform at essentially the same speed. A computer implementation by the authors of [30]
confirms that the same is true for the performance of both composition operations in practice.
Using repeated applications of Algorithm R-PRODUCT in combination with R-ADVANCE, we can adapt
the binary exponentiation technique mentioned earlier to compute for a reduced principal ideal a and an
the reduced ideal below nffi(a).
Algorithm R-EXP (exponentiation, real case)
Input: (Q a ; P a ; n) where a = (Q a ; P a ) is a reduced principal ideal in reduced form and n 2 N 0 .
is the reduced principal ideal below nffi(a) in reduced form and
Algorithm:
1. ffl / 0.
2. If
2.1
else
2.2 Compute the binary representation
2.3
2.4 For i / 1 to l do
2.4.1
2.4.2
2.4.3 If b
2.4.3.1
2.4.3.2
Proposition 3.7 The ideal computed by Algorithm R-EXP is the reduced principal ideal below nffi(a). Fur-
thermore, the algorithm performs O(maxf1; g 2 log ng) field operations.
Proof: We first observe that (1; d) is the reduced representation of O which is the reduced principal ideal
below nffi(a) for Assume now that n ? 0 and set s
to show that at the end of the i-th iteration of the for loop, b is the reduced
principal ideal below s i ffi (a) and ffl
is correct. Now consider the (i 1)-st iteration of the for loop. Step 2.4.1 produces the reduced principal
ideal b below 2ffi(b i ) and 2.4.2 generates the reduced principal ideal ~ b below
and
which is correct. Suppose b
the reduced principal ideal " b below
Finally, step 2.4.3.2 generates the
reduced principal ideal b i+1 below
and
Now \Gammag  ffi; ffl  0 for the values of ffi and ffl throughout the algorithm, so each R-ADVANCE call advances
a distance of O(g). Hence the complexity result follows from Propositions 3.6 and 3.5. 2
Using the previous algorithm, we can now generate the reduced principal ideal below any nonnegative integer
k. Here, we make use of the fact that if r d) (in reduced form), then r d) with distance
g, then we first compute the reduced principal ideal
using R-EXP on the base ideal r 2 and the exponent n. Then we apply reduction
steps until we reach the reduced principal ideal
Algorithm R-BELOW (generates an ideal of specific distance, real case)
Output: (Q; is the reduced principal ideal below k and
Algorithm:
1. n /
2. (Q a ; P a
3. (Q;
Proposition 3.8 Algorithm R-BELOW computes the reduced principal ideal r below k and the quantity
k. Furthermore, the algorithm performs O(g 2 log field operations.
Proof: We have
4 Cryptographic Schemes
We now present three cryptographic schemes for both real and imaginary of quadratic function fields, namely
a key exchange protocol, a public-key system, and signature scheme. Each system uses the "exponentiation"
method corresponding to the composition operation. The field K should be chosen so that q g is large. More
details on the choice of the field will be given in the next section. For simplicity, we specify the generating
polynomial to be monic.
We begin with the imaginary case. All our schemes require the following precomputation.
I-PRECOMPUTATION (precomputation, imaginary case)
1. Generate an odd prime power q,
2. generate a random squarefree monic polynomial D 2 F q [t] of odd degree,
3. generate a random ideal
4. publicize (q; D; Q; P ).
KEY EXCHANGE PROTOCOL (imaginary case)
Precomputation: Alice and Bob jointly obtain (q; D; Q; P ) by performing I-PRECOMPUTATION.
Protocol:
1. Alice
1.1 secretly generates an integer a, 0 ! a ! q bg=2c ,
1.2 computes (Q a ; P a ) / I-EXP(Q;
1.3 transmits (Q a ; P a ) to Bob.
2. Bob
2.1 secretly generates an integer b,
2.2 computes (Q
2.3 transmits (Q b ; P b ) to Alice.
3. Alice computes (Q
4. Bob computes (Q
parties have now computed the
unique reduced ideal equivalent to r
ab in standard form. They can use the polynomials (Q
previously agreed upon portion thereof) as their key. Since a and b are reduced and in standard form, both
parties transmit approximately 2g log q bits of information.
PUBLIC-KEY CRYPTOSYSTEM (imaginary case)
Key Generation:
All participants jointly obtain (q; D; Q; P ) by performing I-PRECOMPUTATION.
Each participant
1. secretly generates an integer a, 0 ! a ! q bg=2c ,
2. computes (Q a ; P a ) / I-EXP(Q;
3. makes (Q a ; P a ) the public key and a the secret key.
Encryption: To encrypt a message M , the sender (with secret key s)
1. looks up the recipient's public
2. computes (Q
3. repeat
3.1 generates the bit string x 2 N obtained by concatenating the coefficients in F q of the polynomial
3.2 removes the first block m with
3.3 sends the ciphertext m \Phi x (the bitwise "exclusive or"of m and x),
until all of M encrypted.
Decryption: To decrypt a ciphertext C, the recipient (with secret key r)
1. looks up the sender's public key (Q
2. computes (Q
3. repeat
3.1 generates the bit string x 2 N obtained by concatenating the coefficients in F q of the polynomial
3.2 removes the first block c with c ! x from C,
3.3 computes m / c \Phi x,
until all of C is decrypted,
4. concatenates all the blocks m to obtain the plaintext M .
Once again (Q parties compute the same reduced ideal (Q
thus the same polynomial Q k and bit string x. Since deg(Q k )  g, each block c of ciphertext is approximately
log q bits long.
Our next scheme requires a collision-resistant one-way hash function hash that takes as input a message M
and the polynomials Q and P of a reduced ideal (in standard form) and produces positive integer values not
exceeding q bg=2c . The inputs of this hash function can also be thought of as bit strings, if we concatenate
M , Q, and P . The idea of using a hash function as described above was first presented in [27], where it was
used for a signature scheme based on a real quadratic function field of characteristic 2.
SIGNATURE SCHEME (imaginary case)
Precomputation:
All participants jointly
1. obtain (q; D; Q; P ) by performing I-PRECOMPUTATION.
2. agree on a cryptographically secure hash function hash : N \Theta F q [t] g \Theta F q [t]
(here, F q [t] m denotes the set of polynomials in F q [t] of degree at most m).
Each participant
1. secretly generates an integer a, 0 ! a ! q bg=2c ,
2. computes (Q a ; P a ) / I-EXP(Q;
3. makes (Q a ; P a ) the public key and a the secret key.
Signature Generation: To sign a message M , the signer (with secret key a)
1. secretly generates an integer r,
2. computes (Q r
3. computes m /
4. computes s / r \Gamma ma,
5. sends the signature (Q along with the message M .
Signature Verification: To verify the signature (Q s) to the message M , the verifier
2. computes (Q
3. looks up the senders public key (Q a ; P a ),
4. computes (Q
5. computes (Q r
6. accepts the signature if and only if Q r 0
To show that the verification procedure is correct, we first observe that if ( ~
P) is any reduced ideal, then
P ) is the reduced representative of the ideal class that is the inverse in the class group C of the ideal
class of ( ~
is clear that ( ~
reduced and in standard form, and multiplying ( ~
using algorithm MULT gives as result the ideal O = (1; 0).
Now we have (Q
To forge a signature, an adversary needs to generate a reduced ideal and an integer s such
that (Q; P It is necessary to use the hash function to prevent the following
attack. Suppose we replaced by a message block m where . Then an
adversary can simply pick a random positive integer s and compute the reduced ideal (Q r ; P r ) equivalent to
Such a forged signature (Q would always be accepted by the verifier. The hash
function forces the signer to generate the reduced ideal (Q r ; P r ) before computing s, rather than making it
possible to choose s first and then generate a "fitting" reduced ideal (Q r ; P r ).
, so the transmission of a signature requires approximately
3g log q bits of information. Signatures can be somewhat shortened by imposing a smaller upper bound on
a and m.
We now continue with cryptographic schemes in the real setting. Some of the schemes require a participant to
generate a reduced principal ideal together with its distance. The easiest way to achieve this is to generate a
random nonnegative integer a of desired size and compute (Q a ; P a
The schemes also require the precomputation of
Dc. This can be done using a Puisseux diagram (see
[23]). Once again, we there is a common precomputation to all schemes.
R-PRECOMPUTATION (precomputation, real case)
1. Generate an odd prime power q,
2. generate a random squarefree monic polynomial D 2 F q [t] of even degree,
3. compute d / b
Dc,
4. publicize (q; D; d).
The protocol given below is a slight improvement over the versions given in [34] and [27] in that it eliminates
the need for including a reduced ideal in the set of public parameters.
KEY EXCHANGE PROTOCOL (real case)
Precomputation: Alice and Bob jointly obtain (Q; D; d) by performing R-PRECOMPUTATION.
Protocol:
1. Alice
1.1 secretly generates a reduced principal ideal a = (Q a ; P a ) with distance
1.2 transmits (Q a ; P a ) to Bob.
2. Bob
2.1 secretly generates a reduced principal ideal
2.2 transmits (Q b ; P b ) to Alice.
3. Alice computes (Q
4. Bob computes (Q
Both parties compute the reduced principal ideal (Q (a)ffi(b). They can use Q k and P k (or
any previously agreed upon portion thereof) as their key. As in the imaginary case, both parties transfer
approximately 2g log q bits of information.
PUBLIC KEY CRYPTOSYSTEM (real case)
Key Generation:
All participants jointly obtain (Q; D; d) by performing R-PRECOMPUTATION.
Each participant
1. secretly generates a reduced principal ideal a = (Q a ; P a ) with distance
2. makes (Q a ; P a ) the public key and ffi (a) the secret key.
Encryption: To encrypt a message M , the sender (with secret key ffi (s))
1. looks up the recipient's public
2. computes (Q
3. repeat
3.1 generates the bit string x 2 N obtained by concatenating the coefficients in F q of the polynomial
3.2 removes the first block m with
3.3 sends the ciphertext m \Phi x (the "exclusive or"of m and x),
until all of M is encrypted.
Decryption: To decrypt a ciphertext C, the recipient (with secret key ffi (r))
1. looks up the sender's public key (Q
2. computes (Q
3. repeat
3.1 generates the bit string x 2 N obtained by concatenating the coefficients in F q of the polynomial
3.2 removes the first block c with c ! x from C,
3.3 computes m / c \Phi x,
until all of C is decrypted,
4. concatenates all the blocks m to obtain the plaintext M .
Both parties compute the reduced principal ideal (Q thus the same polynomial Q k
and bit string x. Again each block c of ciphertext is approximately g log q bits long.
Our next scheme is an improvement over the signature scheme of [27] in that it generates shorter signatures.
Once again, we use a cryptographically secure hash function similar to the one used in the corresponding
scheme in imaginary fields (the signature scheme of [32] failed to take this into consideration).
Precomputation:
All participants jointly
1. obtain (Q; D; d) by performing R-PRECOMPUTATION.
2. agree on a cryptographically secure hash function hash : N \Theta F q [t] g \Theta F q [t] g.
Each participant
1. generates a reduced principal ideal a = (Q a ; P a ) with distance
2. makes (Q a ; P a ) the public key and ffi (a) the secret key.
Signature Generation: To sign a message M , the signer (with secret key ffi (a))
1. secretly generates a reduced principal ideal r with distance
2. computes m /
3. computes s /
4. sends the signature (Q along with the message M .
Signature Verification: To verify the signature (Q s) to the message M , the verifier
2. computes (Q
3. looks up the sender's public key (Q a ; P a ),
4. computes (Q
5. if s  0 then
5.1 computes (Q
5.2 computes (Q r
5.3 accepts the signature if and only if Q r
else
5.4 computes (Q
5.6 accepts the signature if and only if Q b 0
Once again, we check the verification procedure. Write
first that s  0. Then we have
r
0 is the reduced principal ideal below
Now assume that s ! 0. Then
0 is the reduced principal ideal below
To forge a signature (Q r ; P r ; s), an opponent must generate a reduced principal ideal and an
integer s with the following properties. If s  0, then r is the reduced principal ideal below s+mffi(a). If s ! 0,
then b is the reduced principal ideal below s. The similarities in these two cases are best seen as follows.
Let (s; ffi ) be as in step 2 of the verification procedure. If s  0, write
so must be such that r has distance at most 2g below
\Gammag  must be such that b has distance within g of r   s.
so the transmission of a signature again requires at most
3g log q bits of information. The signatures in [27] are between 3g log q and 4g log q bits long. Once again,
signatures could be shortened by imposing tighter bounds on ffi (a) and m.
Before we discuss possible attacks on our cryptographic schemes, we explore the size of our underlying sets.
We need to ensure that the class group C (in the imaginary setting) and the set R of reduced principal ideals
(in the real setting) are sufficiently large.
The order of C is simply the ideal class number h 0 . Consider now the real case and let
is the regulator of the field. So the size of R is determined by the size of R (in the elliptic
case, we even have h be the order of the Jacobian J of the curve C defining the function field
K. Then
ae h 0 in the imaginary case
Rh 0 in the real case
(see [40]). It is well-known (see for example Theorem V.1.15, p. 166, of [39]) that
is the L polynomial of Kjk. Here,
is an algebraic integer
of absolute value p q by the Hasse-Weil Theorem (see Theorem V.2.1, p. 169, of [39]). It follows that
This means that in an imaginary field, there are approximately q g ideal classes in C. Analyzing the size of
R in the real case is slightly more complicated. To ensure a large regulator, we need to make h 0 as small
as possible. A strong heuristic argument ([34], also Section 3.4.1, pp. 107-111, of [37]), analogous to the
Cohen-Lenstra heuristic in real quadratic number fields [14, 15]), shows that the probability that the order
of the odd part of the ideal class group exceeds x is 1=2x +O((log x)=x 2 ). In fact, in the elliptic case, there
is very strong numerical evidence that ideal class groups behave according to this heuristic [19, 20], and it
can be proved that for sufficiently large q, the probability that h At the same time, it is
easy to find real fields whose ideal class number is odd; for example, by a result of Zhang [41], it suffices to
choose D to be irreducible over k or the product of two odd-degree irreducibles in k[t]. Hence under these
choices, h 0 is small with high probability, and there are close to q g reduced principal ideals in K.
Hence to foil an exhaustive search attack, we should ensure that q g is sufficiently large. Considerations for
good choices of q and g are discussed below, but we point out that within these considerations, users can
take advantage of the following trade-off. For small q and large g, our complexity analysis in section 3 results
in very good performance in terms of field operations, but field arithmetic will dominate our computation
times. If g is small and q is large, then field arithmetic will be very fast, but the number of field operations
performed by our algorithms will increase. Thus, one could select q and g in such a way as to optimize
performance, while ensuring a sufficient level of security in our systems.
We now explore the possibility of breaking our schemes. We begin with the imaginary model. Here, the
relevant problem underlying all three schemes is the DLP in the class group C of K: given two ideals g and
d with d  g
x for some x 2 f0; find the discrete logarithm x. It is obvious that for any of
the schemes, there is a polynomial-time reduction from an algorithm for solving the DLP to an algorithm
for breaking the system. Since no other way of compromising any of the schemes is known, we focus our
attention on the difficulty of the DLP in C.
The ideal class group C is isomorphic to the Jacobian J , and the DLPs in C and J are polynomially
equivalent. We first observe that in certain cases, the DLP in the Jacobian of an elliptic or hyperelliptic
curve is reducible to the DLP in a finite field, in which case using (hyper)elliptic function fields represents no
advantage over using finite fields for the implementation of discrete logarithm based cryptosystems. More
exactly, the curve C should not be supersingular [25], and the largest prime divisor of h 0 should not divide
small k for which the DLP in F q k is feasible [18]. It is currently unknown whether such
reductions are possible in situations other than those cited above.
In [4], a probabilistic algorithm for computing discrete logarithms in J in the case where q is a prime is
given. This technique is subexponential of complexity exp(c
log q g log log q g ) where c ? 0 is a constant,
small compared to g. The algorithm may be generalizable to odd prime
powers q, but seems infeasible in practice for sufficiently large parameters, and one could foil an attack based
on this method by choosing q to be large and the genus g to be small.
In general, a technique analogous to that of Pohlig-Hellman [31] can be used to compute discrete logarithms
in C. The complexity of this method is essentially of order p p where p is the largest prime factor of h 0 . This
attack requires that h 0 be known. A technique described in [24] can be used to compute h 0 by generating the
coefficients of the L polynomial L(t); this method works particularly well for small g. Another algorithm for
computing (among other quantities) h 0 given in [3] is polynomial in the size of q and exponential in g. Hence,
while it might be feasible to determine h 0 , particularly for small g, the Pohlig-Hellman attack is infeasible
unless h 0 is smooth, i.e. has only small prime factors.
In the real setting, there are two problems that are relevant to possible attacks on our cryptoschemes. The
distance problem (DP) in R requires the computation of the distance of a reduced principal ideal. The DLP
in R is the problem of finding x (mod R), given reduced principal ideals g and d where d is the reduced
principal ideal below xffi(g). Both problems are equally difficult; hence, the problem of breaking any of our
schemes is polynomial-time reducible to either problem.
Proposition 5.1 There is a polynomial-time reduction from the DLP to the DP and vice versa.
Proof: Suppose first that we can solve any instance of the DLP. Let r be a reduced principal ideal. We wish
to find ffi (r). Let ffi g. Let r
0 be the ideal below (y
Suppose the call R-ADVANCE(Q r sequence a
reduced principal ideals which we store in memory. Then (3g 1. Now by (5.2):
hence
g. Using the
use our DLP algorithm to determine from the ideal r d) with distance
and the reduced principal ideal r
below yffi 2 the discrete logarithm y 2. Of these of our DLP
procedure, one will give a correct answer for y might give a wrong or meaningless
answer or no answer at all). We now have
us
can check which one of these candidates is the correct one by using the following simple technique. If l is a
candidate for ffi (r), compute (Q;
Assume now that we know how to compute distances and let g and d be reduced principal ideals such that
d is the reduced principal ideal below xffi(g) for some x 2 N 0 . Our task is to find x (mod R). First compute
bounds uniquely determine the integer x. If ffi (g)  g, then O, in which case
Clearly, our three systems are broken if there is a fast algorithm for the DLP or the DP. The difficulty of
the DLP was already discussed in [34], so we briefly repeat the arguments here. It was shown in [37, 38]
that there is a simple bijection from to the set f0; of multiples
of P (except P itself) that maps r 1 onto 0 and r i onto iP for 2  i  m. Here, P is a point on a certain
elliptic curve over F q . Consequently, there is a polynomial-time reduction from the DLP in R to the DLP
in the group of points on the elliptic curve: given two points P and Q on the curve with
then there is also a polynomial-time reduction in the opposite direction, so
the DLP for elliptic real function fields of characteristic not equal to 3 is polynomially equivalent to the DLP
for elliptic curves over a finite field. Since the best known algorithm for computing discrete logarithms on an
elliptic curve over a finite field F q has complexity of order p q, provided the curve is not supersingular, we
require at this point exponential time to compute discrete logarithms in the set of reduced principal ideals
of an elliptic function field.
For hyperelliptic real fields, there is no equivalence of the type discussed above. Here, the best known
general algorithms for computing both discrete logarithms and the regulator R of the field are of complexity
O(q (2g\Gamma1)=5 ) (see Theorem 2.2.33, p. 78, of [37]). If log q  2g small compared to g,
then discrete logarithms, including the regulator, can be computed probabilisticly in subexponential time
exp(c
log q g log log q g ) where c ? 0 is a constant ([26], Theorem 6.3.2, p. 203, of [37]). The algorithm does
not appear feasible in practice; nevertheless, to be safe, one might again wish to choose q to be large relative
to g. The computations in [34] show that the elliptic case performed best computationally; for a 50
digit prime q, a call of R-EXP with a 50 digit exponent required 3.76 seconds on a Silicon Graphics Challenge
workstation, and further optimization of this implementation will undoubtedly produce faster running times.
A Pohlig-Hellman-like technique for computing discrete logarithms in a real quadratic function field of
characteristic 2 described in considerable detail in [27] can easily be adapted to work in real fields of odd
characteristic. The algorithm requires knowledge of the regulator R, and as usual, its running time is
essentially the square root of the largest prime factor of R. Once again, this method does not pose a threat
to our cryptographic schemes at this time if q g is sufficiently large (100 decimal digits seems more than
sufficient with current computer technology) and R is not smooth.
Thus, if the parameters are chosen with some care, the fastest currently known methods for breaking our
schemes are all exponential. This is in contrast to systems based on discrete logarithms in finite fields where
the DLP is subexponential [2], as well as the corresponding systems in quadratic number fields (both real and
imaginary), where the relevant DLPs can also be solved in subexponential time [22, 1]. Thus, our systems
might well be more secure. Our real key exchange protocol is also significantly faster than the corresponding
scheme in real quadratic number fields [11, 33] (see our computations in [34]), although we have no data
available as to how our systems would perform relative to elliptic curve systems such as [5].
Unfortunately, in some instances, more information needs to be transmitted than in the original Diffie-Hellman
and ElGamal systems. Let l be the size of the underlying set, i.e. for the original
Diffie-Hellman and ElGamal schemes over a finite field F p and l  g g for our schemes. Diffie-Hellman keys
require log l bits of transmission, whereas our keys are twice as long. Similarly, ElGamal signatures have
size 2 log l, while our signatures are up to 3 log l bits long. However, as mentioned before, they can be made
shorter, say 2 log l bits as well, if we reduce our upper bound on our parameters from q g=2 to q g=4 . Even
with these smaller quantities, we consider the schemes secure.



--R

Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ord- nungen
A subexponential algorithm for discrete logarithms over all finite fields.
Counting rational points on curves and Abelian varieties over finite fields.
A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields.

Quadratische Korper im Gebiete der hoheren Kongruenzen I
Cryptographic protocols based on real-quadratic A-fields (ex- tended abstract)
Cryptographic protocols based on discrete logarithms in real-quadratic orders



Computing in the Jacobian of a hyperelliptic curve.
A Course in Computational Algebraic Number Theory.
Heuristics on class groups.
Heuristics on class groups of number fields.
New directions in cryptography.
A public-key cryptosystem and a and a signature scheme based on discrete logarithms
A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves
A special case of Cohen-Lenstra heuristics in function fields
Class group frequencies of real quadratic function fields: the degree 4 case.

A rigorous subexponential algorithm for computation of class group.
Theorie der Algebraischen Funktionen einer Veranderlichen.
Reducing elliptic curve logarithms to logarithms in a finite field.
Computing discrete logarithms in real quadratic congruence function fields of large genus.
Discrete Logarithm based cryptosystems in quadratic function fields of characteristic 2.
National Institute for Standards and Technology
Real and Imaginary Quadratic Representations of Hyperelliptic Function Fields.
Comparing real and imaginary arithmetics for divisor class groups of hyperelliptic curves.
An improved algorithm for computing logarithms over GF (p) and its cryptographic significance.
Cryptography in real quadratic congruence function fields.
A key exchange protocol using real quadratic fields.

The infrastructure of a real quadratic field and its applications.
Baby step-Giant step-Verfahren in reell-quadratischen Kongruenzfunktionenkorpern mit Charakteristik ungleich 2
Algorithmen in reell-quadratischen Kongruenzfunktionenkorpern
Equivalences between elliptic curves and real quadratic congruence function fields.
Algebraic Function Fields and Codes.
Artins Theorie der quadratischen Kongruenzfunktionenkorper und ihre Anwendung auf die Berechnung der Einheiten- und Klassengruppen
Ambiguous classes and 2-rank of class groups of quadratic function fields
--TR
A key-exchange system based on imaginary quadratic fields
Hyperelliptic cryptosystems
A key exchange system based on real quadratic fields
A remark concerning <italic>m</italic>-divisibility and the discrete logarithm in the divisor class group of curves
A course in computational algebraic number theory
Key-Exchange in Real Quadratic Congruence Function Fields
Discrete Logarithm Based Cryptosystems in Quadratic Function Fields of Characteristic 2
Computing discrete logarithms in real quadratic congruence function fields of large genus
Real and imaginary quadratic representations of hyperelliptic function fields
Class group frequencies of real quadratic function fields
Cryptographic Protocols Based on Discrete Logarithms in Real-quadratic Orders
Cryptographic Protocols Based on Real-Quadratic A-fields
A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields
Counting Rational Points on Curves and Abelian Varieties over Finite Fields
Comparing Real and Imaginary Arithmetics for Divisor Class Groups of Hyperelliptic Curves

--CTR
Ian F. Blake , Theo Garefalakis, On the complexity of the discrete logarithm and Diffie-Hellman problems, Journal of Complexity, v.20 n.2-3, p.148-170, April/June 2004
ElGamal signature scheme;quadratic function field;public key cryptosystem;diffie-hellman key exchange protocol;discrete logarithm