### 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

##### Metadata
Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
H coefficientsSecurity proofCompositionXOR of permutationsFeistel SchemesLuby-Rackoff construction
Contact author(s)
rodolphe lampe @ gmail com
History
2013-06-04: last of 5 revisions
2012-03-21: received
See all versions
Short URL
https://ia.cr/2012/131
License

CC BY

BibTeX

@misc{cryptoeprint:2012/131,
author = {Rodolphe Lampe and Jacques Patarin},
title = {Composition Theorems for CCA Cryptographic Security},
howpublished = {Cryptology ePrint Archive, Paper 2012/131},
year = {2012},
note = {\url{https://eprint.iacr.org/2012/131}},
url = {https://eprint.iacr.org/2012/131}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.