International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Sihem Mesnager

Affiliation: University Paris VIII

Publications

Year
Venue
Title
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2010
EPRINT
On a conjecture about binary strings distribution
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^{k-1} . \] \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}).
2008
EPRINT
A new class of Bent functions in Polynomial Forms
Sihem Mesnager
This paper is a contribution to the construction of bent functions having the form $f(x) = \tr {o(s_1)} (a x^ {s_1}) + \tr {o(s_2)} (b x^{s_2})$ where $o(s_i$) denotes the cardinality of the cyclotomic class of 2 modulo $2^n-1$ which contains $i$ and whose coefficients $a$ and $b$ are, respectively in $F_{2^{o(s_1)}}$ and $F_{2^{o(s_2)}}$. Many constructions of monomial bent functions are presented in the literature but very few are known even in the binomial case. We prove that the exponents $s_1=2^{\frac n2}-1$ and $s_2={\frac {2^n-1}3}$, where $a\in\GF{n}$ and $ b\in\GF[4]{}$ provide the construction of new infinite class of bent functions over $\GF{n}$ with maximum algebraic degree. For $m$ odd, we give an explicit characterization of the bentness of these functions, in terms of the Kloosterman sums of the corresponding coefficients. For $m$ even, we give a necessary condition in terms of these Kloosterman sums.
2007
EPRINT
Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity
Sihem Mesnager
The recent algebraic attacks have received a lot of attention in cryptographic literature. The algebraic immunity of a Boolean function quantifies its resistance to the standard algebraic attacks of the pseudo-random generators using it as a nonlinear filtering or combining function. Very few results have been found concerning its relation with the other cryptographic parameters or with the $r$-th order nonlinearity. As recalled by Carlet at Crypto'06, many papers have illustrated the importance of the $r$th-order nonlinearity profile (which includes the first-order nonlinearity). The role of this parameter relatively to the currently known attacks has been also shown for block ciphers. Recently, two lower bounds involving the algebraic immunity on the $r$th-order nonlinearity have been shown by Carlet et \emph{al}. None of them improves upon the other one in all situations. In this paper, we prove a new lower bound on the $r$th-order nonlinearity profile of Boolean functions, given their algebraic immunity, that improves significantly upon one of these lower bounds for all orders and upon the other one for low orders.
2004
EPRINT
On the supports of the Walsh transforms of Boolean functions
Claude Carlet Sihem Mesnager
In this paper, we study, in relationship with covering sequences, the structure of those subsets of $\V {n}$ which can be the Walsh supports of Boolean functions.