QUANTITY

Anyone who needs to be able to determine the security level of cryptosystems in the age of powerful quantum computers must have a deep understanding of the cryptographic relevance of quantum algorithms*. Currently, cryptosystems are deemed to be quantum computer-resistant if they can withstand attacks by Shor’s and Grover’s quantum algorithms. In QUANTITY, we are developing applications of quantum algorithms in cryptanalysis methods for quantum computer-resistant cryptosystems and analysing them to determine the security of cryptosystems in the presence of powerful quantum computers. We will first determine potential speed-ups of classical cryptanalysis methods using quantum algorithms and the cryptographic relevance of existing quantum algorithms. Based on these findings, we will develop novel quantum computer-assisted cryptanalysis methods and validate them using a proof-of-concept implementation.

Motivation

Advances in quantum computing have significant implications for the security of encryption systems. For example, Grover’s quantum search algorithm and Shor’s quantum factorisation algorithm reduce the security level of symmetric and asymmetric encryption methods respectively. While the threat posed by Grover’s search algorithm can be averted by increasing the key length, most of the asymmetric public key methods currently in use, such as Rivest-Shamir-Adleman (RSA), Diffie-Hellman (DH) and methods based on elliptic curves (ECC), are completely broken by Shor’s algorithm. Cryptosystems are considered quantum computer-resistant if they can withstand all currently known attacks on both classical and quantum computers. Quantum computer-resistant cryptosystems will therefore be essential to ensure data security in the age of powerful quantum computers.

Challenge

Currently, the term quantum computer-resistant primarily means “resistant to attacks using Shor and Grover”. However, such a definition only covers a very small part of the possible attacks using quantum algorithms. To determine the security level of encryption methods, the most efficient attacks must be taken into account, on both classical and quantum computers. In order to carry out a cryptanalysis of such methods, the complexity of the solution to the problem underlying the corresponding encryption system must be determined. A promising approach here is the combination of classical cryptanalysis methods with novel or existing quantum algorithms. Analysing and developing cryptographically relevant quantum algorithms thus makes an important contribution to determining the long-term security level of encryption methods and to hardening the concept of quantum computer resistance.