Paper 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 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 the 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 block cipher Serpent with symmetric noise, show that this modified algorithm is more efficient than the original one.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
Boolean polynomial system with noiseMax-PoSSoISBS methodCold Boot attackSerpent
Contact author(s)
huangzhenyu @ iie ac cn
History
2016-10-21: last of 2 revisions
2014-11-25: received
See all versions
Short URL
https://ia.cr/2014/962
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/962,
      author = {Zhenyu Huang and Dongdai Lin},
      title = {Solving Polynomial Systems with Noise over F_2: Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2014/962},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/962}},
      url = {https://eprint.iacr.org/2014/962}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.