Cryptology ePrint Archive: Report 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.
Category / Keywords: secret-key cryptography / block ciphers, cryptanalysis, data complexity
Date: received 13 May 2016, last revised 24 May 2016
Contact author: palash at isical ac in
Available format(s): PDF | BibTeX Citation
Version: 20160524:163505 (All versions of this report)
Short URL: ia.cr/2016/465
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]