Paper 2006/027
Finding Low Degree Annihilators for a Boolean Function Using Polynomial Algorithms
Vladimir Bayev
Abstract
Low degree annihilators for Boolean functions are
of great interest in cryptology because of algebraic attacks on
LFSR-based stream ciphers. Several polynomial algorithms for
construction of low degree annihilators are introduced in this
paper. The existence of such algorithms is studied for the
following forms of the function representation: algebraic normal
form (ANF), disjunctive normal form (DNF), conjunctive normal form
(CNF), and arbitrary formula with the Boolean operations of
negation, conjunction, and disjunction. For ANF and DNF of a
Boolean function
Metadata
- Available format(s)
-
PDF PS
- Category
- Foundations
- Publication info
- Published elsewhere. English version of the paper from Mathematics and Security of Information Technologies 2005
- Keywords
- Boolean functionlow degree annihilatorpolynomial algorithmrecursive algorithm.
- Contact author(s)
- vbayev @ yandex ru
- History
- 2006-01-27: received
- Short URL
- https://ia.cr/2006/027
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/027, author = {Vladimir Bayev}, title = {Finding Low Degree Annihilators for a Boolean Function Using Polynomial Algorithms}, howpublished = {Cryptology {ePrint} Archive, Paper 2006/027}, year = {2006}, url = {https://eprint.iacr.org/2006/027} }