Semantic Mutation Operator for Fast and Efficient Design of Bent Boolean Functions

Nelinearita, ohnuté booleovské funkce, heuristická optimalizace, Genetické programování, Sémantická mutace

Booleovské funkce jsou důležitá kryptografická primitiva s rozsáhlým využitím v symetrické kryptografii. Aby byly tyto funkce užitečné, musí mít různé vlastnosti, například nelinearitu. Hlavním limitujícím faktorem kvality booleovské funkce je dostatečně velký počet jejích vstupních proměnných. Současné konstrukční metody buď špatně škálují, nebo jsou schopny tvořit pouze malou podmnožinu všech booleovských funkcí s požadovanými vlastnostmi, což vyžaduje vývoj nových a efektivnějších způsobů jak je tvořit. V tomto článku navrhujeme nový operátor sémantické mutace pro tvorbu ohnutých booleovských funkcí pomocí genetického programování. Princip navrhovaného operátoru spočívá v podrobném vyhodnocení nelinearity funkce, tak, aby se zabránilo potenciálně rušivým mutacím, a ve využití skutečnosti, že nelinearita booleovské funkce zůstává při všech afinních transformacích neměnná. Abychom vyhodnotili efektivitu tohoto operátoru, experimentujeme se třemi různými variantami genetického programování, a jeho výkon porovnáváme vůči třem dalším, běžně používaným, ne-sémantickým operátorům mutace. Podrobné experimentální vyhodnocení prokázalo, že navrhovaný sémantický operátor mutace je nejen výrazně efektivnější z hlediska počtu jedinců kteří genetickým programování musejí být vyhodnoceni, ale je také téměř třikrát rychlejší než druhý nejlepší operátor při navrhování ohýbaných funkcí s 12 vstupy a téměř šestkrát rychlejší pro funkce s 20 vstupy.