The proofs and security of block ciphers constructed especially of Luby Rackoff
ID: 648679 • Letter: T
Question
The proofs and security of block ciphers constructed especially of Luby Rackoff Constructions and Feistel Networks is based on the number of queries and round functions. The security measure is always based on the probability with which the attacker can distinguish the randomness in the cipher text. For example Patarin's proof says the encryption can be distinguished in O(m2/2l/2)) where m is number of queries and l is length of input bits.
But in general the bigger the key length it is considered as good against brute force and adding tweaks is considered provides additional randomness. Then why is the security measure not involving the key length or tweak length ? or is there a security measure that involves key and tweak ?
Explanation / Answer
Generally speaking, in proofs of security for Feistel ciphers with various numbers of randomly selected round functions, the secret 'key' is the set of round functions. Thus, when Patarin or whoever gives upper bounds on the Adversarial advantage for distinguishing a Feistel cipher with k rounds from a random permutation, the key 'length' (i.e. the size of the key space) is implicit in k, the number of rounds. Keep in mind that many of the bounds (e.g. of Patarin) are information theoretic, so brute force isn't really an option -- that is, even someone with an infinitely powerful computer would not be able to distinguish the Feistel cipher from a random permutation better than the relevant bound.
Tweaks are not commonly included mostly because tweakable block ciphers are a recent innovation.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.