# Can we apply Grover to meet-in-the-middle attack?

$$\newcommand{\Ket}[1]{\left|#1\right>}$$ If we have the superposition $$\displaystyle \sum \dfrac{1}{2^n} \Ket x \Ket{ f(x)} \Ket 0 \Ket y \Ket{g(y)} \Ket 0 \Ket {\delta_{x,y}} ,$$ here $$\delta_{x,y} = 1$$ if $$f(x) = g(y)$$, else $$\delta_{x,y}=0$$. I want to copy $$\delta_{x,y}$$ to qubit $$\Ket 0$$ by some ways so that it becomes superpositon $$\left(\displaystyle \sum \dfrac{1}{2^{n/2}} \Ket x \Ket{f(x)}\Ket {\delta_x} \right) \left(\displaystyle \sum \dfrac{1}{2^{n/2}} \Ket y \Ket{g(y)} \Ket{\delta_y} \right) \Ket 0 ,$$ means that $$\delta_x = 1$$ if $$f(x)$$ collides with some $$g(y)$$, and so does $$y$$. After that, apply Grover's algorithm on the first half and second half to find $$x$$ and $$y$$ that collides, in $$O(2^{n/4})$$ time complexity.

Is there any way to copy like this?

• I may be misunderstanding something, but why wouldn't $\delta_x$ and $\delta_y$ always be equal to $1$? It looks like both $x$ and $y$ are $n$-bit strings which are iterated over all possible values. – dlyongemallo Jan 18 at 0:27
• Yes, $x,y$ are $n$-bit string and are iterated over all values. If x collides with some y, then $\delta_{x,y} =1}$, and I copy it to $\delta_x$ and $\delta_y$. But to make the second superposition, if x collides with some y, we have to copy $\delta_x=1$ to all other $y’$ which do not collide x. How to do it? – Phuong Pham Thi Minh Jan 19 at 2:51
• But if both $x$ and $y$ are iterated over all values, every single one of them will have a collision. If $x$ collides with some $y$, you say that you want to copy $\delta_{x} = 1$ to all other $y'$ which do not collide with $x$, but $y'$ must collide with some $x'$, no? In other words, there should be no need to do what you're asking. Instead of $x$ and $y$, did you mean for example some function $f(x)$ and $f(y)$? Otherwise, can you work out an example with $n=1$ maybe so I can see where there would even be a $|0\rangle$ to "copy" to? I think $\delta_{x}=\delta_{y}=1$ for all $x,y$ already. – dlyongemallo Jan 19 at 16:38
• Sorry for my mistake. You're right, I mean $f(x)$ and $f(y)$ here. I am trying to quadratic speedup the classical meet-in-the-middle attack, so $x$ and $y$ are subkeys guesses of the first half and second half of a cipher. – Phuong Pham Thi Minh Jan 20 at 7:26
• So you simply want to amplify the amplitude of all the components with $\delta_{x,y}=1$? So long as you have a unitary that produces that top state, this is exactly what the amplitude amplification algorithm does. – DaftWullie Jan 20 at 8:00