Theoretical advances in practical quantum cryptography

Abstract

Most of themainstream cryptographic protocols that are used today rely on the assumption that the adversary has limited computational power, and that a given set of mathematical problems is hard to solve (on average), i.e. that there is no polynomial time algorithm that solves these problems. While these assumptions are reasonable for now they might not be as relevant for long termsecurity. Indeed, all the communication that happens today can be recorded by an adversary who can later – when the technology allows it – break security. There are good reasons to think that technological progress may lead to break the assumptions made today. For example the rapidly increasing computational power of our computer already allows one to break anything that has been encrypted using DES in the 70s and 80s in few days using regular desktop type devices. There is also the constant improvement of the efficiency of the known algorithms that solve a class of problems. Note that, even though the discovery of a polynomial algorithm for a problem we believe to be hard is still possible, much weaker improvements on current algorithms that solve these hard problems, can already be a threat for security.