International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Divisibility of the Hamming Weight by $2^k$ and Monomial Criteria for Boolean Functions

Authors:
Dmitry Khovratovich
Download:
URL: http://eprint.iacr.org/2006/180
Search ePrint
Search Google
Abstract: In this paper we consider the notions of the Hamming weight and the algebraic normal form. We solve an open problem devoted to checking divisibility of the weight by $2^k$. We generalize the criterion for checking the evenness of the weight in two ways. Our main result states that for checking whether the Hamming weight of $f$ is divisible by $2^k, \,k>1$, it is necessary and sufficient to know its algebraic normal form accurate to an additive constant.
BibTeX
@misc{eprint-2006-21673,
  title={Divisibility of the Hamming Weight by $2^k$ and Monomial Criteria for Boolean Functions},
  booktitle={IACR Eprint archive},
  keywords={boolean functions, Hamming weight, algebraic normal form, coding theory},
  url={http://eprint.iacr.org/2006/180},
  note={The Russian version was submitted to the workshop on discrete mathematics in Russia in 2006 diho@rnt.ru 13293 received 25 May 2006},
  author={Dmitry Khovratovich},
  year=2006
}