Solving polynomial systems with noise over F-2: Revisited

doi:10.1016/j.tcs.2017.03.005

CSpace

	Solving polynomial systems with noise over F-2: Revisited
	Huang, Zhenyu 1,2; Lin, Dongdai 1
	2017-05-09
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	676 页码:52-68
摘要	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.
关键词	Boolean polynomial system with noise Max-PoSSo ISBS method Cold Boot attack Serpent
DOI	10.1016/j.tcs.2017.03.005
语种	英语
资助项目	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
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000401399800005
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/25376
专题	中国科学院数学与系统科学研究院
通讯作者	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.