On a Conjecture about Binary Strings Distribution

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. Very recently, an infinite class of Boolean functions has been proposed by Tu and Deng having many good cryptographic properties under the assumption that the following combinatorial conjecture about binary strings is true: Conjecture 0.1. Let S t , k be the following set: $$ S_t,k= \left\(a,b) \in \left( \mathbb Z / (2^k-1) \mathbb Z \right)^2 | a + b = t ~\rm and ~ w(a) + w(b) Then: $$ |S_t,k| \leq 2^k-1. $$ The main contribution of the present paper is the reformulation of the problem in terms of carries which gives more insight on it than simple counting arguments. Successful applications of our tools include explicit formulas of for numbers whose binary expansion is made of one block, a proof that the conjecture is asymptotically true and a proof that a family of numbers (whose binary expansion has a high number of 1 s and isolated 0 s) reaches the bound of the conjecture. We also conjecture that the numbers in that family are the only ones reaching the bound.
Type de document :
Chapitre d'ouvrage
Carlet, Claude and Pott, Alexander. Sequences and Their Applications - SETA 2010, 6338, Springer Berlin / Heidelberg, pp.346-358, 2010, 978-3-642-15873-5. 〈10.1007/978-3-642-15874-2_30〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00642283
Contributeur : Jean-Pierre Flori <>
Soumis le : jeudi 17 novembre 2011 - 17:06:19
Dernière modification le : mardi 22 mai 2018 - 20:40:03

Lien texte intégral

Identifiants

Citation

Jean-Pierre Flori, Hugues Randriam, Gérard Cohen, Sihem Mesnager. On a Conjecture about Binary Strings Distribution. Carlet, Claude and Pott, Alexander. Sequences and Their Applications - SETA 2010, 6338, Springer Berlin / Heidelberg, pp.346-358, 2010, 978-3-642-15873-5. 〈10.1007/978-3-642-15874-2_30〉. 〈hal-00642283〉

Partager

Métriques

Consultations de la notice

322