Consequences of Grover's algorithm

Question

I want to look more closely at the consequences of the Grovers algorithm. As is well known, the algorithm provides a quadratic improvement compared to classical search algorithms.

Specifically, I would be interested in the implications of Grover's algorithm on modern cryptography. So how is the influence of grover's algorithm on cryptography. Maybe someone here has some good tips and sources where you can read something, or where something is discussed.

I would be very grateful if anyone knows scientific papers that investigate this influence. Also, I would be interested in the weaknesses of the algorithm, what are the practical implications? So if anyone knows of any scientific sources dealing with this problem I would be very happy if you can share this.

Answer 1

In this survey article they discuss Grover's algorithm. In my opinion, the most important part:

Grover’s speed-up from $N$ to $\sqrt{N}$ is not as devastating as Shor’s speed-up. Furthermore, each of Grover’s $\sqrt{N}$ quantum evaluations must wait for the previous evaluation to finish. To quantify this issue, define T as the number of serial evaluations that can be carried out in the time available: for example, if the quantum computer can evaluate f in a nanosecond, and if the attacker is prepared to run a computation lasting for a year, then T≈$2^{55}$. If $\sqrt{N}$ exceeds T, then Grover’s algorithm cannot use fewer than N/T evaluations spread across $N/T^2$ parallel quantum processors. This is a factor T better than pre-quantum techniques, but it is possible that this improvement will be wiped out by the overhead of qubit operations being more expensive than bit operations, making Grover’s algorithm useless—even if scalable quantum computers are built and run Shor’s algorithm successfully.

This is the main and oft-discussed issue, that Grover's algorithm parallelizes very badly (provably so: Zalka 1997). Bear in mind that our usual classical heuristics of security - $2^{80}$ operations, say - are based on extremely parallel architectures.

Here's another paper discussing the same issue and suggesting a fixed time limit for post-quantum security definitions. NIST included maximum depths in their definitions of quantum security for the post-quantum cryptography standardization process (See Section 4A).

Some other issues: Grassl et al. give circuits for AES, showing that reversibility also adds some noticeable overhead.

Also, Grover's algorithm has a very high depth compared to Shor's algorithm, meaning the qubits and circuit need to have very, very low errors. This will, in turn, create large (though poly-logarithmic) overheads for error correction.

So:

1. As far as I know, no one is trying to build any "quantum-safe" symmetric cryptography, because modern symmetric cryptography is already quantum-safe (Grover's algorithm is still exponential)

2. Because of the practical issues I mentioned, the key sizes may not even not to increase

3. Sill, it's not too hard to eliminate even what little risk there is; from the same survey article:

On the other hand, if qubit operations are small enough and fast enough, then Grover’s algorithm will threaten many cryptographic systems that aim for $2^{128}$ security, such as 128-bit AES keys. We recommend simply switching to 256-bit AES keys: the extra costs are rarely noticeable. ‘Information-theoretic’ MACs such as GMAC and Poly1305 already protect against quantum computers without any modifications: their security analysis already assumes an attacker with unlimited computing power.