Paper 2010/170
On a conjecture about binary strings distribution
JeanPierre Flori, Hugues Randriambololona, Gérard Cohen, and Sihem Mesnager
Abstract
It is a difficult challenge to find Boolean functions used in stream ciphers achieving all of the necessary criteria and the research of such functions has taken a significant delay with respect to cryptanalyses. A lot of attacks has led to design criteria for these functions; mainly: balancedness, a high algebraic degree, a high nonlinearity, a good behavior against Fast Algebraic Attacks and also a high algebraic immunity (which is now an absolutely necessary criterion (but not sufficient) for cryptographic Boolean functions). Very recently, an infinite class of Boolean functions has been proposed by Tu and Deng having many very nice cryptographic properties under the assumption that the following combinatorial conjecture about binary strings is true: \begin{cjt} \label{cjt:original} Let $\Stk$ be the following set: \[ \Stk=\set{(a,b) \in \left(\Zk\right)^2  a + b = t \text{ and } w(a) + w(b) < k} . \] Then: \[ \abs{\Stk} \leq 2^{k1} . \] \end{cjt} The main contribution of the present paper is the reformulation of the problem in terms of {\em carries} which gives more insight on it than simple counting arguments. Successful applications of our tools include explicit formulas of $\abs{\Stk}$ for numbers whose binary expansion is made of one block (see theorem \ref{thm:one}), a proof that the conjecture is {\em asymptotically} true (see theorem \ref{thm:asymptotic}) and a proof that a family of numbers (whose binary expansion has a high number of \textttup{1}s and isolated \textttup{0}s) reaches the bound of the conjecture (see theorem \ref{thm:extremal}). We also conjecture that the numbers in that family are the only ones reaching the bound (see conjecture \ref{cjt:extremal}).
Note: Corrected authors' affiliations.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 boolean functions combinatorics
 Contact author(s)
 flori @ enst fr
 History
 20100401: last of 3 revisions
 20100330: received
 See all versions
 Short URL
 https://ia.cr/2010/170
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/170, author = {JeanPierre Flori and Hugues Randriambololona and Gérard Cohen and Sihem Mesnager}, title = {On a conjecture about binary strings distribution}, howpublished = {Cryptology ePrint Archive, Paper 2010/170}, year = {2010}, note = {\url{https://eprint.iacr.org/2010/170}}, url = {https://eprint.iacr.org/2010/170} }