Solving polynomial systems with noise over F-2: Revisited

doi:10.1016/j.tcs.2017.03.005

	Solving polynomial systems with noise over F-2: Revisited
	Huang, Zhenyu 1,2; Lin, Dongdai 1
刊名	THEORETICAL COMPUTER SCIENCE
	2017-05-09
卷号	676 页码:52-68
关键词	Boolean polynomial system with noise Max-PoSSo ISBS method Cold Boot attack Serpent
ISSN号	0304-3975
DOI	10.1016/j.tcs.2017.03.005
英文摘要	Solving polynomial systems with noise over F-2 is a fundamental problem in computer science, especially in cryptanalysis. ISBS is a new method for solving this problem based on the idea of incrementally solving the noisy polynomial systems and backtracking all the possible noises, and it has better performance than other methods in solving some problems generated from cryptanalysis. In this paper, some further researches on ISBS are presented. The structure and size of the search tree of ISBS are theoretically analyzed. Then two major improvements, artificial noise-bound strategy and s-direction approach, are proposed. Based on these improvements, a modified ISBS algorithm is implemented, and the experiments of solving the Cold Boot key recovery problems of the block cipher Serpent with symmetric noise, show that this modified algorithm is more efficient than the original one. (C) 2017 Elsevier B.V. All rights reserved.
资助项目	National Key Basic Research Program of China[2013CB834203] ; National Key Research and Development Plan of China[2016YFB0200504] ; National Natural Science Foundation of China[61502485]
WOS研究方向	Computer Science
语种	英语
出版者	ELSEVIER SCIENCE BV
WOS记录号	WOS:000401399800005
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/25375]
专题	中国科学院数学与系统科学研究院
通讯作者	Huang, Zhenyu
作者单位	1.Chinese Acad Sci, Inst Informat Engn, SKLOIS, Beijing 100093, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, KLMM, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Huang, Zhenyu,Lin, Dongdai. Solving polynomial systems with noise over F-2: Revisited[J]. THEORETICAL COMPUTER SCIENCE,2017,676:52-68.
APA	Huang, Zhenyu,&Lin, Dongdai.(2017).Solving polynomial systems with noise over F-2: Revisited.THEORETICAL COMPUTER SCIENCE,676,52-68.
MLA	Huang, Zhenyu,et al."Solving polynomial systems with noise over F-2: Revisited".THEORETICAL COMPUTER SCIENCE 676(2017):52-68.