Sieving is the ¬rst and major phase of the fastest problem) in ideal class groups of quadratic number

general algorithms for integer factoring and for ¬elds). The basic idea of sieving in function ¬elds

solving the discrete logarithm problem. Here, the is to ¬nd a good representation of polynomials by

candidates sought are those that are divisible only integers, which allows one to “jump” from one poly-

by small primes or their equivalent (see smooth- nomial to another, and to increment the exponent

ness and factor base). Speci¬c examples of sieving in the cell of a three dimensional matrix. All the

are described further in the entries Number Field other optimizations known from the number ¬eld

Sieve, Quadratic Sieve, sieving in function ¬elds, sieve could then be applied. Later, Smart [9] com-

and index calculus. See also TWIRL for a recent pared the Hafner-McCurley variant with the orig-

design for ef¬cient sieving in hardware. inal, theoretically faster, Adleman“De Marrais“

Huang variant which allows one to construct

Burt Kaliski

sparse systems of linear equations, therefore being

better suited for curves of larger genus (the genus

basically being the size of the discriminant of the

SIEVING IN FUNCTION function ¬eld). It turned out that the size of the

FIELDS cryptosystems N.P. Smart experienced with was

still too small. Later on, N.P. Smart implemented

the sieving technique for superelliptic cryptosys-

Function ¬elds are analogous constructions to

tems (where the degree of the corresponding func-

number ¬elds, where the role of the integers is

tion ¬eld is at least 3) based on a joint work with

replaced by polynomials. The coef¬cients of these

Galbraith and the author [5]. None of these im-

polynomials are elements of ¬nite ¬elds for all

plementations was ever even close to the size real

cryptographically relevant applications. But in

cryptosystems would use, but no one ever started

contrast to number ¬elds, function ¬elds over ¬-

a massively parallel project as for the number

nite ¬elds (so they are called) have interesting

¬eld sieve for these types of cryptosystems. As

properties, notably concerning smoothness of el-

a consequence, one cannot sincerely decide about

ements, an important topic for sieving.

the practical usefulness of hyperelliptic cryptosys-

Notably, there exists a provable bound for the

tems.

necessary size of a factor base, a set of elements

This is very different to the other application

generating a larger, targeted set of elements to be

of sieving in function ¬elds: namely, to compute

factored. This is due to the fact that the analog of

578 Signcryption

the discrete logarithm in a ¬nite ¬eld. This can [4] Flassenberg, R. and S. Paulus (1999). “Sieving

in function ¬elds.” Experimental Mathematics, 8,

be done by constructing for a given ¬nite ¬eld a

339“349.

function ¬eld with the following property: there

[5] Galbraith, S.D., S. Paulus, and N.P. Smart (2001).

is an embedding of subgroups of the multiplica-

“Arithmetic on superelliptic curves.” Mathematics

tive group of the ¬nite ¬eld into the Jacobian of a

of Computation, 71, 393“405.

curve corresponding to the ¬eld. This mapping has

[6] Hafner, James L. and Kevin S. McCurley (1991).

been used for applying the Adleman-De Marrais- “Asymptotically fast triangularization of matrices

Huang result to ¬nite ¬elds with small character- over rings.” SIAM Journal of Computer, 20 (6),

istic and high degree, resulting in a subexponen- 1068“1083.

tial algorithm for discrete logarithms in this type [7] Joux, A. and R. Lercier (2002). “The function ¬eld

of ¬eld [2]. Since solving discrete logarithms in ¬- sieve is quite special.” Proceedings of ANTS-V, Lec-

nite ¬elds is of general interest, especially for ¬- ture Notes in Computer Science, vol. 2369, eds.

C. Fieker and D.R. Kohel. Springer-Verlag, Berlin,

nite ¬elds with characteristic 2, there are a few

431“445.

implementations of these algorithms.

[8] Koblitz, N. (1989). “Hyperelliptic cryptosystems.”

An important point is how the function ¬eld

Journal of Cryptology, 1 (3), 139“150.

is constructed. Whereas Adleman and Huang [2]

[9] Smart, N.P. (1999). “On the performance of hyper-

were looking for the most simple representation

elliptic cryptosystems.” Advances in Cryptology”

for an optimal performance of the necessary func- EUROCRYPT™99, Lecture Notes in Computer Sci-

tion ¬eld arithmetic, Joux and Lercier in 2001 ence, vol. 1592. Springer-Verlag, Berlin, 165“175.

[7] generalized this approach to get better asym- [10] Thome, E. (2001). “Computation of discrete log-

potic running times. They proved their theoreti- arithms in GF(2607 ).” Advances in Cryptology”

cal result by solving a discrete logarithm in the ASIACRYPT 2001, Lecture Notes in Computer

¬nite ¬eld of size 2521 in approximately one month Science, vol. 2248, ed. C. Boyd. Springer-Verlag,

Berlin, 107“124.

on one machine. Moreover, they showed that the

specialized algorithm of Coppersmith [3], which

holds the actual discrete logarithm record (in a

SIGNCRYPTION

¬eld of size 2607 ), is a special case of their algo-

rithm in the case of characteristic 2. But since the

INTRODUCTION: Encryption and digital signa-

record computation, done by Thome in 2001 [10],

was performed using massively parallel computa- ture schemes are fundamental cryptographic tools

tions for collecting relations in the sieving part for providing privacy and authenticity, respec-

of the algorithm, there is still room for practical tively, in the public-key setting. Traditionally,

improvements of the computation of discrete log- these two important building-blocks of public-

arithms by using Joux™ and Lercier™s ideas. Es- key cryptography have been considered as dis-

pecially, there are no known practically relevant tinct entities that may be composed in various

results for characteristics different from 2 as of ways to ensure simultaneous message privacy and

this writing. authentication. However, in the last few years

a new, separate primitive”called signcryption

Sachar Paulus

[14]”has emerged to model a process simulta-

neously achieving privacy and authenticity. This

References

emergence was caused by many related reasons.

The obvious one is the fact that given that both pri-

[1] Adleman, L.M., J. De Marrais, and M.-D. Huang

vacy and authenticity are simultaneously needed

(1994). “A subexponential algorithm for discrete

in so many applications, it makes a lot of sense

logarithms over the rational subgroup of the

to invest special effort into designing a tailored,

Jacobian of large genus hyperelliptic curves over ¬-

nite ¬elds.” ANTS-1: Algorithmic Number Theory, more ef¬cient solution than a mere composition of

Lecture Notes in Computer Science, vol. 877, eds. signature and encryption. Another reason is that

L.M. Adleman and M.-D. Huang. Springer-Verlag, viewing authenticated encryption as a separate

Berlin, 28“40. primitive may conceptually simplify the design of

[2] Adleman, L.M. and M.-D. Huang (1999). “Function

complex protocols which require both privacy and

¬eld sieve method for discrete logarithms over ¬-

authenticity, as signcryption could now be viewed

nite ¬elds.” Information and Computation, 151, 5“

as an “indivisible” atomic operation. Perhaps most

16.

importantly, it was noticed by [2,3] (following some

[3] Coppersmith, Don (1984). “Fast evaluation of Log-

previous work in the symmetric-key setting [4,10])

arithms in Fields of Characteristic Two, IEEE.

that proper modeling of signcryption is not so obvi-

Transaction on Information Theory, vol. IT-30 (4),

ous. For example, a straightforward composition of

587“594.

Signcryption 579

signature and encryption might not always work; an ordinary digital signature. For example, one

at least, unless some special care is applied [2]. can talk about indistinguishability of signcryp-

The main reason for such dif¬culties is the fact texts under chosen ciphertext attack, or existen-

that signcryption is a complex multi-user primi- tial unforgeability of signcryptexts under chosen

tive, which opens a possibility for some subtle at- message attack, among others. For concreteness,

tacks (discussed below), not present in the settings we concentrate on the above two forms of security

of stand-alone signature and encryption. too, since they are the strongest.

However, several new issues come up due to

De¬ning Signcryption the fact that signcryption/designcryption take as

an extra argument the identity of the sender/

recipient. Below, we semiformally introduce some

Syntactically, a signcryption scheme consists

of those issues (see [2] for in-depth technical dis-

of the three ef¬cient algorithms (Gen, SC, DSC).