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

Metadata
Available format(s)
PDF
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
Creative Commons Attribution
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.