
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

On Quantum RelatedKey Attacks on Iterated EvenMansour Ciphers
Akinori HOSOYAMADA Kazumaro AOKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.1
pp.2734 Publication Date: 2019/01/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E102.A.27
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Keyword: postquantum cryptography, symmetric key cryptography, quantum superposition attacks, iterated EvenMansour ciphers,
Full Text: PDF(908KB)>>
Summary:
It has been said that security of symmetric key schemes is not so much affected by quantum computers, compared to public key schemes. However, recent works revealed that, in some specific situations, symmetric key schemes are also broken in polynomial time by adversaries with quantum computers. These works contain a quantum distinguishing attack on 3round Feistel ciphers and a quantum key recovery attack on the EvenMansour cipher by Kuwakado and Morii, in addition to the quantum forgery attack on CBCMAC which is proposed independently by Kaplan et al., and by Santoli and Schaffner. Iterated EvenMansour cipher is a simple but important block cipher, which can be regarded as an idealization of AES. Whether there exists an efficient quantum algorithm that can break iterated EvenMansour cipher with independent subkeys is an important problem from the viewpoint of analyzing postquantum security of block ciphers. Actually there is an efficient quantum attack on iterated EvenMansour cipher by Kaplan et al., but their attack can only be applied in the case that all subkeys are the same. This paper shows that there is a polynomial time quantum algorithm that recovers partial keys of the iterated EvenMansour cipher with independent subkeys, in a relatedkey setting. The relatedkey condition is somewhat strong, but our algorithm can recover subkeys with two related oracles. In addition, we also show that our algorithm can recover all keys of the iround iterated EvenMansour cipher, if we are allowed to access i related quantum oracles. To realize quantum relatedkey attacks, we extend Simon's quantum algorithm so that we can recover the hidden period of a function that is periodic only up to constant. Our technique is to take differential of the target function to make a double periodic function, and then apply Simon's algorithm.

