Cryptology ePrint Archive: Report 2012/131

Security of Feistel Schemes with New and Various Tools

Rodolphe LAMPE and Jacques PATARIN

Abstract: We combine the H Coefficients technique and the Coupling technique to improve security bounds of balanced Feistel schemes. For q queries and round functions of n bits to n bits, we find that the CCA Security of 4 + 2r rounds Feistel schemes is upperbounded by 2q/(r+3) * (4q/2^n)^((r+1)/2) + q(q-1)/2^(2n+1). This divides by roughly 1.5 the number of needed rounds for a given CCA Security, compared to the previous results of Hoang and Rogaway [HR10] who found an advantage of 2q/(r+1) * (4q/2^n)^r for 6r-1 rounds Feistel schemes . Independently of this result, we found a new composition theorem in the H Coefficients technique, allowing the existing bounds for a small fixed number of rounds to be extended to arbitrary multiples of this round number. With this new theorem, we compose 6 rounds Feistel schemes to upperbound the CCA security of 6r rounds Feistel schemes by: (8q/2^n)^r + q(q-1)/2^(2n+1) when q<2^n/(67n), improving very significantly the previous bound for this range of queries.

Category / Keywords: Feistel schemes, Coupling, H coefficients, Security proof, Luby-Rackoff construction

Date: received 8 Mar 2012, last revised 30 Aug 2012

Contact author: rodolphe lampe at gmail com

Available formats: PDF | BibTeX Citation

Version: 20120830:074533 (All versions of this report)

Discussion forum: Show discussion | Start new discussion