Quantum attack on CTR

Question

I'm reading the article named "Characterizing the qIND-qCPA (in)security of the CBC, CFB, OFB and CTR modes of operation".

An attack on CTR mode is presented in the article. The proof of thm 1 states:

• Adversary prepares the state $|+\rangle$ and makes a query to embedding oracle using it.
• Adversary receives $\sum_{x}|x\rangle|x\oplus s\rangle$ (in $b = 0$ case). Slightly different sum the adversary receives in $b=1$ case.

Here is the question: why we have sum over all $x$ here? An embedding oracle receives $|x\rangle$ and sends back $|x\rangle|f(x)\rangle$. I.e. the first register remains unchanged.

Why we have sum over $x$ (with eqaul coefficients) in the oracle's answer then?

Answer 1

why we have sum over all $x$ here?

The difference here is notational. We use the + operator not to mean 'addition with some group operation', but instead that the state can be represented by a combination of orthogonal base states.

For example, if we have a state where we have two base vectors |0> and |1>, and they are of equal amplitude, we can represent the state as |0> + |1>.

Now, if we have $n$ such orthogonal base vectors, we can use the $\sum$ notation to mean |0> + |1> + ... + |n-1> in the obvious manner.

Now, when they write |+> (not to be confused with the + notation above), what they mean can be represented as $\sum_x$ |x>, however that misses a fine point. |+> can be generated (and this is what the proof means by preparing) by taking the |0> state and applying the Hadamard (H) operator; in the 'computational basis' (which is the basis used in the representation $\sum_x$ |x>) every bit pattern has an equal amplitude. However, there exists an alternative basis where the only nonzero amplitude is on a specific basis vector (denoted as +). The reason this is important is if take this state, and apply the Hadamard operator to it again, it'll move it back to the |0> state; this does not apply to an arbitrary state, even if that state has equal amplitude with respect to all computational basis vectors (that is, performing a measurement on that state will generate all possible values with equal probability).

I.e. the first register remains unchanged.

Welcome to Oz (that is, Quantum Mechanics), where this is not true (!). In classical computation, reading a value has no effect on that value. However, in Quantum Computation, it does. This is not a trivial point; if you don't understand it, their proof will not make any sense.

The effect of taking |x>|0> and converting that into |x>|f(x)> is that the components become entangled, and in particular, if the |x> side was initially a pure |+> state, it no longer is.

What they do is they the |x>|f(x)> state (which they get from their encryption oracle) and change that into |x>|f(x) ⊕ x>. This again affects the left side; if f(x) was $x \oplus s$ (for some secret constant $s$), then the state is |x>|s>; that is, the two sides are no longer entangled, and so the left side goes back to a pure |+> state. If f(x) is something else, the two sides are sides are still entangled, and so the left side is something other than a pure |+> state.

They then use a Hadamard operator (and a measurement) to test the left hand side to see if it was a pure |+> state.

Yes, Quantum Mechanics is weird. It is not irrational; it is just highly counterintuitive to anyone who hasn't worked with it a lot...

Answer 2

Disclaimer: I'm one of the authors of the article.

---

poncho's answer is great, but I'd like to just add some additional details that may help you in understanding the article.

When describing the action of a quantum oracle, it is enough to give its action on the basis states. Think of it as the equivalent classical result that knowing the action of a matrix on each vector of some basis completely characterizes it.

However, you have to recall that the oracle is applied to a superposition of states. Mathematically, this simply means that if you have a quantum state: $$|\psi\rangle=\sum_i\alpha_i|i\rangle$$ And you want to apply some oracle $\mathcal{O}$ on it. Since $\mathcal{O}$ is in fact a matrix you will just have, by linearity: $$\mathcal{O}|\psi\rangle=\sum_i\alpha_i\mathcal{O}|i\rangle$$ And now, if you know the expression of $\mathcal{O}|i\rangle$, you can just replace it.

In this case, we first start from the $|+\rangle$ state (which is an abuse of notation, it should be $|+\rangle^{\otimes n}$ really), which is, omitting normalization: $$\sum_x|x\rangle$$ We then only have to use the definition of the embedding oracle: $$\mathcal{O}|x\rangle=|x\rangle|f(x)\rangle$$ Thus, we use the linearity to obtain the expression of our state after having applied the oracle: $$\sum_x|x\rangle|f(x)\rangle$$ And this is why there is a sum over the $x$s: it comes from the fact that $|+\rangle$ is a superposition on the basis states, and from the fact that applying an oracle is done using linearity.

In the case of the CTR mode, we have $f(x)=x\oplus s$ since this is a stream cipher, and this gives you the expression in the article.

---

As a side note, it's also an abuse of notation to write: $$\mathcal{O}|x\rangle=|x\rangle|f(x)\rangle$$ Because the vectors don't have the same size here. What happens when using an embedded oracle is that a $|0\rangle$ state will be appended to the state prior to querying the oracle.