Paper 2006/027 Original: eprint.iacr.org/2006/027 ↗
Finding Low Degree Annihilators for a Boolean Function Using Polynomial Algorithms
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$.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2006-01-27: last updated
- 2006-01-27: published
- Short URL
- https://ia.cr/2006/027
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}