Cryptology ePrint Archive: Report 2014/962

Solving Polynomial Systems with Noise over F_2: Revisited

Zhenyu Huang and Dongdai Lin

Abstract: Solving polynomial systems with noise over F_2 is a funda- mental problem in computer science, especially in cryptanalysis. ISBS is a new method for solving this problem based on the idea of incremen- tally solving the noisy polynomial systems and backtracking all the pos- sible noises. It had better performance than other methods in solving the Cold Boot Key recovery problem. In this paper, some further researches on ISBS are presented. We proposed a polynomial ordering scheme by which we can accelerate the incremental solving process of ISBS. We present some computation complexity bounds of ISBS. Two major im- provement strategies, artificial noise-bound strategy and two-direction searching strategy, are proposed and theoretically analyzed. Based on these improvements, we propose a variant ISBS algorithm, and by the experiments of solving the Cold Boot key recovery problem of Serpent with symmetric noise, we show that our new algorithm is more efficient than the old one.

Category / Keywords: foundations / Boolean polynomial system with noise, Max-PoSSo, ISBS method, Cold Boot attack, Characteristic Set method, Serpent

Date: received 24 Nov 2014

Contact author: huangzhenyu at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20141125:204450 (All versions of this report)

Short URL: ia.cr/2014/962

Discussion forum: Show discussion | Start new discussion