**Benes and Butterfly schemes revisited**

*Jacques Patarin and Audrey Montreuil*

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

**Category / Keywords: **

**Date: **received 7 Jan 2005

**Contact author: **audrey_montreuil at hotmail com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20050108:013523 (All versions of this report)

**Short URL: **ia.cr/2005/004

[ Cryptology ePrint archive ]