Original title: Evoluce kryptografických funkcí s pomocí lokálního prohledávání
Translated title: Evolution of cryptographic functions with local search
Authors: Kadlecová, Tereza ; Matoušek, Jiří (referee) ; Husa, Jakub (advisor)
Document type: Bachelor's theses
Year: 2026
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Jednou z nejdůležitějších vlastností kryptografických funkcí je nelinearita. Maximální nelinearity lze dosáhnout pouze u funkcí se sudým počtem vstupů. Pokud má funkce lichý počet vstupů, je problém nejvyšší dosažitelné nelinearity stále otevřený. Existuje několik způsobů, jak funkce s vysokou nelinearitou vytvořit – jedním z nich je heuristická konstrukce. Mezi používané heuristiky patří evoluční algoritmy, ze kterých v tomto oboru nejlepší výsledky obvykle poskytuje genetické programování. Lokální prohledávání je heuristika, kde je z kandidátního řešení iterativní aplikací operátorů prohledáván prostor řešení. Přidání tohoto kroku by mělo zvýšit efektivitu heuristického přístupu k řešení problému tvorby vysoce nelineárních kryptografických funkcí. Tato práce se omezuje na hledání rotačně symetrických funkcí s devíti vstupy. V průběhu práce bylo vyzkoušeno mnoho různých nastavení dvou nově navržených algoritmů lokálního prohledávání a bylo statisticky dokázáno, že s jejich pomocí lze snížit počet vyhodnocovaných kandidátních řešení a zvýšit tak efektivitu evolučního algoritmu. One of the most important properties of cryptographic functions is nonlinearity. Maximum nonlinearity can be achieved only for functions with an even number of inputs. If a function has an odd number of inputs, the maximum achievable nonlinearity is still an open problem. There are multiple ways in which functions with high nonlinearity can be created – one of them is heuristic construction. Evolutionary algorithms are one of these heuristic constructions and in the field of cryptography the best results are usually achieved by genetic programming. Local search is a heuristic, where problem space is searched by iterative application of operators on a candidate solution. By adding this step the efficiency of the heuristic approach to finding highly nonlinear cryptographic functions should be improved. This work is focused on searching for rotation symmetric boolean functions with nine inputs. In this work we tried many settings of two newly proposed local search algorithms and it was statistically proven that with their help the number of evaluated candidate solutions can be decreased, thus improving the efficiency of the evolutionary algorithm.
Keywords: Boolean functions.; cryptography; Genetic programming; local search; nonlinearity; booleovské funkce.; Genetické programování; kryptografie; lokální prohledávání; nelinearita

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/258829

Permalink: http://www.nusl.cz/ntk/nusl-777435


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses