## CryptoDB

### Sihem Mesnager

#### Affiliation: University Paris VIII

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

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. 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
Abstract

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
Abstract

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
Abstract

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.

#### Coauthors

- Claude Carlet (1)
- Pascale Charpin (1)
- Lusheng Chen (1)
- Gérard D. Cohen (1)
- Jean-Pierre Flori (1)
- Nese Koçak (1)
- Jian Liu (1)
- Ferruh Özbudak (1)
- Hugues Randriambololona (1)
- Sumanta Sarkar (1)