**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 at mmrc iss ac cn

**Available format(s): **PDF | BibTeX Citation

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

**Short URL: **ia.cr/2009/637

[ Cryptology ePrint archive ]