Sept. 1115, 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. 1115 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 1012 am (class starts Oct. 16)
Next class Oct. 18, 1012 am
Oct. 2327, 2006 and Nov. 617, 2006
Highspeed cryptography
Instructor: D. J. Bernstein (University of Illinois
at Chicago)
First class October 23 Fields room 230 at 3:30p.m., course
runs Oct. 2327 and Nov. 617
Quantum Information Theory
*Course has been cancelled*
Courses of interest being held at the University of Waterloo:
Sept. 11Dec. 5, 2006
Quantum Information Theory, Errorcorrection,
and Cryptography
Instructors: Ashwin Nayak and Debbie Leung (University
of Waterloo)
Time: MWF 11:3012: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. 1115 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 preknowledge can
be gained e.g. in the summer school on "Computational Number
Theory and Applications to Cryptography", June 19July
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
TateLichtenbaum 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 HasseWeil 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 padic 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
nonsupersingular 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:309:00 
Registration 

9:0010:00 
Efficient arithmetic of finite fields 
Daniel J. Bernstein

10:1511:15 
Elliptic curves I 
Roger Oyono

11:3012:30 
Addition chains 
Peter Birkner

12:3014:00 
lunch 

14:0015:00 
Generic attacks 
Roger Oyono 
15:0017:00 
exercises & answers 

Tuesday, September 12 
9:0010:00 
Hyperelliptic curves I 
Tanja Lange 
10:1511:15 
Hyperelliptic curves II 
Tanja Lange 
11:3012:00 
Index calculus attack in finite fields 
Roger Oyono 
12:0012:30 
Elliptic curves II 
Reinier Bröker 
12:3014:00 
lunch 

14:0015:00 
Background mathematics for CM 
Reinier Bröker 
15:0017:00 
exercises & answers 

Wednesday, September 13 
9:0010:00 
Arithmetic on EC, large characteristic 
Daniel J. Bernstein 
10:1511:15 
Arithmetic on EC, small characteristic 
Nicolas Thériault 
11:3012:30 
Point counting on EC 
Reinier Bröker 
12:3014:00 
lunch 

14:0015:00 
Complex multiplication I 
Reinier Bröker 
15:0017:00 
exercises & answers 

Thursday, September 14 
9:0010:00 
Index calculus attacks on HECC I 
Nicolas Thériault 
10:1511:15 
Complex multiplication II 
Reinier Bröker 
11:3012:30 
Arithmetic on HEC 
Tanja Lange 
12:3014:00 
lunch 

14:0015:00 
Pairings I 
Tanja Lange 
15:0017:00 
exercises & answers 

Friday, September 15 
9:0010:00 
Pairings II 
Tanja Lange 
10:1511:15 
Construction of pairing friendly curves 
Michael Naehrig 
11:3012:30 
Index calculus attacks on HECC II 
Nicolas Thériault 
12:3014:00 
lunch 

14:0015:00 
Summary  how to choose curves 
Tanja Lange 
Highspeed 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. 2327 and Nov. 617
**students should watch for announcements
Week 
Day 
Date 
Time 
1 
Mon 
2006.10.23 
15:3017:00 
1 
Tue 
2006.10.24 
11:0012:30, 15:3017:00 
1 
Wed 
2006.10.25 
11:0012:30, 15:3017:00 
1 
Thu 
2006.10.26 
11:0012:30, 15:3017:00 
1 
Fri 
2006.10.27 
11:0012: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:3017:00 
3 
Tue 
2006.11.07 
11:0012:30, 15:3017:00 
3 
Wed 
2006.11.08 
11:0012:30, 15:3017:00 
3 
Thu 
2006.11.09 
11:0012:30, 15:3017:00 
3 
Fri 
2006.11.10 
11:0012: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:0012:30 (project reports and discussion) 
4 
Fri 
2006.11.17 
15:3017: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 creditcard number won't be able to
figure out the original number.
Highspeed 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 stateoftheart 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 nonprerequisites: 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 stateoftheart
function takes half a millisecond on my laptop to compute a highsecurity
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 computerdependent 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 higherlevel speedups are also constantfactor speedups.
In fact, most of the speedups in the algorithms literature are
constantfactor 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, Errorcorrection,
and Cryptography
Instuctor: Ashwin Nayak and Debbie Leung, (University of
Waterloo)
Time: MWF 11:3012:20
Location: MC 5158A, U. Waterloo
INTRODUCTORY MATERIAL
a) Basic framework of Q systems
 postulates of QM
 qubits, unitary ops, measurements
 continuoustime evolution of Hamiltonians
 superdense coding
 teleportation
 nocloning
 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 9qubit code
 CSS codes, including 7qubit code
 discussion of asymptotic results regarding QECCs
 stabilizer codes, including 5qubit code
b) Faulttolerance
 general discussion of faulttolerance, 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
 bitcommitment
 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 entanglementassisted
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. HoiKwong 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:
BACK TO TOP