Paper 2017/391

Another Look at Success Probability in Linear Cryptanalysis

Subhabrata Samajder and Palash Sarkar

Abstract

This work studies the success probability of linear cryptanalysis. Complete expressions for the success probability are obtained using two different approaches, namely the order statistics and the hypothesis testing based approaches. We argue that the hypothesis testing based approach is theoretically more sound and does not require a number of assumptions and approximations which are inherent in the order statistics based approach. For analysing success probability, a unifying framework of general key randomisation hypotheses is introduced. The previously used standard key randomisation hypotheses and the adjusted wrong key randomisation hypothesis can be seen to special cases of the general framework. Derivations of expressions for the success probability are carried out under both the settings of the plaintexts being sampled with and without replacements. Finally, the complete picture of the dependence of the success probability on the data complexity is derived and it is argued that in most practical scenarios, the success probability will be a monotone increasing function of the data complexity. We believe that compared to the extant literature, our work provides a deeper and more thorough understanding of the success probability of linear cryptanalysis.

Note: Corrected a typo in the abstract.