Welcome to the resource topic for 2006/027
Title:
Finding Low Degree Annihilators for a Boolean Function Using Polynomial Algorithms
Authors: 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 f there exist polynomial algorithms that find
the vector space A_d (f) of all annihilators of degree
\leqslant d. For CNF this problem is NP-hard. Nevertheless author
introduces one polynomial algorithm that constructs some subspace
of A_d (f) having formula that represents f.
ePrint: https://eprint.iacr.org/2006/027
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .