Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Application in Analysis of Stream Ciphers

Xiao-shan Gao; Zhenyu Huang

Paper 2009/637

Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Application in Analysis of Stream Ciphers

Xiao-shan Gao and Zhenyu Huang

Abstract

Efficient characteristic set methods for computing solutions of a polynomial equation system in a finite field are proposed. We introduce the concept of proper triangular sets and prove that proper triangular sets are square-free and have solutions. We present an improved algorithm which can be used to reduce the zero set of an equation system in general form to the union of zero sets of proper triangular sets. Bitsize complexity for the algorithm is given in the case of Boolean polynomials. We also give a characteristic set method for Boolean polynomials, where the size of the polynomials are effectively controlled. The methods are implemented and extensive experiments show that they are quite efficient for solving equations raised in analyzing certain classes of stream ciphers.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: Characteristic set finite field Boolean function stream cipher
Contact author(s): xgao @ mmrc iss ac cn
huangzhenyu @ mmrc iss ac cn
History: 2010-01-06: revised; 2010-01-01: received; See all versions
Short URL: https://ia.cr/2009/637
License: CC BY

BibTeX

@misc{cryptoeprint:2009/637,
      author = {Xiao-shan Gao and Zhenyu Huang},
      title = {Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Application in Analysis of Stream Ciphers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/637},
      year = {2009},
      url = {https://eprint.iacr.org/2009/637}
}