Feistel networks made public, and applications

Yevgeniy Dodis, Prashant Puniya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Feistel Network, consisting of a repeated application of the Feistel Transform, gives a very convenient and popular method for designing "cryptographically strong" permutations from corresponding "cryptographically strong" functions. Up to now, all usages of the Feistel Network, including the celebrated Luby-Rackoff's result, critically rely on (a) the (pseudo)randomness of round functions; and (b) the secrecy of (at least some of) the intermediate round values appearing during the Feistel computation. Moreover, a small constant number of Feistel rounds was typically sufficient to guarantee security under assumptions (a) and (b). In this work we consider several natural scenarios where at least one of the above assumptions does not hold, and show that a constant, or even logarithmic number of rounds is provably insufficient to handle such applications, implying that a new method of analysis is needed. On a positive side, we develop a new combinatorial understanding of Feistel networks, which makes them applicable to situations when the round functions are merely unpredictable rather than (pseudo)random and/or when the intermediate round values may be leaked to the adversary (either through an attack or because the application requires it). In essence, our results show that in any such scenario a super-logarithmic number of Feistel rounds is necessary and sufficient to guarantee security. Of independent interest, our technique yields a novel domain extension method for messages authentication codes and other related primitives, settling a question studied by An and Bellare in CRYPTO 1999.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2007 - 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
PublisherSpringer Verlag
Pages534-554
Number of pages21
ISBN (Print)9783540725398
DOIs
StatePublished - 2007
Event26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2007 - Barcelona, Spain
Duration: May 20 2007May 24 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4515 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2007
CountrySpain
CityBarcelona
Period5/20/075/24/07

Keywords

  • Domain extension
  • Feistel network
  • MACs
  • PRFs
  • PRPs
  • Verifiable random functions/permutations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Feistel networks made public, and applications'. Together they form a unique fingerprint.

Cite this