THEMATIC PROGRAMS

March 19, 2024

Fall 2006
Thematic Program in Cryptography

Graduate Courses held at the Fields Institute


Sept. 11-15, 2006
Elliptic and hyperelliptic curve cryptography

Instructor: Tanja Lange (Eindhoven Technical University, The Netherlands, and Technical University of Denmark)
The course will take place Sep. 11-15 2006, each day from 09:00 till 12:30 and 14:00 till 17:30.

Oct. 16 -Dec 15, 2006
Abelian varieties and Cryptography
Instructor: Kumar Murty (Toronto)
Monday 10-12 am (class starts Oct. 16)
Next class Oct. 18, 10-12 am

Oct. 23-27, 2006 and Nov. 6-17, 2006
High-speed cryptography

Instructor
: D. J. Bernstein (University of Illinois at Chicago)
First class October 23 Fields room 230 at 3:30p.m., course runs Oct. 23-27 and Nov. 6-17

Quantum Information Theory
*Course has been cancelled*

Courses of interest being held at the University of Waterloo:

Sept. 11-Dec. 5, 2006
Quantum Information Theory, Error-correction, and Cryptography
Instructors: Ashwin Nayak and Debbie Leung (University of Waterloo)
Time: MWF 11:30--12:20
Location: MC 5158A, U. Waterloo

CO681/CS767/Phys767 -- Quantum Information Processing
Instructor: Richard Cleve


Elliptic and hyperelliptic curve cryptography
Instuctor
: Tanja Lange (Eindhoven Technical University, The Netherlands, and Technical University of Denmark)
Summer School on Elliptic and Hyperelliptic Curve Cryptography
with lectures given by
Daniel J. Bernstein (University of Illinois at Chicago, USA)
Peter Birkner (Technical University of Denmark)
Reinier Bröker (University of Calgary, Canada)
Michael Naehrig (RWTH Aachen University, Germany)
Roger Oyono (University of Waterloo, Canada)
Nicolas Thériault (Fields Institute Toronto, Canada)

This course will be given in the form of a summer school just before ECC.
The course will take place Sep. 11-15 2006, each day from 09:00 till 12:30 and 14:00 till 17:30.

Prerequisites:This course is intended for graduate students in the field of cryptography and mathematics. The participants are expected to be familiar with finite fields and have some background in implementations, some experience with elliptic curves is helpful but not necessary. Such pre-knowledge can be gained e.g. in the summer school on "Computational Number Theory and Applications to Cryptography", June 19-July 7, 2006, Laramie, Wyoming, which is also linked to the special program at the Fields Institute.

Content: The objective of the course is to prepare for the following ECC conference - but should be interesting as an individual course to get an overview of the area of curve cryptography, too.

The course starts with an introduction to elliptic and hyperelliptic curves and details efficient arithmetic in their ideal class group. We also consider possible special choices like Koblitz curves which are defined over subfields and GLV curves which allow to speed up the computation of scalar multiples (the main operation in curve based cryptography) by using efficiently computable endomorphisms.

A comparably new topic in curve based cryptography are pairings. They have been studied in mathematics since many years but only the constructive application of pairings in cryptographic protocols raised interest in the efficient computation of the Weil and Tate-Lichtenbaum pairing. We introduce the pairings and explain optimizations for their implementation.

We present generic methods of computing discrete logarithms and detail special methods applicable to curves like index calculus attacks on hyperelliptic curves of large genus and attacks via Weil descent. Clearly, pairings can also be used to transfer the discrete logarithm problem (DLP) from the Jacobian of a curve to the DLP in a finite extension field of the ground field.

To avoid attacks by brute force, the group order must be large enough. The Hasse-Weil bound gives bounds on the number of points over finite fields and thus allows to know the size of the groups approximately. However, since the DLP could be solved in subgroups and then computed for the big group with the help of the Chinese Remainder Theorem one needs to ensure that the group order is known and contains a large prime factor. For elliptic curves we explain Schoof's algorithm as a method to count points on curves over prime fields and consider p-adic methods like AGM which are more efficient in the case of small characteristic fields.

A different approach is to construct curves using the CM method. Even though nowadays counting points via Schoof's algorithm is feasible for elliptic curves of cryptographic seize this method is still of interest, e.t. it is the main way of constructing non-supersingular curves with low embedding degree which can be useful in pairing based protocols if one wants to avoid supersingular curves for some reason or if a larger embedding degree is desired.

Schedule:

  Title Instructor
Monday, September 11
8:30-9:00 Registration  
9:00-10:00 Efficient arithmetic of finite fields Daniel J. Bernstein
10:15-11:15 Elliptic curves I Roger Oyono
11:30-12:30 Addition chains Peter Birkner
12:30-14:00 lunch  
14:00-15:00 Generic attacks Roger Oyono
15:00-17:00 exercises & answers  
Tuesday, September 12
9:00-10:00 Hyperelliptic curves I Tanja Lange
10:15-11:15 Hyperelliptic curves II Tanja Lange
11:30-12:00 Index calculus attack in finite fields Roger Oyono
12:00-12:30 Elliptic curves II Reinier Bröker
12:30-14:00 lunch  
14:00-15:00 Background mathematics for CM Reinier Bröker
15:00-17:00 exercises & answers  
Wednesday, September 13
9:00-10:00 Arithmetic on EC, large characteristic Daniel J. Bernstein
10:15-11:15 Arithmetic on EC, small characteristic Nicolas Thériault
11:30-12:30 Point counting on EC Reinier Bröker
12:30-14:00 lunch  
14:00-15:00 Complex multiplication I Reinier Bröker
15:00-17:00 exercises & answers  
Thursday, September 14
9:00-10:00 Index calculus attacks on HECC I Nicolas Thériault
10:15-11:15 Complex multiplication II Reinier Bröker
11:30-12:30 Arithmetic on HEC Tanja Lange
12:30-14:00 lunch  
14:00-15:00 Pairings I Tanja Lange
15:00-17:00 exercises & answers  
Friday, September 15
9:00-10:00 Pairings II Tanja Lange
10:15-11:15 Construction of pairing friendly curves Michael Naehrig
11:30-12:30 Index calculus attacks on HECC II Nicolas Thériault
12:30-14:00 lunch  
14:00-15:00 Summary - how to choose curves Tanja Lange


Abelian varieties and Cryptography
Instructor: Kumar Murty (Toronto)
Monday 10-12 am, Fields room 230 (class starts Oct. 16)
Schedule:

Monday October 16, 10-12 am Fields Room 230
Wednesday October 18, 10a.m.-12p.m. Fields Room 230
Monday October 23, 10-12 am Fields Room 230
Wednesday October 25, 9-11a.m. Fields Room 230
Monday November 6, 10-12 am (Course cancelled)  
Wednesday November 8, 1:30 -3 pm Fields Room 230
Monday November 13, 10-12 Fields Room 230
Wednesday November 15, 1:30 -3 pm Fields Room 230
Monday November 20, 10-12 am Fields Room 230
Wednesday November 22, 10a.m.-12p.m. Fields Room 230
Monday December 4, 10-12 am Fields Room 230
Wednesday December 6, 10a.m.-12p.m. Fields Room 230

Audio & Slides

The use of elliptic curves (one-dimensional Abelian varieties) in cryptography has been extensively studied over the last two decades. In this course, we will start to look at the higher-dimensional case. We will begin by discussing the necessary number theoretic and algebro-geometric background that will be necessary for this study. We will then discuss the case of elliptic curves and of Jacobians of various families of curves. Finally, we will discuss the case of general Abelian varieties. We will be looking at both constructive (i.e. explicit arithmetic and point counting) and destructive (i.e. weaknesses, attacks, etc.) aspects. The course will assume elementary number theory and abstract algebra.


High-speed cryptography
Instructor: D. J. Bernstein
Professor, Mathematics, Statistics,and Computer Science, University of Illinois at Chicago
First class October 23 Fields room 230 at 3:30p.m., course runs Oct. 23-27 and Nov. 6-17
**students should watch for announcements

Week Day Date Time
1 Mon 2006.10.23 15:30-17:00
1 Tue 2006.10.24 11:00-12:30, 15:30-17:00
1 Wed 2006.10.25 11:00-12:30, 15:30-17:00
1 Thu 2006.10.26 11:00-12:30, 15:30-17:00
1 Fri 2006.10.27 11:00-12:30
2 Mon 2006.10.30 no lectures (students attend CCANTC workshop)
2 Tue 2006.10.31 no lectures (students attend CCANTC workshop)
2 Wed 2006.11.01 no lectures (students attend CCANTC workshop)
2 Thu 2006.11.02 no lectures (students attend CCANTC workshop)
2 Fri 2006.11.03 no lectures (students attend CCANTC workshop)
3 Mon 2006.11.06 15:30-17:00
3 Tue 2006.11.07 11:00-12:30, 15:30-17:00
3 Wed 2006.11.08 11:00-12:30, 15:30-17:00
3 Thu 2006.11.09 11:00-12:30, 15:30-17:00
3 Fri 2006.11.10 11:00-12:30
4 Mon 2006.11.13 no lectures (students work on course projects)
4 Tue 2006.11.14 no lectures (students work on course projects)
4 Wed 2006.11.15 no lectures (students work on course projects)
4 Fri 2006.11.17 11:00-12:30 (project reports and discussion)
4 Fri 2006.11.17 15:30-17:00 (project reports and discussion)

 

Course contents: Anyone with access to the Internet can intercept mail messages and web pages and other packets of data to see what they say. He can also send fake messages that look like real messages.

Cryptography protects messages sent through the Internet. Cryptography scrambles and unscrambles packets to protect against forgery and against espionage. An attacker who forges a message won't be able to scramble it in the right way, so when we unscramble it we'll see that it's a forgery and that we should throw it away. An attacker who intercepts a scrambled credit-card number won't be able to figure out the original number.

High-speed cryptography is important for busy network servers. Here's a quote from Cricket Liu, author of several books on the Internet's Domain Name System: ``Verifying signed resource records [i.e., performing cryptographic operations] is computationally intensive [i.e., is painfully slow]. This has slowed deployment of DNS security.'' As a practical matter, DNS security still doesn't exist; attackers can seize control over incoming mail and outgoing web pages by forging DNS records. The users need faster software to scramble DNS records.

This course will explain state-of-the-art algorithms for the four fundamental operations in cryptography: (1) using a long shared secret to protect a long series of private messages; (2) expanding a short shared secret into a long shared secret; (3) sharing a secret through a public conversation; and (4) using a sender secret, with no shared secrets, to protect a long series of public messages.

Prerequisites and non-prerequisites: Students are expected to have some experience with algorithm analysis (figuring out why a computer hasn't finished a computation yet) and algorithm improvement (making the computer finish the computation more quickly). A typical introductory algorithms course uses a textbook by Cormen, Leiserson, Rivest, and Stein; features quotes such as ``Heapsort takes time n log n times, um, some constant''; and incorrectly describes its algorithm improvements as ``optimizations.''

The most obvious difference in flavor between this course and a typical algorithm course is that this course will pay attention to constants. This course will, for example, explain how a state-of-the-art function takes half a millisecond on my laptop to compute a high-security shared secret from a public conversation. Ignoring constant factors would remove all content from this statement.

Of course, these constants depend on the choice of computer. Sometimes one computer takes 10 clock cycles for an operation while another computer takes just 1 clock cycle; this affects the time for any algorithm built on top of that operation. Students might have seen some computer-dependent algorithm analysis and algorithm improvement in courses on architecture, assembly language, ``optimizing'' compilers, supercomputing, etc. None of those courses are prerequisites; this course will include an introduction to the speed of real computers.

Many higher-level speedups are also constant-factor speedups. In fact, most of the speedups in the algorithms literature are constant-factor speedups. However, students will not be presumed to have any previous experience handling constant factors in algorithm analysis.

The other obvious difference in flavor between this course and other algorithm courses is the choice of functions being computed. A typical introductory algorithm course spends time on sorting, for example, and on various graph operations such as shortest paths. This course instead focuses on a few critical cryptographic operations. Those operations rely on some mathematics that students might have seen in previous courses on algebra, number theory, or cryptography. None of those are prerequisites; this course will include an introduction to the relevant mathematics.


Quantum Information Theory, Error-correction, and Cryptography
Instuctor: Ashwin Nayak and Debbie Leung, (University of Waterloo)
Time: MWF 11:30--12:20
Location: MC 5158A, U. Waterloo

INTRODUCTORY MATERIAL

a) Basic framework of Q systems
- postulates of QM
- qubits, unitary ops, measurements
- continuous-time evolution of Hamiltonians
- superdense coding
- teleportation
- no-cloning
- density matrices, ensembles, partial trace
- Schmidt decomposition
- purification of a density matri
b) General framework of Q systems
- CPTP maps (general "quantum operations")
- Kraus Representation theorem
- POVMs

ERROR CORRECTION AND FAULT TOLERANCE

a) Basic overview of QECCs
- basics of classical ECCs
- Shor's 9-qubit code
- CSS codes, including 7-qubit code
- discussion of asymptotic results regarding QECCs
- stabilizer codes, including 5-qubit code
b) Fault-tolerance
- general discussion of fault-tolerance, and the threshold theorem (need not be complete)

CRYPTOGRAPHY

a) Quantum key distribution
- BB84, general sketch of protocol and intuition behind it's security, including discussion of what has to be addressed in the actual security proof
- complete proof of security of BB84 (in "ideal" model, where single qubits can be sent, etc)
- relationship to "Cryptographic devices" ?
b) Possible other topics
- coin flipping
- authentication
- bit-commitment
- digital signatures
- private quantum channels
- quantum secret sharing
- composability

INFORMATION THEORY

a) Operational tasks: compression, purification, etc
- von Neumann entropy
- information compression ??
- entanglement purification
- Holevo's theorem (statement of it and some motivating issues, such as applications)
- distinguishability of quantum states (trace norm, fidelity)
- Nayak's bound and random access codes ??
b) Noisy channels
- basic statement of the classical and quantum channel capacity theorem
- above, but with proofs ??
- sketch of the variety of communication tasks in the presence of noise, and their relations (such as entanglement-assisted classical communication, the relation between entanglement purification protocol and channel capacity etc (these are no more than prepending and appending superdense coding and teleportation), and remote state preparation.


ECE1531F Quantum Information Theory (course has been cancelled)
Instructor: Prof. Hoi-Kwong Lo

Objectives: This course is an introduction to quantum information theory. We will focus on the theory of quantum communication and quantum cryptography. Quantum information processing offers some dramatic advantages over conventional information processing. For instance, quantum computers can efficiently break standard encryption schemes such as RSA. Therefore, much of conventional cryptography will fall apart if a quantum computer is ever built. Moreover, quantum cryptography allows perfectly secure communications with its security guaranteed by the fundamental laws of physics. Many institutions in the world are currently experimenting with technologies for implementing quantum information processing. We survey recent progress and open questions in quantum information theory.

Prerequisites: Strong undergraduate background in a mathematical subject (e.g. Electrical engineering, Physics, mathematics or computer science) is needed. Even though prior exposure will be desirable, no background in quantum mechanics or
conventional information theory is assumed.



Taking the Institute's Courses for Credit

As graduate students at any of the Institute's University Partners, you may discuss the possibility of obtaining a credit for one or more courses in this lecture series with your home university graduate officer and the course instructor. Assigned reading and related projects may be arranged for the benefit of students requiring these courses for credit.

Financial Assistance

As part of the Affiliation agreement with some Canadian Universities, graduate students are eligible to apply for financial assistance to attend graduate courses. To apply for funding, apply here(coming shortly)
Two types of support are available:

  • Students outside the greater Toronto area may apply for travel support. Please submit a proposed budget outlining expected costs if public transit is involved, otherwise a mileage rate is used to reimburse travel costs. We recommend that groups coming from one university travel together, or arrange for car pooling (or car rental if applicable).

  • Students outside the commuting distance of Toronto may submit an application for a term fellowship. Support is offered up to $1000 per month.

    For more details on the thematic year, see Program Page or contact crypto@fields.utoronto.ca

    BACK TO TOP