Advanced Cryptography: quantum cryptography

Corresponding entry in Aachen Campus, Bonn Basis (Lecture, Tutorial).

Responsible

Prof. Dr. Joachim von zur Gathen

Lecture

Michael Nüsken.

Tutorial

Daniel Loebenberger.

Time & Place

Monday 12¹⁵-13⁴⁵, b-it 1.25.
Tuesday 13⁰⁰-14³⁰, b-it 1.25.
Tutorial: Tuesday 14⁴⁵-16¹⁵, b-it 1.25.

First meeting: Tuesday, 26 October 2010, 13³⁰, b-it Rheinsaal.

All times subject to agreement in class. (Before 12 November instead of Monday the course took place on Wednesday.)

Notes

The screen notes (PDF) contain all handwritten stuff (last updated 01 February 2011, 16:01).

Exercises

Exercise 1 (PDF, last updated 28 October 2010, 00:03).
Exercise 2 (PDF, last updated 11 November 2010, 13:30).
Exercise 3 (PDF, last updated 16 November 2010, 19:07).
Exercise 4 (PDF, last updated 17 November 2010, 12:21).
Exercise 5 (PDF, last updated 26 November 2010, 22:25).
Exercise 6 (PDF, last updated 08 December 2010, 17:05).
Exercise 7 (PDF, last updated 20 December 2010, 16:04).
Exercise 8 (PDF, last updated 15 December 2010, 15:12).
Exercise 9 (PDF, last updated 22 December 2010, 13:25).
Exercise 10 (PDF, last updated 12 January 2011, 18:28).
Exercise 11 (PDF, last updated 19 January 2011, 17:22).
Exercise 12 (PDF, last updated 26 January 2011, 15:41).

Prerequisites

Basic knowledge in cryptography is required.

Cryptography is affected two-fold by quantum theoretical ideas: quantum channels and quantum computers.

Quantum effects may be used to transmit secrets securely through a so-called quantum channel. Any tampering can be detected by the conversation parties with high probability. Based on these absolutely secure cryptography is possible. Well, unless the physics has not been understood correctly...

There is a theoretical model of quantum computers. On these theoretical quantum Turing machines factoring can be solved in polynomial time. However, physical realization of quantum computers is tricky: All efforts during the last two decades have only led to quantum computers with up to 12 qubits which is just enough to factor the integer 15. Nevertheless this shows that factoring and also discrete logarithm based cryptosystems may be attackable in the near future. Because of this and to enlarge the basis of cryptographic security new cryptographic systems based on other primitives are needed. The pitfall and challenge is that most systems constructed so far have been shown too weak.

The course intends to show the quantum theory needed and the computational model(s) of quantum computers, use them to break factoring and discrete logarithm problems, and have a look at candidates for systems that (hopefully) cannot be attacked by quantum computers as well.

Literature

Michael A. Nielsen and Isaac L. Chuang (2000). Quantum Computation and Quantum Information. Cambridge University Press.
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John Smolin & Harald Weinfurter (1995). Elementary gates for quantum computation. ArXiv.
Daniel J. Bernstein, Johannes Buchmann & Erik Dahmen (eds., 2010). Post-Quantum Cryptography. Springer-Verlag Berlin, Heidelberg.
Paul Falstad (2005). Hydrogen Atom Orbital Viewer.
Mika Hirvensalo (2004). Quantum Computing. Second edition, Springer-Verlag Berlin Heidelberg.
wikimedia (2010). Hydrogen atom, complex 3D, real 3D.

Allocation

4+2 SWS, 8 credits. Optionally, 3+2 SWS, 6 credits.

Successful completion of the course yields 8 credit points. For students who only want 6 credit points, a breakpoint at about 3/4 of the teaching time will be defined, and only the course material up to that point will be relevant for their exams and grades.

Media Informatics: Computer and Communication Technology.
Recommendation for University of Bonn - Computer Science: A or A1, respectively.

Mailinglist

We will put each member on the mailing list . You can also subscribe yourself. The list is intented for all participants of the course as a platform for discussions around the topic. Furthermore, announcements regarding the course are made here.