How do Shors and Grovers algorithms work

Quantum Secure Algorithms / Post-Quantum Cryptography - Prof. Dr. Norbert Pohlmann


Quantum secure algorithms / post-quantum cryptography

The availability of powerful Quantum computers The consequence for cryptography would be that all currently used asymmetric encryption methods, such as the RSA encryption method, would be insecure. All encryption protocols with which Internet communication is encrypted, such as SSH, TLS, IPSec, PGP, S / MINE, would be unusable from then on. Encrypted or signed e-mail traffic and secure Internet surfing would no longer be possible. This would mean that all business processes in e-commerce would no longer be confidential and therefore any forms of online trading and online banking would effectively no longer be possible.

background

In 1994 the mathematician Peter Shor developed an algorithm with which it is theoretically possible to determine the prime factors of a number N using quantum computers. The special feature of this method is that the problem can be solved considerably faster than with the fastest possible conventional method Factoring algorithm. The security of many asymmetrical encryption methods today is based on the assumption that there is no method that can break down very high random numbers in polynomial time into their prime factors. However, a quantum computer with enough qubits and the Shor algorithm would be able to do just that.

Experts estimate that a 2048-bit RSA key can be broken by a quantum computer with 4000 qubits. In the past 15 years there have been a handful of experimental implementations of Shors algorithm. In 2012 the number 21 was prime factorized. These implementations will not be dangerous to any encryption method, but they mark the start of a turnaround in this field of encryption.

Today's symmetrical encryption methods, such as the Advanced Encryption Standard (AES), would not be able to break a quantum computer with Shors' algorithm. But with the help of another method, the so-called Grover algorithm, a quantum computer would be able to effectively halve the security of these processes.

AES-256 would therefore only be as secure as AES-128 for a quantum computer with the Grover algorithm. To prevent this risk, it would be sufficient to double the length of the key. It doesn't look so easy with asymmetrical procedures. Although there are already algorithms today that could probably withstand attacks by quantum computers, the absolute majority of these only exist in theory. The term post-quantum cryptography is used here.

Post-quantum cryptography

But quantum computing will not only have disadvantages for the security of cryptographic processes. Certain quantum mechanical phenomena, such as the no-cloning theorem, can be used to make connections really secure. This is called quantum cryptography. Assuming that there are currently no computers with enough computing power to crack certain keys, it can be said that current processes are practically secure. With the help of Quantum cryptography however, communication channels can be established that are "absolutely secure". Processes have already been developed in which the security is not based on the computing power of mainframes, but rather on the laws of physics and these cannot be broken by any computer, no matter how powerful.
More specifically, such a method is about the secure exchange of a key via a public channel, more precisely, a quantum channel.

Here qubits are used in the form of photons, for example. These are useful because they can be transmitted relatively easily through fibers or in the air. The information can be encoded on the photons based on their polarization. If an attacker tries to eavesdrop on this public channel, this is not possible without changing the original message and thus falsifying it. This would mean that the two communication participants would find out that they were being eavesdropped and that there would be no key exchange. The obvious advantage of such a connection is the proven secure communication. However, the disadvantages quickly become apparent when one considers the effort required to implement such a quantum channel in practice. This method is already being used today, but so far it has only been applicable over short distances of a little over a hundred kilometers. It is true that photons can be sent relatively easily, but such communication is very susceptible to interference. The transmission distance in cables is severely limited by their attenuation. Transmission through the air over long distances is prevented by the atmosphere.


W.Further information on the term “quantum secure algorithms / post-quantum cryptography”:


Lecture: "Cryptography"

items: “A quantum bit. Quantum computers and their implications for tomorrow's security ”

Information about the textbook: "Cyber ​​Security"

Cyber ​​security glossary:Federal Office for Information Security (BSI)