Cybersecurity in an era with quantum computers: Will we be safe?, QCrypt 2005 invited talk, available at http://2015.qcrypt.net/wp-content/uploads/ 2015/10/Invited7 Michele-Mosca.pdf

Cyber technologies are becoming an increasingly important part of all facets of our lives. Consequently, cybersecurity is a fundamental and growing part of what it means for us to be safe. One of the most fundamental pillars of cybersecurity is cryptography. Most of the cryptography tools we use today rely on computational assumptions, such as the hardness of factoring 2048 bit numbers. These computational problems are sometimes broken (e.g. [Tut00], [BFMV84], [FMS01], [WY05]) by algorithmic advances or increased computing power. Two decades ago, we learned that the quantum paradigm implies that essentially all the deployed public key cryptography will be completely broken by a quantum computer [Sho94] and that brute force attacks of symmetric ciphers can also be sped up by roughly a quadratic factor [Gro96, BBHT98]. Most new paradigms are not initially greeted with great acceptance, as described nicely in the Max Planck quote [Kuh70]: “A new scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die, and a new generation grows up that is familiar with it. ” There has been much skepticism about the prospect of a large scale quantum computer in the forseeable future (or ever) capable of implementing Shor’s algorithms or quantum searching. People naturally ask if they can continue to delay taking action, since there are many other urgent and seriou