Cryptology ePrint Archive: Report 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

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)

Short URL: ia.cr/2012/131

Discussion forum: Show discussion | Start new discussion