**Two Simple Composition Theorems with H-coefficients**

*Jacques Patarin*

**Abstract: **We will present here two new and simple theorems that show that when we compose permutation generators with
independent keys, then the ``quality'' of CCA security increases. These theorems (Theorems 2 and
5 of this paper) are written in terms of
H-coefficients (which are nothing else, up to some normalization factors, than transition probabilities). Then we will use these theorems on the classical analysis of Random Feistel Schemes (i.e.
Luby-Rackoff constructions) and we will compare the results obtained with the bounds obtained with the
coupling technique. Finally, we will show an interesting difference between 5 and 6 Random Feistel Schemes.
With 5 rounds on $2n$ bits $\rightarrow 2n$ bits, when the number of $q$ queries satisfies $\sqrt{2^n}
\ll q \ll 2^n$, we have some ``holes'' in the H-coefficient values, i.e. some H values are much smaller than
the average value of H. This property for 5 rounds does not exist anymore on 6 rounds.

**Category / Keywords: **secret-key cryptography / security

**Date: **received 3 Oct 2016, last revised 5 Jan 2018

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

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

**Note: **The proof of theorem 2 has been improved.

**Version: **20180105:145637 (All versions of this report)

**Short URL: **ia.cr/2016/956

[ Cryptology ePrint archive ]