Designing Bent Boolean Functions With Parallelized Linear Genetic Programming

Bent Boolean functions, nonlinearity, parallelization, linear programming.

Bent Boolovské funkce jsou jedním z kryptografických primitiv nezbytných pro zajištění bezpečnosti kryptografických algoritmů, kde poskytují nelinearitu jinak lineárním systémům. Maximální možná nelinearita Boolovské funkce je určena počtem jejích vstupů. K zaručení dostatečné bezpečnosti moderních systémů je tak zapotřebí vytvářet stále nové a větší Boolovské funkce. Jedním z přístupů který lze pro návrhu těchto funkcí použít je genetické programování. Tento článek navrhuje, k návrhu bent Boolovských funkcí, použít metodu lineárního genetického programování. Článek demonstruje že tento přístup umožňuje navrhnout větší funkce než které mohou být navrženy pomocí ostatních přístupů, a zkoumá jaký je vliv jednotlivých evolučních parametrů na množství výpočetního času, který je k uskutečnění tohoto návrhu potřeba. Paralelní implementace navržené metody je použita k nalezení nových bent boolovských funkcí, a její výstupy jsou porovnány s jinými podobnými metodami. Výsledky ukazují, že lineární genetické programování je schopno si s rostoucím množstvím požadovaných vstupů poradit lépe než ostatní přístupy, což umožňuje ve srovnatelném čase dosáhnou návrhu výrazně větších funkcí.