Paper 2016/956

Two Simple Composition Theorems with H-coefficients

Jacques Patarin

Abstract

We will present here two new and simple theorems that show that when we compose permutation generators with independent keys, then the ``quality'' of CCA security increases. These theorems (Theorems 2 and 5 of this paper) are written in terms of H-coefficients (which are nothing else, up to some normalization factors, than transition probabilities). Then we will use these theorems on the classical analysis of Random Feistel Schemes (i.e. Luby-Rackoff constructions) and we will compare the results obtained with the bounds obtained with the coupling technique. Finally, we will show an interesting difference between 5 and 6 Random Feistel Schemes. With 5 rounds on $2n$ bits $\rightarrow 2n$ bits, when the number of $q$ queries satisfies $\sqrt{2^n} \ll q \ll 2^n$, we have some ``holes'' in the H-coefficient values, i.e. some H values are much smaller than the average value of H. This property for 5 rounds does not exist anymore on 6 rounds.

Note: The proof of theorem 2 has been improved.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
security
Contact author(s)
valerie nachef @ u-cergy fr
History
2018-01-05: last of 2 revisions
2016-10-04: received
See all versions
Short URL
https://ia.cr/2016/956
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/956,
      author = {Jacques Patarin},
      title = {Two Simple Composition Theorems with H-coefficients},
      howpublished = {Cryptology ePrint Archive, Paper 2016/956},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/956}},
      url = {https://eprint.iacr.org/2016/956}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.