Cryptology ePrint Archive: Report 2018/478

On Non-Monotonicity of the Success Probability in Linear Cryptanalysis

Ali Aydin Selcuk

Abstract: Like any other cryptanalytic attack, the success rate of a linear attack is expected to improve as more data becomes available. Bogdanov and Tischhauser (FSE 2013) made the rather surprising claim that the success rate of a linear attack may go down with increasing plaintext amount, after an optimal point. They supported this claim with experimental evidence by an attack on SmallPresent-20. Different explanations have been given to explain this surprising phenomenon. In this note, we give quantitative values regarding when this phenomenon can be observed. We conclude that it should not be an issue for attacks in practice except for those with a tiny bias.

Category / Keywords: secret-key cryptography / Linear cryptanalysis, success probability, non-monotonicity.

Date: received 20 May 2018

Contact author: aliaydinselcuk at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180523:024112 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]