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

作     者：CHEN Yu-Ao GAO Xiao-Shan CHEN Yu-Ao;GAO Xiao-Shan

作者机构：Academy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing 100190China University of Chinese Academy of SciencesBeijing 100049China 

出 版 物：《Journal of Systems Science & Complexity》 (系统科学与复杂性学报（英文版）)

年 卷 期：2022年第35卷第1期

页      面：373-412页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 070201[理学-理论物理] 0701[理学-数学] 0702[理学-物理学] 

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

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

摘      要：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 *** runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with *** 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 *** 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 *** leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers:The corresponding condition number.