Tweaking Key-Alternating Feistel Block Ciphers

Tweakable block cipher as a cryptographic primitive has found wide applications in disk encryption, authenticated encryption mode and message authentication code, etc. One popular approach of designing tweakable block ciphers is to tweak the generic constructions of classic block ciphers. This paper focuses on how to build a secure tweakable block cipher from the Key-Alternating Feistel (KAF) structure, a dedicated Feistel structure with round functions of the form 𝐹𝑖(𝑘𝑖⊕𝑥𝑖) , where 𝑘𝑖 is the secret round key and 𝐹𝑖 is a public random function in the i-th round. We start from the simplest KAF structures that have been published so far, and then incorporate the tweaks to the round key XOR operations by (almost) universal hash functions. Moreover, we limit the number of rounds with the tweak injections for the efficiency concerns of changing the tweak value. Our results are two-fold, depending on the provable security bound: For the birthday-bound security, we present a 4-round minimal construction with two independent round keys, a single round function and two universal hash functions; For the beyond-birthday-bound security, we present a 10-round construction secure up to 𝑂(min{22𝑛/3,22𝑛𝜖−1‾‾‾‾‾‾√4}) adversarial queries, where n is the output size of the round function and 𝜖 is the upper bound of the collision probability of the universal hash functions. Our security proofs exploit the hybrid argument combined with the H-coefficient technique.