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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]