Welcome to the resource topic for 2005/004
Title:
Benes and Butterfly schemes revisited
Authors: Jacques Patarin, 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.
ePrint: https://eprint.iacr.org/2005/004
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .