Cryptography & Number Theory /Cryptographie et Théorie des
(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
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
- 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, 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
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
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 2m,
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( t3/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.