Strict Evaluation of the Maximum Average of Differential Probability and the Maximum Average of Linear Probability

Kazumaro AOKI, Kazuo OHTA

Summary :

Nyberg and Knudsen proved that the maximum average of differential probability (ADP_max) and the maximum average of linear probability (ALP_max) of Feistel cipher with over 4 rounds can be evaluated as ADP_max 2DCP²_max and ALP_max 2LCP²_max using the maximum of defferential characteristic probability (DCP_max) and the maximum of linear characteristic probability (LCP_max) per round. This paper shows ADP_max DCP²_max and ALP_max LCP²_max if the F function is a bijection and the Feistel cipher has more than 3 rounds. The results prove that Feistel ciphers are stronger against differential and linear cryptanalyses than previously thought. Combining this result with that of Luby and Rackoff, the implication is that the 3-round Feistel cipher could be used as a building block cipher for the construction of provable secure block cipher algorithm.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.1 pp.2-8
• Publication Date: 1997/01/25
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Authors

Kazumaro AOKI
Kazuo OHTA

Keyword

Feistel cipher,  differential cryptanalysis,  linear cryptanalysis,  differential probability,  potential of linear approximate hull