### Tight Security for Key-Alternating Ciphers with Correlated Sub-Keys

Stefano Tessaro and Xihu Zhang

##### Abstract

A substantial effort has been devoted to proving optimal bounds for the security of key-alternating ciphers with independent sub-keys in the random permutation model (e.g., Chen and Steinberger, EUROCRYPT '14; Hoang and Tessaro, CRYPTO '16). While common in the study of multi-round constructions, the assumption that sub-keys are truly independent is not realistic, as these are generally highly correlated and generated from shorter keys. In this paper, we show the existence of non-trivial distributions of limited independence for which a t-round key-alternating cipher achieves optimal security. Our work is a natural continuation of the work of Chen et al. (CRYPTO '14) which considered the case of t = 2 when all-subkeys are identical. Here, we show that key-alternating ciphers remain secure for a large class of (t-1)-wise and (t-2)-wise independent distribution of sub-keys. Our proofs proceed by generalizations of the so-called Sum-Capture Theorem, which we prove using Fourier-analytic techniques.

Available format(s)
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2021
DOI
10.1007/978-3-030-92078-4_15
Keywords
Provable SecurityKey-alternating Ciphers
Contact author(s)
xihu @ cs washington edu
History
2021-12-10: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/1571

CC BY

BibTeX

@misc{cryptoeprint:2021/1571,
author = {Stefano Tessaro and Xihu Zhang},
title = {Tight Security for Key-Alternating Ciphers with Correlated Sub-Keys},
howpublished = {Cryptology ePrint Archive, Paper 2021/1571},
year = {2021},
doi = {10.1007/978-3-030-92078-4_15},
note = {\url{https://eprint.iacr.org/2021/1571}},
url = {https://eprint.iacr.org/2021/1571}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.