On Quantum Related-Key Attacks on Iterated Even-Mansour Ciphers

The impacts that quantum computers will have on cryptography have become more and more important to study for not only public key cryptography but also symmetric key cryptography. For example, at ISITA 2012, Kuwakado and Morii showed that an adversary with a quantum computer can recover keys of the Even-Mansour construction in polynomial time by applying Simon's algorithm. In addition, at CRYPTO 2016, Kaplan et al. showed that Simon's algorithm can also be used to perform forgery attacks against MACs and exponentially speed-up a slide attack. This paper introduces a tool for finding the period of a function that is periodic up to constant addition and shows that a quantum adversary can use the tool to perform a related-key attack in polynomial time. Our quantum related-key attack is an extension of the quantum slide attack by Kaplan et al. against iterated Even-Mansour ciphers that are implemented on quantum circuits. Although the relationships among keys are strong, our algorithm can recover all the keys of a two-round iterated Even-Mansour cipher in polynomial time.