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 |
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:
BACK TO TOP
