Cryptology ePrint Archive: Report 2021/1571

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.

Category / Keywords: secret-key cryptography / Provable Security, Key-alternating Ciphers

Original Publication (with major differences): IACR-ASIACRYPT-2021

Date: received 30 Nov 2021, last revised 10 Dec 2021

Contact author: xihu at cs washington edu

Available format(s): PDF | BibTeX Citation

Version: 20211210:142557 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]