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 format(s): PDF | BibTeX Citation
Version: 20100106:084752 (All versions of this report)
Short URL: ia.cr/2009/637
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]