Composition Theorems for CCA Cryptographic Security

Rodolphe Lampe; Jacques Patarin

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 α_{F}$ and $\leq α_{G}$ , we prove that the set of permutations $f \circ g, f \in F, g \in G$ has CCA distinguishability advantage $\leq α_{F} \times α_{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 $4 r$ and $6 r$ 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 with distinghuishability advantage and , we prove that the set of functions has distinguishability advantage . As an example, we apply this new theorem to analyze the XOR of 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 coefficients Security proof Composition XOR of permutations Feistel Schemes Luby-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},
      url = {https://eprint.iacr.org/2012/131}
}