Computational methods for finding cryptographic functions

Abstract

Recent studies have demonstrated several methods on different approaches to classi- fication of vectorial Boolean functions up to certain equivalence relation and to finding new quadratic Almost Perfect Nonlinear (APN) functions. In this work we explore these classification methods of vectorial Boolean functions, in particular those that minimise the search space up to EA-equivalence or linear-equivalence. We also investigate various strategies for finding quadratic APN functions. These methods are rooted in various aspects of algebraic theory. We explore the mathematical theory in more detail, and provide a guide to practical application of the theory. We also provide implementations of these methods and illustrate them in the context of the presented theory. 1

Nedávné studie přinesly několik různých přístupů ke klasifikaci vektorových booleovských funkcí na základě různě definovaných relací ekvivalence, a k nalezení nových kvadrat- ických "téměř dokonale nelineárních" (APN) funkcí. V této práci se zabýváme těmito klasifikacemi a to především takovými, které zmenšují počet všech hledaných funkcí na základě rozdělení do tříd EA-ekvivalence nebo lineární ekvivalence. Zároveň se také věnujeme různým přístupům pro hledání kvadratických APN funkcí. Tyto metody mají základ v odlišných odvětvích algebraické teorie. Podrobněji se zabýváme matematickou částí této teorie a poskytujeme popis jejího praktického uplatnění. Rovněž přinášíme implementace těchto metod a vysvětlujeme je v kontextu popsané teorie. 1