Paper 2005/004

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.