[Resource Topic] 2016/956: Two Simple Composition Theorems with H-coefficients

Welcome to the resource topic for 2016/956

Two Simple Composition Theorems with H-coefficients

Authors: Jacques Patarin


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.

ePrint: https://eprint.iacr.org/2016/956

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 .