THEMATIC PROGRAMS

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

Banquet:
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
Secondo 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
Dessert	Assorted biscotti and fruit platter/table Expresso, cappucino, latte

BACK TO TOP