Evolving boolean functions for fast and efficient randomness testing

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

MRÁZEK Vojtěch SÝS Marek VASICEK Zdenek SEKANINA Lukáš MATYÁŠ Václav

Year of publication 2018
Type Article in Proceedings
Conference Proceedings of the Genetic and Evolutionary Computation Conference 2018
MU Faculty or unit

Faculty of Informatics

Citation
Web https://dl.acm.org/citation.cfm?id=3205518
Doi http://dx.doi.org/10.1145/3205455.3205518
Keywords Boolean function; evolutionary computing; randomness; statistical test
Description The security of cryptographic algorithms (such as block ciphers and hash functions) is often evaluated in terms of their output randomness. This paper presents a novel method for the statistical randomness testing of cryptographic primitives, which is based on the evolutionary construction of the so-called randomness distinguisher. Each distinguisher is represented as a Boolean polynomial in the algebraic normal form. The previous approach, in which the distinguishers were developed in two phases by means of the brute-force method, is replaced with a more scalable evolutionary algorithm (EA). On seven complex datasets, this EA provided distinguishers of the same quality as the previous approach, but the execution time was in practice reduced 40 times. This approach allowed us to perform a more efficient search in the space of Boolean distinguishers and to obtain more complex high-quality distinguishers than the previous approach.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.