---

Cryptography & Number Theory /Cryptographie et Théorie des nombres
(Hugh Williams and Gary Walsh, Organizers)

---

DAN BERNSTEIN, University of Illinois at Chicago, Chicago, Illinois, USA
Sieving in cache

Modern integer factorization algorithms do not need as much memory for sieving as is commonly believed. This talk will explain how tomorrow's factoring projects can take advantage of fast arithmetic on stupendously large integers.

TOM CUSICK, Department of Mathematics, State University of New York at Buffalo, Buffalo, New York  14214, USA
Boolean functions and cryptography

Boolean functions with special features are important in cryptography. The talk will survey some relevant properties and the progress which has been made in constructing Boolean functions with these properties.

JOHN FRIEDLANDER, University of Toronto, Toronto, Ontario  M5S 3G3
Carmichael's function and the power generator

We discuss recent joint work with C. Pomerance and I. Shparlinski on bounds for the frequency of large and small values of the Carmichael function and of the relevance of such bounds for the distribution of the power generator of pseudorandom numbers.

ROB LAMBERT, Certicom Corporation, 5520 Explorer Drive, Mississauga, Ontario  L4W 5L1
Solution of linear systems for discrete logarithm calculation

Integer factorization and discrete logarithm calculation are important to public key cryptography. The most efficient known methods for these problems require the solution of large sparse linear systems, modulo two for the factoring case, and modulo large primes for the logarithm case. This talk is concerned with solving these equations modulo large primes.

A solution method derived from the bi-diagonalization method of Golub and Kahan is developed, and shown to require one-half the storage of the Lanczos method, one-quarter less than the conjugate gradient method, and no more computation than either of these methods.

The problem of breakdown for the general case of non-symmetric and possibly singular matrices is considered, and new lookahead methods for orthogonal and conjugate Lanczos algorithms are derived. A unified treatment of the Lanczos algorithms, the conjugate gradient algorithm and the Wiedemann algorithm is given using an orthogonal polynomial approach. It is shown, in particular, that incurable breakdowns can be handled by such an approach. The conjugate gradient algorithm is shown to consist of coupled conjugate and orthogonal Lanczos iterations, linking it to the development given for Lanczos methods. An efficient integrated lookahead method is developed for the conjugate gradient algorithm.

MICHELE MOSCA, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario  N2L 3G3
Quantum computers: powers and limitations

Information is stored, transmitted and processed always by physical means. Thus the capabilities and limitations of any information processing device is dictated by the laws of physics. Early last century, experiments showed that the ``classical'' laws of physics are wrong and a new theory was developed: quantum mechanics. Quantum information processing can be qualitatively different and much more powerful than its classical analogue. For example, a quantum algorithm can factor integers and find discrete logarithms using only a polynomial number of steps. I will describe the powers and discuss the limitations of quantum computers.

KUMAR MURTY, University of Toronto, Toronto, Ontario  M5S 3G3
Points on Abelian varieties over finite fields

We will describe joint work with Ram Murty on establishing the cyclicity of the group of points on a class of Abelian varieties over finite fields. The Abelian varieties are those associated to modular forms of weight 2.

RENATE SCHEIDLER, Department of Combinatorics and Optimization, University of Waterloo Waterloo, Ontario  N2L 3G1
Invariant computation and cryptography in function fields

The problem of computing the divisor class number, i.e. the order of k-rational points of the Jacobian, of an algebraic function field K over a finite field k appears to be very difficult. If K is represented as an extension of some rational function field k(x), then h is essentially equal to the product of the regulator R and the ideal class number h¢ of this extension. Since the computation of h¢ and R in algebraic number fields has been studied extensively, an obvious approach to the problem of finding h is to adapt the techniques used in number fields to function fields. This idea has already shown considerable success in hyperelliptic, i.e. quadratic function fields, and we are in the process of exploring certain cubic function field extensions for this purpose.

Function fields of small degree also offer a suitable environment for cryptography. Generally, one of h¢ or R is exponentially large in the genus of K, while the other is extremely small. If h¢ is large, then the ideal class group of K/k(x) can be used for key exchange a la Diffie-Hellman. If R is large, then the set of reduced principal fractional ideals in K/k(x) admits an almost group-like structure (coined ``infrastructure'' by D. Shanks) which can also serve as the basis for cryptographic key transfer. Algorithms for solving the respective discrete logarithm problems underlying the two protocols are directly related to computing h¢ and R.

OLIVER SCHIROKAUER, Department of Mathematics, Oberlin College Oberlin, Ohio  44074, USA
The discrete logarithm problem in finite fields

The security of many cryptographic schemes depends on the difficulty of computing logarithms in finite fields. In this talk I will provide an overview of the fastest algorithms currently available to compute such logarithms and discuss some of the directions being explored to improve these methods. Particular emphasis will be placed on the number field sieve and the function field sieve.

JON SORENSON, Butler University, Indianapolis, Indiana  46208, USA
A fast algorithm for approximately counting smooth numbers

Let Y(x,y) denote the number of integers £ x that are composed entirely of primes bounded by y. We present an algorithm for estimating the value of Y(x,y) with a running time roughly proportional to Öy. Our algorithm is a modification of an algorithm by Hunter and Sorenson that is based on a theorem of Hildebrand and Tenenbaum. This previous algorithm ran in time roughly proportional to y.

ANDREAS STEIN, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario  N2L 3G1
Explicit bounds in function fields and cryptographic applications

We discuss a number of applications of the theory of function fields to cryptography. By considering the function fields of irreducible hyperelliptic curves we can analyze the security of hyperelliptic curve cryptosystems with the help of number-theoretic ideas.

One application is the computation of regulators and class numbers of hyperelliptic function fields with the help of truncated Euler products. Hereby, we provide sharp estimates for the divisor class number of a hyperelliptic function field, i.e. the cardinality of the Jacobian of the corresponding hyperelliptic curve. These estimates can be used to develop an effective method of computing the divisor class number.

Furthermore, we provide heuristics on the distribution of the divisor class number within the bounds on the divisor class number. These heuristics suggest that, although the bounds are sharp, the approximation is in general far better. We explain these heuristics based on recent results of Katz and Sarnak.

DOUG STINSON, Department of Combinatorics and Optimization University of Waterloo, Waterloo Ontario  N2L 3G1
Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem

We present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are required to find a discrete logarithm in a finite group of order approximately 2^m, given that then unknown logarithm has a specified number of 1's, say t, in its binary representation. Heiman and Odlyzko presented the first algorithms for this problem. Unpublished improvements by Coppersmith include a deterministic algorithm with complexity O( m (\binom[(m)/2][(t)/2])) , and a Las Vegas algorithm with complexity O( Öt (\binom [(m)/2][(t)/2])).

We perform an average-case analysis of Coppersmith's deterministic algorithm. The average-case complexity achieves only a constant factor speed-up over the worst-case. Therefore, we present a generalized version of Coppersmith's algorithm, utilizing a combinatorial set system that we call a splitting system. Using probabilistic methods, we prove a new existence result for these systems that yields a deterministic algorithm with complexity O( t^3/2 (logm) (\binom [(m)/2][(t)/2])). We also present some explicit constructions for splitting systems that make use of perfect hash families.

GARY WALSH, CSE, Ottawa
Problems of fundamental importance in crypto number theory

Cryptographic devices whose security is based on the computational difficulty of certain number theoretic problems have flourished in recent years, both in Industry and in Government. Although significant progress has been made in assessing the level of security provided by these systems, it is certainly the case that future progress is pending, and that current systems are vulnerable to new mathematical ideas. We discuss the current status on certain problems of fundamental importance in this research area, and exhibit some open problems pertaining to security vulnerabilities.

ROBERT ZUCCHERATO, Entrust Technologies, 750 Heron Road, Ottawa, Ontario  K1V 1A7
Obtaining non-repudiation within a PKI environment

Non-repudiation is an often quoted security attribute that can be provided by the application of a digital signature. However, the existence of a signature alone does not provide this important property. Various architectural and procedural considerations must first be addressed before non-repudiation can be supported within a PKI environment. This talk will explore the issues surrounding non-repudiation and describe certain requirements that must be met before non-repudiation can be supported. Since for most organizations the ability to recover encryption keys is a requirement, an architecture that supports separate encryption and signature keys is crucial to supporting non-repudiation. In addition, the requirement that a certificate revocation mechanism be provided means that timestamping and/or notarization services are important components in the support of non-repudiation. If long-term support for non-repudiation is required, a secure evidence archive may be desirable. Finally, the issue of public key validation will be addressed. It has been proposed that public keys must be validated before non-repudiation can be supported. However, within the proper environment, public key validation does not provide additional support for non-repudiation and therefore is not required.