TY - GEN
T1 - Feistel networks made public, and applications
AU - Dodis, Yevgeniy
AU - Puniya, Prashant
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Domain extension
KW - Feistel network
KW - MACs
KW - PRFs
KW - PRPs
KW - Verifiable random functions/permutations
UR - http://www.scopus.com/inward/record.url?scp=38049138727&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38049138727&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72540-4_31
DO - 10.1007/978-3-540-72540-4_31
M3 - Conference contribution
AN - SCOPUS:38049138727
SN - 9783540725398
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 534
EP - 554
BT - Advances in Cryptology - EUROCRYPT 2007 - 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
PB - Springer Verlag
T2 - 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2007
Y2 - 20 May 2007 through 24 May 2007
ER -