**Composition Theorems for CCA Cryptographic Security**

*Rodolphe Lampe and Jacques Patarin*

**Abstract: **We present two new theorems to analyze the indistinguishability of the composition of cryptographic permutations and the indistinguishability of the XOR of cryptographic functions. Using the H Coefficients technique of \cite{Patarin-2001}, for any two families of permutations $F$ and $G$ with CCA distinghuishability advantage $\leq\alpha_F$ and $\leq\alpha_G$, we prove that the set of permutations $f\circ g, f\in F, g\in G$ has CCA distinguishability advantage $\leq\alpha_F\times\alpha_G$. This simple composition result gives a CCA indistinguishability geometric gain when composing blockciphers (unlike previously known clasical composition theorems). As an example, we apply this new theorem to analyze $4r$ and $6r$ rounds Feistel schemes with $r\geq 1$ and we improve previous best known bounds for a certain range of queries. Similarly, for any two families of functions $F$ and $G$ with distinghuishability advantage $\leq\alpha_F$ and $\leq\alpha_G$, we prove that the set of functions $f\oplus g, f\in F, g\in G$ has distinguishability advantage $\leq\alpha_F\times\alpha_G$. As an example, we apply this new theorem to analyze the XOR of $2r$ permutations and we improve the previous best known bounds for certain range of queries

**Category / Keywords: **H coefficients, Security proof, Composition, XOR of permutations, Feistel Schemes, Luby-Rackoff construction

**Date: **received 8 Mar 2012, last revised 4 Jun 2013

**Contact author: **rodolphe lampe at gmail com

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

**Version: **20130604:202946 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]