Cryptologic Protocol Theory

                               Ivan Damgård and Jesper Buus Nielsen

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.

• Cramer, Gennaro and Schoenmakers: A Secure and Optimally Efficient Multi-Authority
• Election Scheme. Available here as ps file. See also a later paper by Damgård, 
• Jurik and Nielsen here, on an alternative implementation that is more efficient for large scale 
• elections.
• Cramer, Damgård and Nielsen: Lecture Notes on Electronic Payments
• Revised May 10: Cramer, Damgård and Nielsen: Draft of book on Multiparty Computation
• Cramer, Damgård and Nielsen:    Lecure Notes on Multiparty Computation.
• Slides on multiparty computation, now version from 2006, here as pdf file
• Slides on Multiparty Computation fra Barcelona Workshop
• Additional Exercises on Multiparty Computation.
• 
  

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.