Publication Details
Evolving Boolean Functions for Fast and Efficient Randomness Testing
Sýs Marek (VUT)
Vašíček Zdeněk, doc. Ing., Ph.D. (DCSY)
Sekanina Lukáš, prof. Ing., Ph.D. (DCSY)
Matyáš Václav, Dr. (CM-SFE)
Boolean function, genetic algorithm, statistical randomness testing
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.
@inproceedings{BUT155018,
author="Vojtěch {Mrázek} and Marek {Sýs} and Zdeněk {Vašíček} and Lukáš {Sekanina} and Václav {Matyáš}",
title="Evolving Boolean Functions for Fast and Efficient Randomness Testing",
booktitle="Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18)",
year="2018",
pages="1302--1309",
publisher="Association for Computing Machinery",
address="Kyoto",
doi="10.1145/3205455.3205518",
isbn="978-1-4503-5618-3",
url="https://www.fit.vut.cz/research/publication/11686/"
}