**Security of balanced and unbalanced Feistel Schemes with Linear Non Equalities**

*Jacques Patarin*

**Abstract: **\begin{abstract}
In this paper we will study 2 security results ``above the birthday bound'' related to secret key cryptographic problems.\\
1. The classical problem of the security of 4, 5, 6 rounds balanced Random Feistel Schemes.\\
2. The problem of the security of unbalanced Feistel Schemes with contracting functions from $2n$ bits to $n$ bits. This problem was studied by Naor and Reingold~\cite{NR99} and by~\cite{YPL} with a proof of security up to the birthday bound.\\
These two problems are included here in the same paper since their analysis is closely related, as we will see. In problem 1 we will obtain security result very near the information bound (in $O(\frac {2^n}{n})$) with improved proofs and stronger explicit security bounds than previously known. In problem 2 we will cross the birthday bound of Naor and Reingold. For some of our proofs we will use~\cite{A2} submitted to Crypto 2010.
\end{abstract}

**Category / Keywords: **secret-key cryptography / Luby-Rackoff constructions, Balanced random Feistel schemes, Unbalanced random Feistel schemes, Security Proofs, linear equalities and linear non equalities.

**Date: **received 17 May 2010

**Contact author: **valerie nachef at u-cergy fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20100518:040821 (All versions of this report)

**Short URL: **ia.cr/2010/293

[ Cryptology ePrint archive ]