request@qapp.tech
RU
Grover's Search Algorithm

Summary

Grover's algorithm is a quantum algorithm for unstructured search, i.e. essentially solving the f(x)=y equation, where f is a Boolean function of n variables. Grover's algorithm is based on the physical effect called amplitude amplification of the target state. The algorithm can quadratically reduce the search problem complexity, i.e. instead of O(N) operations that a classical computer requires for a brute-force search, a quantum computer can solve the problem in O(N1/2) operations. Grover's algorithm can be efficiently applied to cryptanalysis problems. For example, in the case of block ciphers (AES, etc.), the quadratic brute-force search speedup by Grover's algorithm requires doubling the key length for the cipher to maintain the initial level of robustness.
More on the topic

The quantum search algorithm (sometimes called a database search algorithm), developed by the American mathematician Lov Grover in 1996, is applied to various cryptanalysis problems. For a given Boolean function f of n variables, Grover's algorithm can solve the equation f(x)=y in O(N1/2) operations, while the classical brute-force algorithm requires O(N) operations.
    If we consider the problem of decrypting a block cipher with an n-bit-long key as a Boolean function-inversion problem, Grover's algorithm can solve it in 2n/2 operations, in contrast to the classical computer taking 2n operations. Thus, for a block cipher to maintain a given level of robustness against quantum computer attacks, it is necessary to double the key length.

    Similarly, if we consider the problem of finding a hash function preimage, one also needs to double the hash code size to maintain the given level of robustness. Note, however, that the BHT quantum algorithm used for finding collisions is more efficient and requires a three-fold hash code size increase.

    Lov Kumar Grover
    Grover's algorithm can also be applied to the analysis of asymmetric cryptographic systems, but in this case, it is usually inferior to specialized algorithms such as Shor's polynomial algorithm for factorization.
    The currently used symmetric cryptographic algorithms, such as the block ciphers AES-256, the hash functions SHA-512, are sufficiently robust against Grover's algorithm, while asymmetric cryptographic algorithms, such as RSA, (EC)DSA, which are usually used along with the symmetric ones, can be considered vulnerable. So much so that in the nearest future, it will be necessary to switch to post-quantum cryptographic algorithms.
    What can you do to protect your data security systems from the quantum threat?

    To integrate post-quantum cryptography solutions into your data security systems, you can use our PQLR SDK library of quantum-resistant algorithms.