Quantum Chosen-Ciphertext Attacks Based on Simon’s Algorithm Against Unified Structures
摘要
Simon’s algorithm, which constructs periodic functions from encryption and decryption oracles of a cipher, has shown great power in breaking symmetric ciphers. This paper studies the quantum chosen-ciphertext attacks (qCCA) distinguishers based on Simon’s algorithm and the general technique to build such distinguishers. The qCCA distinguishers can be divided into distinguishers that use only the decryption oracle and those that use the encryption oracle. We refer to these two types of distinguishers as the \(\textsf{qCCA}^{d}\) distinguishers and the \(\textsf{qCCA}^{e}\) distinguishers, respectively. Firstly, we show the general methods of constructing \(\textsf{qCCA}^{d}\) distinguishers exploiting truncated differential, which can explain the previous work, that is, constructing Simon-based \(\textsf{qCCA}^{d}\) distinguishers of primitives case by case. Secondly, we explored the relations between periodic functions used by \(\textsf{qCCA}^{e}\) distinguishers and boomerang distinguishing attacks. Specifically, we deeply observed truncated boomerang attacks and introduced the definition of truncated boomerang differential to find the relations. The basic observation is that an improved truncated boomerang differential with probability 1 can be used to construct periodic functions, and two such constructions are presented. With these new construction techniques, we present new qCCA distinguishers of unified structures that unify the Feistel, Lai-Massey, MARS-like, and SM4-like structures. In particular, for the d-branch MARS-like and SM4-like structures, we prove the existence of 2d-round qCCA distinguishers that are the best results so far as we know.