Paper 2012/131

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