Almost perfect nonlinear functions and related combinatorial structures

Date
2005-01-01
Authors
Maxwell, Mandi
Major Professor
Advisor
Sung-Yell Song
Clifford Bergman
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
Abstract

A map f(x) from the finite field Fpn to itself is said to be differentially k-uniform if k is the maximum number of solutions of the equation f(x + a) - f(x) = b where a, b [is in] Fpn , a ≠ 0. In particular, 2-uniform maps over F2n are called almost perfect nonlinear (APN) maps. These maps are of interest in cryptography because they offer optimum resistance to linear and differential attacks on certain cryptosystems. They can also be used to construct several combinatorial structures of interest.;In this dissertation, we characterize and classify all known power maps f(x) = xd over F2n , which are APN or of low uniformity. We discuss some basic properties of APN maps, collect all known APN power maps, and give a classification of APN power maps up to equivalence. We also give some insight regarding efforts to find other APN functions or prove that others do not exist and classify all power maps according to their degree of uniformity for n up to 13.;In the latter part of this dissertation, through the introduction of an incidence structure, we study how these functions can be used to construct semi-biplanes utilizing the method of Robert S. Coulter and Marie Henderson. We then consider a particular class of APN functions, from which we construct symmetric association schemes of class two and three. Using the result of E. R. van Dam and D. Fon-Der-Flaass, we can see that the relation graphs of some of these association schemes are distance-regular graphs. We discuss the local structure of these distance-regular graphs and characterize them.

Comments
Description
Keywords
Citation
Source