Huiqin Xie

Huiqin Xie, Li Yang

Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting, and proposed a specific related-key attack which can recover the key of block ciphers efficiently, as long as the attacked block ciphers satisfy certain conditions. The attack algorithm employs Bernstein-Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. Afterwards, we rigorously demonstrate the validity of the attack and analyze its complexity. Our work shows that related-key attack is quite powerful when combined with quantum algorithms, and provides some guidance for the design of block ciphers that are secure against quantum adversaries.

Huiqin Xie, Li Yang

Traditional cryptography is suffering a huge threat from the development of quantum computing. While many currently used public-key cryptosystems would be broken by Shor's algorithm, the effect of quantum computing on symmetric ones is still unclear. The security of symmetric ciphers relies heavily on the development of cryptanalytic tools. Thus, in order to accurately evaluate the security of symmetric primitives in the post-quantum world, it is significant to improve classical cryptanalytic methods using quantum algorithms. In this paper, we focus on two variants of differential cryptanalysis: truncated differential cryptanalysis and impossible differential cryptanalysis. Based on the fact that Bernstein-Vazirani algorithm can be used to find the linear structures of Boolean functions, we propose two quantum algorithms that can be used to find high-probability truncated differentials and impossible differentials of block ciphers, respectively. We rigorously prove the validity of the algorithms and analyze their complexity. Our algorithms treat all rounds of the reduced cipher as a whole and only concerns the input and output differences at its both ends, instead of specific differential characteristics. Therefore, to a certain extent, they alleviate the weakness of conventional differential cryptanalysis, namely the difficulties in finding differential characteristics as the number of rounds increases.

Huiqin Xie, Li Yang

In this paper, we study applications of Bernstein-Vazirani algorithm and present several new methods to attack block ciphers. Specifically, we first present a quantum algorithm for finding the linear structures of a function. Based on it, we propose new quantum distinguishers for the 3-round Feistel scheme and a new quantum algorithm to recover partial key of the Even-Mansour construction. Afterwards, by observing that the linear structures of a encryption function are actually high probability differentials of it, we apply our algorithm to differential analysis and impossible differential cryptanalysis respectively. We also propose a new kind of differential cryptanalysis, called quantum small probability differential cryptanalysis, based on the fact that the linear structures found by our algorithm are also the linear structure of each component function. To our knowledge, no similar method was proposed before. The efficiency and success probability of all attacks are analyzed rigorously. Since our algorithm treats the encryption function as a whole, it avoid the disadvantage of traditional differential cryptanalysis that it is difficult to extending the differential path.