Quantum period finding based on the Bernstein-Vazirani algorithm (pp65-84)
          Xuexuan Hao, Fengrong Zhang, Yongzhuang Wei, and Yong Zhou
          doi: https://doi.org/10.26421/QIC20.1-2-4
Abstracts: Quantum period finding algorithms have been used to analyze symmetric cryptography. For instance, the 3-round Feistel construction and the Even-Mansour construction could be broken in polynomial time by using quantum period finding algorithms. In this paper, we firstly provide a new algorithm for finding the nonzero period of a vectorial function with O(n) quantum queries, which uses the Bernstein-Vazirani algorithm as one step of the subroutine. Afterwards, we compare our algorithm with Simon's algorithm. In some scenarios, such as the Even-Mansour construction and the function satisfying Simon's promise, etc, our algorithm is more efficient than Simon's algorithm with respect to the tradeoff between quantum memory and time. On the other hand, we combine our algorithm with Grover's algorithm for the key-recovery attack on the FX construction. Compared with the Grover-Meets-Simon algorithm proposed by Leander and May at Asiacrypt 2017, the new algorithm could save the quantum memory.
Key words: quantum cryptanalysis, symmetric cryptography, Bernstein-Vazirani algorithm, Simon's algorithm, FX construction