6 Superposition attacks

While before, we looked at blockciphers, and considered the security of them with and without the existence of quantum computers. Quantum computers weakened the algorithm we looked at but, without completely breaking it. This is very typical of symmetric crypto. Today we will look at a situation where quantum computers can make a more drastic difference, namely superposition attacks.

Recall attacks on block ciphers as we have seen so far:

Chosen plaintext attack

In this attack, the adversary can asc to encrypt any $m$’s with a certain fixed key $k$ (unkown to the adversary). Now this exists with many different variants, the common theme is the adversary can talk to something to get information. This may be called challenger, oracle, or similar. Importantly, the message that is sent to the encryption oracle is classical, while the adversary themselves is a quantum computer internally.

This is because the real world scenario involves a classical crypto system (the honest parties), which is attacked by an adversary who has a quantum computer. Considering this is typical for post-quantum cryptography.

The encryption oracle represents an interaction with the protocol execution. In reality, the adversary might be able to inject messages and/or trick honest parties into encrypting them. We represent this using the oracle.

All of this means that the encryption oracle is classical.

Recall the attack against EM. First, the adversary ran a large number of queries to the encryption oracle, and in a second phase ran Grover’s algorithm. The predicate that we are searching ($\mathbb{L}_{\mathbb{D}}(z)=[P(z) \oplus P(\bar{z}) \in \mathbb{D}]$) is queried in superposition. This is allowed because we do not query the oracle but the permutation $P$ in superposition.

Since $P$ represents a publicly known permutation, the adversary is able to construct a circuit to run it on their quantum computer. And, while the adversary could implement a quantum version of the encryption algorithm, it does not know the key $k$. This means that part has to happen in the system of the honest parties, and therfore classically.

In summary, when we say we do an attack with classical queries (or without superposition queries) we typically mean the following.

When the adversary performs a query that computes a function involving the secrets not known to the adversary (e.g. $E_{kl}$ in Section 5.1.4) the query is a classical query. (Cannot do superposition queries).
When the adversary performs a query that computes a function involving only things known to the adversary (e.g. $P$ in Section 5.1.4) the query is allowed to be a superposition query. (Can do superposition queries.)

CBUt somtimes, we can also consider “attacks with superposition queries”. Here $\underline{\text{all}}$ queries are allowed to be superposition queries (e.g. also $E_{kl}$). Here are some arguments as to why.

Due to miniaturization in chip technology, the honest party may accidentally execute things in superposition. For example if you get classical transistors down to one atom, they may behave quantumly. This is maybe a bit far fetched, but the argument has been made in the literature.
We might in the future want to (honestly) use the encryption scheme on a quantum computer on quantum data. As a counterargument: There is something called quantum encryption for quantum data. Just use that!
Sometimes, in security proofs, you do reductions that transform adversaries in complex ways. E.g., one adversary runs another adversary internally in superposition (which might run $E$). We see examples of such things in Sec N/A.

6.1 Extending Strong Permutations to quantum

Recall: Definition 5.1 of (Strong) PRPs. We will now define this for superposition queries.

Definition 6.1 $(E,D)$ is a $(t,\epsilon)$-$\color{red}\text{strong}$ qPRP iff:

for all keys $k$: $E(k, \cdot)$ is a permutation
for all $k$: $D(k, \cdot)$ is the inverse of $E(k, \cdot)$
for all $t$-time quantum adversaries $A$: $\lvert Pr[b = 1: k \xleftarrow{\$} \mathcal{K}, b \xleftarrow{\$} A^{E(k, \cdot),\color{red}D(k, \cdot)\color{black}}()] - Pr[b = 1: \pi \leftarrow Perm(\mathcal{M}\rightarrow \mathcal{M}),b \leftarrow A^{\pi, \color{red}\pi^{-1}\color{black}}()] \leq \epsilon$. Here $\mathcal{K}$ is key space, $\mathcal{M}$=$\mathcal{C}$ are message space and ciphertext space.

Here all oracles $(E(k,\cdot), D(k,\cdot), \pi, \pi^{-1})$ are given to the adversary as quantum oracles. (A.k.a. superposition oracles.)

In the classical case, oracles are given a bit of data (e.g. a bitstring or a number) and then return their answer to that query (e.g. another bitstring or a bit). In the quantum case, we cannot do that anymore, since we now want a superposition query to be possible. Instead, when the adversary makes a query to a quantum oracle $\mathbb{O}$ (where $\mathbb{O}$ is a function $\mathbb{O}:\{0,1\}^n\rightarrow \{0,1\}^m)$, the adversary provides two registers $X$ and $Y$ consisting of $n$ and $m$ qubits, and then the oracle applies the unitary $(U_{\mathbb{O}}\ket{x,y}\rightarrow \ket{x,y\oplus \mathcal{O}(x)})$ applied to them.

6.2 Quantum-attacking Even-Mansour

This is quite a bit more powerful. Even-Mansour for example is completeley broken by using superposition-attacks. We get a key recovery with $\mathbb{O}(n)$ queries.

We will do this using Simon’s algorithm. This algorithm solves the abstract problem of finding a function period. Let the classical function $f: \{0,1\}^n \rightarrow \{0,1\}^m$ be $t$-periodic with respect to $\oplus$. That is, $f(x) = f(x \oplus t)$. We want the period $t$ to be the only period you can find, since the task is finding it. (This, and “normal” period finding are special cases of “hidden sub-group problems”). This problem is exponentially hard classically.

6.2.1 Simon’s algorithm

We start off with two registers, one with $n$ and $m$ qubits respectively, and initialize them with zeroes. As a natural start, we apply a Hadamard to the first register, producing a uniform superposition over all possible values of this register $(2^{-n/2}\sum_x \ket{x,0})$. We then use the function $\operatorname{U_f}$ to evaluate our function $f$ in superposition $(2^{-n/2}\sum_x \ket{x,f(x)})$. As a final step we measure the lower wire, netting us a value $y$. The upper wire now contains the sum of all possible amplitudes of values $x$ for which $f(x)=y$ $(for x s.t. f(x)=y: \alpha \sum_x \ket{x,f(x)})$. This means because of the periodicity, we can write the state as the superposition of the two points where the function are the same: $\alpha \ket{x_0,f(x_0)} + \alpha \ket{x_0 \oplus t, f(x_0 \oplus t)}$. This also makes it clear that alpha is $1/\sqrt{2}$. Therefore, we can write the state as: $1\sqrt{2}( \ket{x_0} + \ket{x_0 \oplus t}) \otimes \ket{y}$. The first part being on the top wire, and $\ket{y}$ on the bottom wire. Here, we apply the Hadamard because it has similar properties to the DFT.

A result we are going to use here, is that $H^{\bigotimes n}\ket{x}=2^{-n/2}\sum_x (-1)^{xz}\ket{z}$ (*).

We then get the following state $\Psi_1$ on the first wire: $1/sqrt{2} H^{\otimes n}\ket{x_0} + 1\sqrt{2} H^{\otimes n}\ket{x_0 \oplus t} \stackrel{*}{=} \frac{2^{n/2}}{\sqrt{2}}(\sum_z (-1)^{x_0\cdot z}\ket{z} + (-1)^{x_0\cdot z + t\cdot z}\ket{z})$.

Note: Here the inner product $(\cdot)$ is defined as: $a\cdot b = \sum a_i b_i \mod 2$.

When determining the content of the sum in the parantheses, we have to differentiate between two cases:

$\pm 2*\ket{z}$ (if $t\cdot z = 0$)
$0$ (if $t\cdot z = 1$)

This is equal to $\beta \sum_{z s.t. t\cdot z =0}\pm \ket{z}$, meaning the outcome $z$ satisfies $t\cdot z=0$. In the end, this quantum circuit gives us a uniformly random $z$ with $t \cdot z = 0$. This linear equation with one unknown, for which we can solve.

6.2.2 The attack

Recall that Even-Mansour blockcipher was defined as $E(kl,m)=P(m\oplus k)\oplus l$. We define a function $f(x):=P(x)\oplus E(kl,x)$. Plugging in the definition of E gives us $f(x):=P(x)\oplus P(x\oplus k)\oplus l$. Does this function have a period? Indeed it does. Plugging $x\oplus k$ into $f$ shows us that $f(x):=P(x\oplus k)\oplus P(x\oplus k \oplus k)\oplus l = f(x)$, meaning $k$ is our period, and $f$ is $k$-periodic.

We now need to construct a quantum circuit to compute $\operatorname{U_f}$.

This is surprisingly simple. After applying $U_P$, the top wire has $\ket{x}$ on it, and $\ket{y\oplus P(x)}$ on the bottom wire. Now applying $U_{enc}$ gives us still $\ket{x}$ on the top wire. The bottom wire however, has $\ket{y\oplus P(x)\oplus E(kl,x)}$. You might already recognize, that is exactly $\ket{y\oplus f(x)}$. That means this computes $U_f$. Now, Simon’s algorithm finds periodic $k$ of $f$ in $O(\lvert k \rvert) = O(n)$ evaluations of $U_f$, so also in just as many queries.

Though we do not have the key, we have half of it. Computing $E(kl,0) \oplus P(k)$ (using an encryption query), which is equal to $P(0\oplus k)\oplus l \oplus P(k)$. The $k$’s cancel out, and we are left with $l$.

In summary, we computed the whole key $kl$ in a linear number of queries. Therefore, following our definition, EM is a qPRP.

	Best attack	Security proof
class	$2^{n/2}$	$2^{n/2}$
PRP	$2^{n/3}$	$2^{n/3}$
qPRP	$n$	-

This table shows the best attacks we now, and the security proofs for them. This means how fast we can currently break it, and whether this is already the theoretical maximum. This is the case for the first two attacks, with the runtime of the quantum attack already being so good no one has bothered to show if it can be done faster.

It should be noted that the classical and PRP attacks have large memory requirements. For the quantum evaluations, we need this memory to be quantum readable. This QROM is a steep requirement that bears to keep in mind.

The PRP attack can also be done in polynomial memory if you use a different attack that we will not cover here.