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 pseudorandom functions of $2n$ bits $\rightarrow 2n$ bits from pseudorandom 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 (CPA2). 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 CPA2 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}: Pseudorandom functions, unconditional security, informationtheoretic primitive, design of keyed hash functions.
Metadata
 Available format(s)
 PDF PS
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)
 audrey_montreuil @ hotmail com
 History
 20050108: received
 Short URL
 https://ia.cr/2005/004
 License

CC BY
BibTeX
@misc{cryptoeprint:2005/004, author = {Jacques Patarin and Audrey Montreuil}, title = {Benes and Butterfly schemes revisited}, howpublished = {Cryptology {ePrint} Archive, Paper 2005/004}, year = {2005}, url = {https://eprint.iacr.org/2005/004} }