Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user Security

Guo, Chun;Wang, Lei
(2018) 24th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2018) — Location: Brisbane, QLD (Australia) (2.December.2018)

Files

RevisitingKey-AlternatingFeistelCiphersforShorterKeysandMulti-userSecurity.pdf
  • Open Access
  • Adobe PDF
  • 733.03 KB
Download

Details

Authors
  • Guo, ChunUCLouvain
    Author
  • Wang, LeiShanghai Jiao Tong University, Shanghai, China - Westone Cryptologic Research Center, Beijing, China
    Author
Abstract
Key-Alternating Feistel (KAF) ciphers, a.k.a. Feistel-2 models, refer to Feistel networks with round functions of the form Fi(ki⊕xi), where ki is the (secret) round-key and Fi is a public random function. This model roughly captures the structures of many famous Feistel ciphers, and the most prominent instance is DES. Existing provable security results on KAF assumed independent round-keys and round functions (ASIACRYPT 2004 & FSE 2014). In this paper, we investigate how to achieve security under simpler and more realistic assumptions: with round-keys derived from a short mainkey, and hopefully with identical round functions. For birthday-type security, we consider 4-round KAF, investigate the minimal conditions on the way to derive the four round-keys, and prove that when such adequately derived keys and the same round function are used, the 4-round KAF is secure up to 2n/2 queries. For beyond-birthday security, we focus on 6-round KAF. We prove that when the adjacent round-keys are independent, and independent round-functions are used, the 6 round KAF is secure up to 22n/3 queries. To our knowledge, this is the first beyond-birthday security result for KAF without assuming completely independent round-keys. Our results hold in the multi-user setting as well, constituting the first non-trivial multi-user provable security results on Feistel ciphers. We finally demonstrate applications of our results on designing key-schedules and instantiating keyed sponge constructions.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Guo, C., & Wang, L. (2018). Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user Security. Lecture Notes in Computer Science, 11272(816), 213-243. https://doi.org/10.1007/978-3-030-03326-2_8 (Original work published 2018)