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

doi:10.1007/s11424-020-0028-6

CSpace

	Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
	Chen Yu-Ao 1,2; Gao Xiao-Shan 1,2
	2021-01-12
发表期刊	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
ISSN	1009-6124
页码	40
摘要	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 SHA-3 Keccak HHL algorithm MPKC polynomial system solving quantum algorithm stream cipher Trivum
DOI	10.1007/s11424-020-0028-6
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[11688101] ; National Natural Science Foundation of China[NKRDP 2018YFA0704705]
WOS研究方向	Mathematics
WOS类目	Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000608140200002
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/58010
专题	中国科学院数学与系统科学研究院
通讯作者	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.