Security of balanced and unbalanced Feistel Schemes with Linear Non Equalities.
Jacques Patarin · 2010
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 [14] and by [32] 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 ( 2n 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 [2] submitted to Crypto 2010.