You are looking at a specific version 20100106:084752 of this paper. See the latest version.

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 setfinite fieldBoolean functionstream 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.