Alekseychuk A.N.
Non-asymptotic lower bounds for the data complexity of statistical attacks on symmetric cryptosystems

A method is proposed for obtaining the lower bounds of data complexity of statistical attacks on block or stream ciphers. The method is based on the Fano inequality and, unlike the available methods, doesn’t use any asymptotic relations, approximate formulas or heuristic assumptions about the considered cipher. For a lot of known types of attacks, the obtained data complexity bounds have the classical form. For other types of attacks, these bounds allow us to introduce reasonable parameters that characterize the security of symmetric cryptosystems against these attacks. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: block cipher, correlation attack, data complexity, Fano’s inequality, statistical attack, statistical hypotheses testing, stream cipher, symmetric cryptography, Approximation algorithms, Heuristic methods, Block ciphers, Correlation attack, Data complexity, Statistical attacks, Statistical hypotheses testing, Stream Ciphers, Symmetric cryptography, Cryptography

Cite:
Alekseychuk A.N. (2018). Non-asymptotic lower bounds for the data complexity of statistical attacks on symmetric cryptosystems. Cybernetics and Systems Analysis, 54 (1), 93-104. doi: https://doi.org/10.1007/s10559-018-0009-0 http://jnas.nbuv.gov.ua/article/UJRN-0000805860 [In Russian].