## CryptoDB

### Audrey Montreuil

#### Affiliation: University of Versailles

#### Publications

**Year**

**Venue**

**Title**

2005

EPRINT

Benes and Butterfly schemes revisited
Abstract

In~\cite{AV96}, W. Aiello and R. Venkatesan have shown how to
construct pseudo-random functions of $2n$ bits $\rightarrow 2n$
bits from pseudo-random functions of $n$ bits $\rightarrow n$
bits. They claimed that their construction, called ``Benes'',
reaches the optimal bound ($m\ll 2^n$) of security against
adversaries with unlimited computing power but limited by $m$
queries in an adaptive chosen plaintext attack (CPA-2). However a
complete proof of this result is not given in~\cite{AV96} since
one of the assertions of~\cite{AV96} is wrong. Due to this, the
proof given in~\cite{AV96} is valid for most attacks, but not for
all the possible chosen plaintext attacks. In this paper we will
in a way fix this problem since for all $\varepsilon>0$, we will
prove CPA-2 security when $m\ll 2^{n(1-\varepsilon)}$. However we
will also see that the probability to distinguish Benes functions
from random functions is sometime larger than the term in
$\frac{m^2}{2^{2n}}$ given in~\cite{AV96}. One of the key idea in
our proof will be to notice that, when $m\gg2^{2n/3}$ and
$m\ll2^n$, for large number of variables linked with some critical
equalities, the average number of solutions may be large (i.e.
$\gg1$) while, at the same time, the probability to have at least
one such critical equalities is negligible (i.e. $\ll1$).\\
\textbf{Key Words}: Pseudo-random functions, unconditional
security, information-theoretic primitive, design of keyed hash
functions.

#### Coauthors

- Jacques Patarin (1)