University of Tartu - **©2011 Rafik Chaabouni** - Last update: 08.04.2013 15:14

**Date:** 07/06/2012 16:15 - 18:00 **Location:** J. Liivi 2, room 317 (next to the coffee room)

**Title:**
Classical cryptography that is secure against quantum computers?

**Abstract:**

Security of many currently used cryptographic schemes (such as RSA or Diffie-Helman) is based on the assumption that certain number-theoretic problems (most commonly, factoring or discrete logarithm) are difficult. However, it is known that quantum computers will be able to factor large numbers and solve the discrete logarithm problem efficiently.

In this talk, we consider the following question: which cryptographic schemes will remain secure even when quantum computers are built? We will survey two alternatives: schemes based on lattice problems and schemes based on coding theory (such as McEliece scheme).

The talk will be self-contained and assume no previous knowledge of quantum computing.

Biography: Andris Ambainis holds B.Sc. (1996) and M.Sc. (1997) from University of Latvia and Ph.D. (2001) from University of California, Berkeley. He has been a postdoc at Institute for Advanced Study, Princeton and a faculty member at University of Waterloo, Canada, before returning to University of Latvia in 2007.

Andris Ambainis has made many important contributions to quantum algorithms and complexity theory and is one of the leading experts in the world in computer science aspects of quantum computing. He is an author of over 100 research papers, including 18 papers in two leading theoretical computer science conferences, FOCS and STOC. Andris Ambainis is the youngest ever person elected to Latvian Academy of Sciences in 2007, at the age of 32.