Cryptologic
Protocol Theory
Ivan
Damgård and Jesper Buus Nielsen
This is the 2010 version of the course - Please go to the The
new home page
This is the home page of the course in Cryptologic
Protocol Theory
We cover the basic concepts in protocol theory and look
at a set of practical applications.
More details in the course plan below.
Time
and
Place
Monday 11-13 and Wednesday 12-14, Shannon 159
Documentation
An oral exam at the end of the course. In addition, there
is an exercise to hand in most weeks.
A correct answer to a hand-in gives you 1 point. A
partially correct one gives 1/2 point, you
may then hand-in again and get 1 point instead. Exercises
that are handed in too late can give
at most 1/2 point. There will be about 11 hand-in's and
you need at least 8 points to go to the exam.
Participants can choose to follow an honors version of
the course, you should only make this
choice after discussing with the teachers. Honors
students will be given special exercises in
some weeks, and will, towards the end of the course,
write a report on a subject chosen in
collaboration with the teachers.
Course
Material
There may be revisions during the course, and more may be
added.
NOTE we currently do not plan to cover E-voting in this
version of the course, instead other subjects
such as secure auctions will be covered. We keep the
material on E-voting on the page for
those interested.
- Ivan
Damgård
and Jesper Buus Nielsen: Commitment Schemes and Zero-Knowledge
Protocols
- -
an
overview explaining some basic concepts and listing some of the
- theory
results
known. Available here
as pdf file.
- Ivan
Damgård:
CPT notes nr.1, Graph non-isomorphism, ZK for all of NP, and
exercises.
- Available
here
as pdf file.
- Ivan
Damgård:
On Sigma-protocols, available here as
pdf
file. REVISED March 3.
- Ivan
Damgård,
Jesper Buus Nielsen: Note on E-voting, pdf-file.
REVISED
April 20.
- Ivan
Damgård:
note on Secret Sharing, pdf-file.
Background Material
- mostly for people who do not have much prior
background in crypto before
taking this course. Will not be covered explicitly
in the course.
- Ivan
Damgård:
A quick and dirty introduction to Cryptography - a small
warm-up explaining some basic concepts. Available here
as ps file.
- Bellare
and
Goldwasser: Lecture Notes on Cryptography - lecture notes from a
course taught by the authors at MIT. Very good coverage of almost any
theoretical, complexity based cryptographic construction. It's BIG,
about 200 pages. Available here
as ps file (about 2Mb).
- Papers
by
Cramer and Shoup on chosen ciphertext security, from 1998
and 2002
More material will be added here as we move along, in
case I have it available electronically.
Course
Plan
We will be covering the following main points in roughly
the order listed.
- Introduction
to
some basic concepts and models
- Bit
Commitment
Schemes
- Zero-Knowledge
Protocols
and Interactive Proof Systems
- Theory
Results
- ZKIP=
IP
if one-way functions exist
- Existence
of
commitment schemes
- Application
of
zero-knowledge to Chosen Ciphertext security
- Electronic
Cash
and Payment Systems
- General
Multiparty
Computations
- Applications
to
auctions etc.
Links
Here are some assorted links to various places of
interest:
- The
home
page of IACR,
the
International Association for Cryptologic Research. Info on
conferences, journals etc. IACR is behind most worthwhile activities of
this sort in the area.
- DigiCrime,
where you can have almost any digitial crime committed that your heart
desires: you can ask them to break into other peoples systems,
counterfeit electronic money, etc. Of course it's all a joke,
and hilariously funny too, but with a serious purpose: you can find a
seemingly endless list of real-life security problems and break-in's
that really happened. Of course, DigiCrime were not responsible
for those - or so they say...
- The
Theory
of
Cryptography Library, nice source of the very latest
papers in the area.
- The
theory group
at MIT, houses one of the best cryptography research groups
in complexity based cryptography. They also have several nice
literature search tools on-line.
- The
crypto
group at ETH Zurich, the leading research group in
information theory based cryptography.
- Cryptomathic
AS, local software and consulting company, of which I'm a co-founder
and -owner. Have a look here to get a feeling for some of the things
happening in real life implementations of cryptography.
- Home
page
of Mihir
Bellare, who is one the well known figures in crypto
reserach and has one of the most informative personla home pages in the
arera. Good source of all kinds of links and publications.