About the Courses
(Ronald de Wolf)
Quantum computing tries to improve computers (making them faster, more secure etc.) by using quantum-mechanical effects like superposition, interference, and entanglement. There has been much progress in this area in the last 5 years, both in theory and in experimental realization. This course is meant as an introduction to the area for computer scientists and mathematicians. No prior knowledge of physics is assumed. In the 5 days of the course we'll cover the following topics:
- Introduction: some background, the quantum circuit model, early algorithms
- The quantum Fourier transform and Shor's algorithm for factoring integers (and breaking RSA)
- Grover's algorithm for search, quantum walk algorithms
- Complexity theory: query lower bounds, quantum complexity classes
- Quantum communication
Reading material: lecture notes.
Lattices and Cryptography
Lattices have been investigated by mathematicians for over two centuries. In the last decade they have become an extremely active topic of research in computer science and cryptography. This is mainly due to Ajtai's seminal paper from 1996 ushering the beginning of lattice-based cryptography, as well as more recent work, such as the introduction of the LWE problem in 2005 and Gentry's construction of a fully homomorphic encryption scheme.
This course is mainly meant to serve as an introduction to the area, but will also include some recent developments. Specifically, we will attempt to cover:
- Introduction: history, Minkowski's theorem, basic definitions and results
- Algorithms for lattice problems (both efficient and exponential time), and applications (Coppersmith's method).
- The LWE problem and its quantum aspects. Public key cryptosystems, fully homomorphic encryption.
- Ring-LWE, ideal lattices and quantum algorithms
We will not assume any prior knowledge in the area.
- Lecture notes
- Survey on crypto aspects
- Winter school on cryptography