Paper 2016/465

Can Large Deviation Theory be Used for Estimating Data Complexity?

Subhabrata Samajder and Palash Sarkar

Abstract

Statistical analysis of attacks on block ciphers have mostly used normal approximations. A few recent works have proposed doing away with normal approximations and instead use Chernoff and Hoeffding bounds to obtain rigorous bounds on data complexities of several attacks. This opens up the question of whether even better general bounds can be obtained using the statistical theory of large deviations. In this note we examine this question. Our conclusion is that while in theory this is indeed possible, in general obtaining meaningful expressions for data complexity presents several difficulties. This leaves open the question of whether this can be done for specific attacks.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
block cipherscryptanalysisdata complexity
Contact author(s)
palash @ isical ac in
History
2016-05-24: revised
2016-05-13: received
See all versions
Short URL
https://ia.cr/2016/465
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/465,
      author = {Subhabrata Samajder and Palash Sarkar},
      title = {Can Large Deviation Theory be Used for Estimating Data Complexity?},
      howpublished = {Cryptology ePrint Archive, Paper 2016/465},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/465}},
      url = {https://eprint.iacr.org/2016/465}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.