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

doi:10.1007/s11424-020-0028-6

	Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
	Chen Yu-Ao 1,2; Gao Xiao-Shan 1,2
刊名	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
	2021-01-12
页码	40
关键词	Block cipher AES Boolean equation solving condition number hash function SHA-3 Keccak HHL algorithm MPKC polynomial system solving quantum algorithm stream cipher Trivum
ISSN号	1009-6124
DOI	10.1007/s11424-020-0028-6
英文摘要	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.
资助项目	National Natural Science Foundation of China[11688101] ; National Natural Science Foundation of China[NKRDP 2018YFA0704705]
WOS研究方向	Mathematics
语种	英语
出版者	SPRINGER HEIDELBERG
WOS记录号	WOS:000608140200002
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/58009]
专题	中国科学院数学与系统科学研究院
通讯作者	Gao Xiao-Shan
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Chen Yu-Ao,Gao Xiao-Shan. Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2021:40.
APA	Chen Yu-Ao,&Gao Xiao-Shan.(2021).Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,40.
MLA	Chen Yu-Ao,et al."Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY (2021):40.