April 14, 2024
Fall 2006
Thematic Program in Cryptography

Workshop on Computational challenges arising in algorithmic number theory and Cryptography
October 30- November 3, 2006

Organizers: Renate Scheidler, Andreas Stein, Edlyn Teske

Despite intense research over many decades and sometimes even centuries, there are numerous number theoretic problems for which efficient solutions continue to elude us. Moreover, such solutions are generally not even known to exist. For example, it is unkown whether it is possible to find solutions to Pell equations and other norm equations quickly. Furthermore, to date, no efficient algorithm for factoring a large randomly chosen number into its prime factors is known, and the true complexity of the integer factorization problem is not even clear. Nevertheless, the popular RSA cryptosystem is based on the assumed difficulty of this problem.

In general, the security of most public-key cryptographic systems relies on the believed difficulty of a certain number theoretic problem. In exploring such problems, researchers face mathematical as well as computational and algorithmic difficulties. This workshop is intended to address the manifold computational challenges arising in number theoretic algorithms and cryptographic applications. Questions to be explored may include, but are by no means limited to:

  • discrete logarithm problems in various settings, such as finite fields
    of various forms, algebraic curves and tori, and others
  • integer factorization
  • primality proving
  • lattice problems
  • algebraic number theory computations, including methods for computing
    class groups and class numbers, regulators, and fundamental units
  • efficient arithmetic in various algebraic structures, such as the
    integers, finite fields, polynomial rings, algebraic curves, algebraic
    number fields, and others
  • sieving techniques
  • linear algebra techniques

Schedule (Tentative):

Monday, October 30
(Banquet tickets on sale Monday and Tuesday)
8:30 - 8:45 Registration
8:45 - 9:00 Opening Remarks
9:00 - 10:00 VICTOR S. MILLER, Center for Communications Research
The weil pairing, and its efficient calculation
10:00 - 10:30 Coffee Break
10:30 - 11:20 STEVEN GALBRAITH, Royal Holloway University of London
Some open problems in elliptic curve cryptography
11:25 - 12:15 FLORIAN HESS, Technische Universitt Berlin
The ate pairing - computational aspects of pairings in cryptography
12:15 - 2:10 Lunch
2:10 - 3:00 KIRAN KEDLAYA, Massachusetts Institute of Technology
Recent results on p-adic computation of zeta functions
3:00 - 3:30 Coffee Break
3:30 - 4:20

ALINA COJOCARU, University of Illinois at Chicago
Effective versions of Serre's Theorem for elliptic curves

4:25 - 4:45 HUGH WILLIAMS, University of Calgary
My reminiscences of Emma Lehmer
4:45 Reception at Fields
Tuesday, October 31
(Banquet tickets on sale Monday and Tuesday)
9:00 - 10:00 FRANCOIS MORAIN, Ecole Polytechnique, LIX
Recent improvements to the SEA algorithm in genus 1
10:00 - 10:30 Coffee Break
10:30 - 11:20 ALLISON M. PACELLI, Williams College
Constructing number fields and function fields with prescribed class group properties
11:25 - 12:15 RACHEL PRIES, Colorado State University
Computing the invariants of p-torsion of Jacobians in characteristic p
12:15 - 2:00 Lunch
2:00 - 2:50 YOONJIN LEE, Simon Fraser University
Construction of cubic function fields from quadratic infrastructure
2:50 - 3:15 Coffee Break
3:15 - 4:05

ERICH KALTOFEN, North Carolina State University
Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields

4:05-4:55 DANIELE MICCIANCIO, University of California San Diego
Ideal lattices: cryptographic applications and open problems
Wednesday, November 1
9:00 - 10:00 PIERRICK GAUDRY, Ecole Polytechnique
Variants of the montgomery form based on theta functions
10:00 - 10:30 Coffee Break
10:30 - 11:20

ALFRED MENEZES, University of Waterloo
Another look at provable security

11:25 - 12:15

JOHANNES BUCHMANN, Technische Universitat Darmstad
CMSS - digital signatures without number theory?

  Rest of the day free
Thursday, November 2
9:00 - 10:00 PETER STEVENHAGEN, Universiteit Leiden
Computational challenges arising in complex multiplication
10:00 - 10:30 Coffee Break
10:30 - 11:20 ELISA GORLA, University of Zurich
Computational challenges arising in torus-based cryptography
11:25 - 12:15 JINTAI DING, Technical University of Darmstadt
Multivariate public key cryptography
12:15 - 2:10 Lunch
2:10 - 3:00 DAVID JAO, University of Waterloo
The discrete logarithm problem on algebraic curves
3:00 - 3:30 Coffee Break
3:30 - 4:20 MARK BAUER, University of Calgary
Relating the ECDLP to other curves
6:00 Banquet at L'Expresso Restaurant, corner of St. George & Bloor, 321 Bloor Street
Friday, November 3
9:00 - 10:00 TAKAKAZU SATOH, Tokyo Institute of Technology
On Euclid prime sequences (joint work with Nobushige Kurokawa)
10:00 - 10:30 Coffee Break
10:30 - 11:20 NILS BRUIN, Simon Fraser University
Deciding the existence of rational points on curves
11:25 - 12:15

MICHAEL JACOBSON, University of Calgary
Computing class groups of quadratic fields

12:15 - 2:10 Lunch
2:10 - 3:00 MARK GIESBRECHT AND ARNE STORJOHANN, University of Waterloo
Speedy new algorithms for solving integer linear systems
3:00 - 3:30 Coffee Break
3:30 - 4:20 ROGER OYONO, University of Waterloo
Computation of non-hyperelliptic modular Jacobians of dimension 3

There will be a conference banquet on Thursday November 2. Tickets will be on sale Monday and Tuesday ($60 includes one drink) . All additional drinks are available at the cash bar.
The banquet will take place Thursday night 6 pm at the L'Expresso Restaurant at the corner of St. George and Bloor, 321 Bloor Street. The menu is as follows:

Canopies Assorted mini pizza served as guests arrive
Primo Arugola Salad with asiago cheese, tomato in vinaigrette
Choice of
- Linguine ai Frutti di mare with mussels, calamari, shrimp, sea scallops and salmon or
- Alberta AAA Black Angus Strip loin served with house frites, asparagus and mushroom jus or
- a vegetarian choice,Truffled Risotto with Mushrooms

Assorted biscotti and fruit platter/table

Expresso, cappucino, latte