Paper 2017/729

Success Probability of Multiple/Multidimensional Linear Cryptanalysis Under General Key Randomisation Hypotheses

Subhabrata Samajder and Palash Sarkar

Abstract

This work considers statistical analysis of attacks on block ciphers using several linear approximations. A general and unified approach is adopted. To this end, the general key randomisation hypotheses for multidimensional and multiple linear cryptanalysis are introduced. Expressions for the success probability in terms of the data complexity and the advantage are obtained using the general key randomisation hypotheses for both multidimensional and multiple linear cryptanalysis and under the settings where the plaintexts are sampled with or without replacement. Particularising to standard/adjusted key randomisation hypotheses gives rise to success probabilities in 16 different cases out of which in only five cases expressions for success probabilities have been previously reported. Even in these five cases, the expressions for success probabilities that we obtain are more general than what was previously obtained. A crucial step in the analysis is the derivation of the distributions of the underlying test statistics. While we carry out the analysis formally to the extent possible, there are certain inherently heuristic assumptions that need to be made. In contrast to previous works which have implicitly made such assumptions, we carefully highlight these and discuss why they are unavoidable. Finally, we provide a complete characterisation of the dependence of the success probability on the data complexity.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
multidimensional linear cryptanalysismultiple linear cryptanalysischi-squared distributionsuccess probabilitydata complexityadvantage
Contact author(s)
subhabrata samajder @ gmail com
palash @ isical ac in
History
2017-07-31: received
Short URL
https://ia.cr/2017/729
License
Creative Commons Attribution
CC BY

BibTeX

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