**The advent of quantum computers. Time to panic?**

Quantum computing started as an idea to make our simulations of quantum effects in nature more precise, and more efficient. However this idea was not given much attention, as the classical computers were still getting faster, and capable of better simulations even without the utilization of quantum effects. This changed when Peter Shor presented a quantum algorithm that can quickly factor RSA moduli and compute discrete logarithms. This has effectively shown that almost entire public key cryptography is vulnerable to an attack by a quantum computer. From that day on, the quantum computers are in the centre of interest of cryptologists and technological giants from all around the world.

The power of quantum computers comes from the fact that they are in some sense capable of performing the same calculations on exponentially many inputs in terms of the input length. We shall emphasize this does not mean they can simply break a general encryption algorithm simply by trying all possible keys in parallel and then guess the correct one. Despite the quantum parallelism noted above, we can finally measure only one result that is chosen randomly with certain probability.

Fortunately, in quantum computers, the aforementioned probabilities are governed by amplitudes whose coefficients can be negative or even complex numbers. Thanks to this fact, the amplitudes (and so the probabilities) can actually interfere in either constructive or destructive way. The art of designing quantum algorithms is then to try to amplify the probabilities of correct results, and cancel out the probabilities of incorrect ones. In our lecture, we will use practical examples to illustrate this approach.

To mitigate the threat of quantum attacks, two main approaches emerge – quantum key distribution (QKD) and quantum resistant classical cryptography (so called post-quantum cryptography, PQC). The advantage of QKD is that it utilizes the very power of quantum mechanics to ensure that the distributed key was not eavesdropped. This works, since any observation of an unknown quantum bit inevitably affects its state, so any attempt to tap the channel can be detected. However, due to the same reason, the protocol is not resilient with respect to DoS attacks, as any attempt to tap the channel will also prevent the key distribution.

On the other hand, PQC only requires replacing standard assumptions of computational hardness used in contemporary cryptosystems. In particular, we shall not base our cryptosystems on the hardness of factoring, but use problems that are still hard even for quantum computers.

In the lecture, we will also touch the following questions: When should we expect the first quantum attack? What is the threat of retroactive cryptanalysis? How do these attacks actually work? Can we defend ourselves? How to develop countermeasures? Does the advent of quantum computers mean the end of cryptography as we know it today?

**Jiří Pavlů**

Holds a master degree in mathematics for information technologies from MFF UK. He specializes in theoretical cryptography, especially on the security and usability of symmetric ciphers, and coding theory. He is a cryptologist of the competence centre of Raiffeisen Bank International group.

**Tomáš Rosa**

Holds Ph.D. in cryptology, his doctoral dissertation was awarded the Best Doctoral Work Award of the rector of ČVUT in 2004. He studied on FEL ČVUT and MFF UK in Prague. He deals with mathematical and physical methods of computer security, especially in embedded and radio applications. His work also improved a number of world-wide standards – TLS protocol, EMV scheme, Bluetooth, and GNSS. He is the chief cryptologist of the competence centre of Raiffeisen Bank International group.