We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take $O(\sqrt{N}\text{ }\text{ln}\text{ }N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in $O(\sqrt{N\text{ }\text{ln}\text{ }N})$ steps, thus giving an $O(\sqrt{\text{ln}\text{ }N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take $O(\sqrt{N}\text{ }\text{ln}\text{ }N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in $O(\sqrt{N\text{ }\text{ln}\text{ }N})$ steps, thus giving an $O(\sqrt{\text{ln}\text{ }N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

arXiv:0801.0497Physical Review AJul 9, 2008185 citations

Quantum Meet-in-the-Middle Attack on Feistel Constructions

Yinsong Xu, Zheng Yuan

Quantum attacks on Feistel constructions have attracted much attention from worldwide crytologists. To reduce the time complexity of quantum attacks on $r$ -round ( $r \ge 7$ ) Feistel construction, we propose a novel quantum meet-in-the-middle (QMITM) attack. For 7-round Feistel construction, we introduce quantum computing in the offline computation of the classic meet-in-the-middle (MITM) attack [Guo2016], i.e., propose a quantum claw finding algorithm based on quantum walk, which speeds up the process of finding a match in the offline computation phase. The keys in 7-round Feistel construction could be recovered by the match at last. Furthermore, to attack $r$ -round ( $r > 7$ ), we use amplitude amplification algorithm to search the last $r-7$ rounds of keys. Compared with other quantum attacks in Q2 model, our attack reduces the time complexity from $O({2^{0.25nr - n}})$ to $O({2^{2n/3 + (r - 7)n/4}})$ , and is significantly better than classic attacks. Moreover, our attack only needs to make classical online queries, without quantum superposition queries in other quantum attacks, which is more practical.Quantum attacks on Feistel constructions have attracted much attention from worldwide crytologists. To reduce the time complexity of quantum attacks on $r$-round ($r \ge 7$) Feistel construction, we propose a novel quantum meet-in-the-middle (QMITM) attack. For 7-round Feistel construction, we introduce quantum computing in the offline computation of the classic meet-in-the-middle (MITM) attack [Guo2016], i.e., propose a quantum claw finding algorithm based on quantum walk, which speeds up the process of finding a match in the offline computation phase. The keys in 7-round Feistel construction could be recovered by the match at last. Furthermore, to attack $r$-round ($r > 7$), we use amplitude amplification algorithm to search the last $r-7$ rounds of keys. Compared with other quantum attacks in Q2 model, our attack reduces the time complexity from $O({2^{0.25nr - n}})$ to $O({2^{2n/3 + (r - 7)n/4}})$, and is significantly better than classic attacks. Moreover, our attack only needs to make classical online queries, without quantum superposition queries in other quantum attacks, which is more practical.

Jul 27, 20210 citations

We consider the problem of finding a desired item out of

N

items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take

O(\sqrt{N}\text{ }\text{ln}\text{ }N)

steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in

O(\sqrt{N\text{ }\text{ln}\text{ }N})

steps, thus giving an

O(\sqrt{\text{ln}\text{ }N})

improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

Quantum attacks on Feistel constructions have attracted much attention from worldwide crytologists. To reduce the time complexity of quantum attacks on

r

-round (

r \ge 7

) Feistel construction, we propose a novel quantum meet-in-the-middle (QMITM) attack. For 7-round Feistel construction, we introduce quantum computing in the offline computation of the classic meet-in-the-middle (MITM) attack [Guo2016], i.e., propose a quantum claw finding algorithm based on quantum walk, which speeds up the process of finding a match in the offline computation phase. The keys in 7-round Feistel construction could be recovered by the match at last. Furthermore, to attack

r

-round (

r > 7

), we use amplitude amplification algorithm to search the last

r-7

rounds of keys. Compared with other quantum attacks in Q2 model, our attack reduces the time complexity from

O({2^{0.25nr - n}})

O({2^{2n/3 + (r - 7)n/4}})

, and is significantly better than classic attacks. Moreover, our attack only needs to make classical online queries, without quantum superposition queries in other quantum attacks, which is more practical.