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

Kazumaro AOKI  Kazuo OHTA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.1   pp.2-8
Publication Date: 1997/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
Feistel cipher,  differential cryptanalysis,  linear cryptanalysis,  differential probability,  potential of linear approximate hull,  

Full Text: PDF(404.6KB)>>
Buy this Article




Summary: 
Nyberg and Knudsen proved that the maximum average of differential probability (ADPmax) and the maximum average of linear probability (ALPmax) of Feistel cipher with over 4 rounds can be evaluated as ADPmax 2DCP2max and ALPmax 2LCP2max using the maximum of defferential characteristic probability (DCPmax) and the maximum of linear characteristic probability (LCPmax) per round. This paper shows ADPmax DCP2max and ALPmax LCP2max 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.