International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Perfectly Balanced Boolean Functions and Golić Conjecture

Authors:
Stanislav V. Smyshlyaev
Download:
DOI: 10.1007/s00145-011-9100-7
Search ePrint
Search Google
Abstract: In the current paper we consider the following properties of filters: perfect balancedness of a filter function (i.e. preserving pure randomness of the input sequence) and linearity of a filter function in the first or the last essential variable. Previous results on this subject are discussed, including misleading statements in Gouget and Sibert (LNCS, vol. 4876, 2007) about the connection between perfect balancedness and resistance to Anderson conditional correlation attack; the incorrectness of two known results, the sufficient condition of perfect balancedness in Golić (LNCS, vol. 1039, 1996) and the necessary condition of perfect balancedness in Dichtl (LNCS, vol. 1267, 1997), is demonstrated by providing counterexamples.We present a novel method of constructing large classes of perfectly balanced functions that are nonlinear in the first and the last essential variable and obtain a new lower bound of the number of such functions.Golić conjecture (LNCS, vol. 1039, 1996) states that the necessary and sufficient condition for a function to be perfectly balanced for any choice of a tapping sequence is linearity of a function in the first or the last essential variable. In the second part of the current paper we prove the Golić conjecture.
BibTeX
@article{jofc-2012-29490,
  title={Perfectly Balanced Boolean Functions and Golić Conjecture},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={25},
  pages={464-483},
  doi={10.1007/s00145-011-9100-7},
  author={Stanislav V. Smyshlyaev},
  year=2012
}