QUANTITY - Quantum-assisted Cryptanalysis
Security for cryptosystems in the age of powerful quantum computers
The QUANTITY project is investigating the security of cryptosystems in the age of powerful quantum computers. In addition to known, cryptographically relevant quantum algorithms, other algorithms are also being analyzed and adapted in order to evaluate the effects on the security of cryptosystems.
Anyone who wants 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 considered to be quantum-resistant if they can withstand attacks by the quantum algorithms of Shor and Grover. In the QUANTITY project, we develop the application of quantum algorithms in cryptanalysis methods for quantum-resistant cryptosystems and analyze them in order to determine the security of cryptosystems in the presence of powerful quantum computers. We first determine potential speedups of classical cryptanalysis methods using quantum algorithms and the cryptographic relevance of existing quantum algorithms. Based on these results, we will develop novel quantum computer-assisted cryptanalysis methods and validate them by means of a proof-of-concept implementation.
Motivation
Advances in quantum computing have a significant impact on the security of cryptosystems. For example, Grover's quantum search algorithm and Shor's quantum factorization 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 resistant if they can withstand all currently known attacks on both classical and quantum computers. Quantum resistant cryptosystems are therefore essential to ensure data security in the age of powerful quantum computers.
The Challenge
Currently, the term quantum resistant primarily refers to "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 considered, namely 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. The analysis and development of 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 resistance.
