Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems  

作　　者：CHEN Yu-Ao GAO Xiao-Shan 

机构地区：[1]Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China [2]University of Chinese Academy of Sciences,Beijing 100049,China

出　　处：《Journal of Systems Science & Complexity》2022年第1期373-412,共40页系统科学与复杂性学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant No.11688101and NKRDP 2018YFA0704705。

摘　　要：This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability.The runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with F.As a consequence,the authors give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are polynomial in the size of F.The authors apply the proposed quantum algorithm to the cryptanalysis of several important cryptosystems:The stream cipher Trivum,the block cipher AES,the hash function SHA-3/Keccak,the multivariate public key cryptosystems,and show that they are secure under quantum algebraic attack only if the corresponding condition numbers are large.This leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers:The corresponding condition number.

关 键 词：Block cipher AES Boolean equation solving condition number hash function SHA3/Keccak HHL algorithm MPKC polynomial system solving quantum algorithm stream cipher Trivum 

分 类 号：O413[理学—理论物理] TN918.1[理学—物理]