Faculty of Information Technology, BUT

Publication Details

Evolving Boolean Functions for Fast and Efficient Randomness Testing

MRÁZEK Vojtěch, SÝS Marek, VAŠÍČEK Zdeněk, SEKANINA Lukáš and MATYÁŠ Václav. Evolving Boolean Functions for Fast and Efficient Randomness Testing. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18). Kyoto: Association for Computing Machinery, 2018, pp. 1302-1309. ISBN 978-1-4503-5618-3.
Czech title
Evoluční návrh Boolovských funkcí pro rychlé a efektivní testování náhodnosti
Type
conference paper
Language
english
Authors
Mrázek Vojtěch, Ing., Ph.D. (DCSY FIT BUT)
Sýs Marek, Mgr., Ph.D. (FI MUNI)
Vašíček Zdeněk, doc. Ing., Ph.D. (DCSY FIT BUT)
Sekanina Lukáš, prof. Ing., Ph.D. (DCSY FIT BUT)
Matyáš Václav, prof. RNDr., M.Sc., Ph.D. (FI MUNI)
Keywords
Boolean function, genetic algorithm, statistical randomness testing
Abstract
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.
Published
2018
Pages
1302-1309
Proceedings
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18)
Conference
Genetic and Evolutionary Computations Conference 2018, Kyoto, JP
ISBN
978-1-4503-5618-3
Publisher
Association for Computing Machinery
Place
Kyoto, JP
DOI
BibTeX
@INPROCEEDINGS{FITPUB11686,
   author = "Vojt\v{e}ch Mr\'{a}zek and Marek S\'{y}s and Zden\v{e}k Va\v{s}\'{i}\v{c}ek and Luk\'{a}\v{s} Sekanina and V\'{a}clav Maty\'{a}\v{s}",
   title = "Evolving Boolean Functions for Fast and Efficient Randomness Testing",
   pages = "1302--1309",
   booktitle = "Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18)",
   year = 2018,
   location = "Kyoto, JP",
   publisher = "Association for Computing Machinery",
   ISBN = "978-1-4503-5618-3",
   doi = "10.1145/3205455.3205518",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11686"
}
Back to top