Paper 2017/391

Another Look at Success Probability in Linear Cryptanalysis

Subhabrata Samajder and Palash Sarkar

Abstract

This work studies the success probability of key recovery attacks based on using a single linear approximation. Previous works had analysed success probability under different hypotheses on the distributions of correlations for the right and wrong key choices. This work puts forward a unifying framework of general key randomisation hypotheses. All previously used key randomisation hypotheses as also zero correlation attacks 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. Compared to previous analysis, we uncover several new cases which have not been considered in the literature. For most of the cases which have been considered earlier, we provide complete expressions for the respective success probabilities. Finally, the complete picture of the dependence of the success probability on the data complexity is revealed. Compared to the extant literature, our work provides a deeper and more thorough understanding of the success probability of single linear cryptanalysis.

Note: Corrected a typo in the abstract.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
linear cryptanalysissuccess probabilitydata complexity.
Contact author(s)
subhabrata samajder @ gmail com
palash @ isical ac in
History
2017-12-09: last of 5 revisions
2017-05-05: received
See all versions
Short URL
https://ia.cr/2017/391
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/391,
      author = {Subhabrata Samajder and Palash Sarkar},
      title = {Another Look at Success Probability in Linear Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2017/391},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/391}},
      url = {https://eprint.iacr.org/2017/391}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.