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 $\to 2n$ bits from pseudo-random functions of $n$ bits $\to 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 $$ 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 $$, we will prove CPA-2 security when $$. However we will also see that the probability to distinguish Benes functions from random functions is sometime larger than the term in $$ given in~\cite{AV96}. One of the key idea in our proof will be to notice that, when $$ and $$, for large number of variables linked with some critical equalities, the average number of solutions may be large (i.e. $$) while, at the same time, the probability to have at least one such critical equalities is negligible (i.e. $$). \textbf{Key Words}: Pseudo-random functions, unconditional security, information-theoretic primitive, design of keyed hash functions.