Grover’s Quantum Algorithm

Introduction

With the 1996 article “A fast quantum mechanical algorithm for database search,” Indian-American computer scientist Lov K. Grover helped highlight the non-negligible impact of quantum computing on cryptography in use today.

Grover’s work concerns the search method in an unstructured database, therefore devoid of any sorting that facilitates the operation.

To understand the contribution of Grover’s algorithm, a simple example is given. Consider a common telephone directory in which the names appear in alphabetical order and next to each the corresponding telephone number.

Suppose, however, that you have to perform a reverse search with respect to the custom and, therefore, have a certain telephone number of which you want to identify the owner.

What a classic approach involves to solve this problem is to scroll through the list and check the numbers one by one until you find the one you want, identifying the associated name.

So, in the worst case, to find the name you need to check all the numbers in the list except the last one.

Instead, through Grover’s algorithm, a quantum computer would solve the same instance in a much smaller number of “quantum controls” than in the classical case. In particular, we speak of quadratic speed up with respect to the classic case.

This means that, given a search problem, if in the classical case this requires a number N of controls, in the quantum case, with Grover’s algorithm, are sufficient about  \sqrt{N} quantum controls.

Going back to the previous example, if the telephone directory consisted of 10,000 contacts, the classical approach would require 9999 worst-case checks, while the quantum approach would be limited to less than 100.

If a quantum computer with adequate characteristics were made, the most relevant security implications of Grover’s result would be found in the symmetric cryptography in use today.

For example, consider the Advanced Encrytption Standard (AES) encryption scheme with cryptographic key k of 128-bit length and assume that an attacker knows some plaintext-ciphertext pairs and wants to find the key with which, for each of the known pairs, the corresponding cipher text is obtained starting from the plaintext and vice versa.

At the state of the art, there is no known attack that works significantly better than an exhaustive search to identify the key.

In the classical case, the exhaustive search would require about 2^{128} calls to the oracle O to establish k while, in the case quantum, Grover’s algorithm would invoke the oracle U about 2^{64} times with success probability very close to 1.

It often happens that in the current narrative the Grover’s search algorithm is described as a tool that “halves” the security of symmetric cryptography in use today.

This halving is related to the bit length of the key involved, for example breaking AES with key from 128 bit through the Grover algorithm requires a number of invocations to the quantum oracle comparable to the number of invocations to the classic oracle to break AES keyed by 64 bit, through exhaustive search.

Consequently, it is plausible to expect that to restore the security of symmetric schemes, in the light of developments in quantum computing, it is sufficient to double the bit size of cryptographic keys.

However, this would be a particularly conservative choice in practice, as the halving of security can only be considered effective in part for at least two reasons.

The first reason is the difficulty in establishing in a precise way the computational cost of the execution of U, which in any case is considered higher than that of O.

The second aspect to take into consideration is the impossibility of efficiently parallelizing the quantum search algorithm, which would therefore be generically performed in a single quantum processor, while the computational burden of the exhaustive search can be divided among several devices that operate. in a parallel way.

Click the link to read the full article.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.