New paper claims quantum polylog time attack on AES

Question

It is well known that Grover's algorithm can solve AES in $O(\sqrt{n})$ time, which is why symmetric key length needs to be double to maintain their security level in the face of a quantum adversary. A recent eprint paper claims there exists a polylog time attack on AES (or searching unsorted sets in general) using a quantum computer. Can someone familiar with quantum computing comment on the validity of this attack?

Answer 1

I concur with Xavier Bonnetain per lamba's answer, but can add a bit more flesh to what is going on.

Working through the proposed algorithm with an $n$-bit search space, looking for a solution $x$ to $f(x)=y$, the idea is to first of all prepare $n/2$ banks of $n$ single qubit registers in full superposition (e.g. by using $n^2/2$ Hadamard gates). For each bank of registers, we then use another $n$ single qubit registers to compute the function $f$ (which is taken to be a block cipher with variable key taken from the input register and operating on a fixed plaintext in the cryptanalytic example, but I see no great reason not to apply the general Grover question). Thus we have $n/2$ copies of the state $$\frac1{2^{n/2}}\sum_{x=0}^{2^n-1}|x\rangle|f(x)\rangle.$$ In fact each state will only need two distinct bits of $f(x)$, so the above could be done with a single call to $f(x)$ rather than $n/2$ calls. If we write $S_i$ for the $i$th bank of registers we now do a single iteration of Grover's algorithm looking for solutions $x$ such that $f_{2i,2i+1}(x)=y_{2i,2i+1}$ where subscripting denotes considering only the index bits (i.e. we look for all $x$ such that the $2i$th and $(2i+1)$th bits of $f(x)$ match the corresponding bits of $y$). This is a 2-bit search space and we expect Grover's algorithm to succeed in a single iteration and roughly 1/4 of our search space to match the condition.

Each of our $n/2$ banks now consists of roughly $2^{n/2-1}$ states in balanced superposition with other states effectively of zero amplitude: $$S_i=\frac1{2^{n/2-1}}\sum_{x=0\atop f_{2i,2i+1}(x)=y_{2i,2i+1}}^{2^n-1}|x\rangle|f(x)\rangle$$ note that the only $x$ values to appear in all $n/2$ superpositions are the values with $f(x)=y$. There does not seem to be a critical dependency on the division into pairs of bits here; one could for example divide into $n/k$ banks and consider sextuples of bits and use $O(2^{k/2})$ Grover iterations.

The author now observes that if we could take the Hadamard product (componentwise product) of the amplitudes of each value of $x$ across the $n/2$ banks, then all non-causal values of $x$ will have at least one bank where the amplitude is zero (i.e. at least one bank where $f(x)$ fails to match two of the bits of $y$). In this case, the only non-zero amplitudes would be the values of $x$ that we seek and measurement should recover them. This implicitly assumes a renormalisation of amplitudes within the Hadamard product.

Those with a background in quantum computation will have a worry at this point, as the Hadamard product is not reversible and so not a unitary transform. The paper however notes that the Hadamard product is one of a number of matrix operations covered in the paper Compiling basic linear algebra subroutines for quantum computers by Zhao et al. Treating the Zhao paper as a black box resource for computing renormalised Hadamard products then gives the result. However, I believe that the Zhao paper does not quite work in this way. Hadamard products are computed in the Zhao paper by embedding the problem in a larger unitary system and computing an approximation to the Hadamard product. The amplitude of the causal solution is super exponentially small (roughly $2^{-n^2/4}$) and will be lost in the noise of the approximation. Perhaps more precisely, to approximate the answer sufficiently accurately will require an exponentially growing set of resources. I intend to read the Zhao paper more deeply to expand on this.

Answer 2

There is an answer on the PQC mailing list by Xavier Bonnetain (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/orySwdhmjH8/m/ScE8G_ajBgAJ) which I will copy below:

The algorithm begins but doing many grover searches in the key space with the predicate "Does the encryption of M with K matches the expected encryption on bits (2i,2i+1)?" Assuming the proportion of keys that fulfill this property is exactly 1/4, we obtain, in 1 grover iteration, the exact quantum superposition of all matching keys. Now, the idea is that the correct key is the only one that appears in all the superpositions. The Hadamard product allows to get the interstection of 2 quantum superpositions. Thus, by iterating Hadamard products, we can recover the key.

There are 2 main problems:

• in the algorithm, computing a Hadamard product is not efficient, here it would be exponential.
• The claimed result is not possible: this algorithm would efficiently break any block cipher (and probably, beyond that, almost all cryptography) in black box. This violates lower bounds on the quantum security of the ideal cipher.

To summarize, any attack, classical or quantum, against AES (or any cipher), must, at some point, leverage a specific property of the cipher. This is not the case here.

The original paper was withdrawn but can still be accessed here https://eprint.iacr.org/archive/2022/948/20220722:134301.