Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Characteristic set, finite field, Boolean function, stream cipher

Date: received 30 Dec 2009, last revised 6 Jan 2010

Contact author: xgao at mmrc iss ac cn huangzhenyu@mmrc iss ac cn

Available formats: PDF | BibTeX Citation

Version: 20100106:084752 (All versions of this report)

Discussion forum: Show discussion | Start new discussion