SaTC: CORE: Small: Applications of Galois Theory to the Search for Non-Linear Functions

Block ciphers and hash functions are a foundational building block of secret key Cryptography. Almost Perfect Nonlinear (APN) functions, i.e. functions defined over a finite field that behave as non-linearly as possible, are used to design block ciphers and hash functions secure against differential attacks. This project supports research on the construction of APN functions that impact the design of the next generation of ciphers which will need to operate in constraint environments (lightweight cryptography), and feature large keys to offer high levels of bit security against quantum adversaries.

The broader impacts of this project include the organization of workshops bringing together Academia and Industry, the development of new cryptography curriculum at USF, the organization of Summer camps, and the design of animated videos featuring important concepts in cryptography.

To achieve the construction of new APN functions, this project supports the development of Galois theoretical methods to decide whether APN functions (more specifically APN permutations) exist for given parameters such as the size of the finite field and the degree of the APN function. In particular, the problem of finding an APN function is converted into the problem of solving a polynomial system of equations arising from group theory.

This generates multiple polynomial systems, each one allowing either the construction of a given APN function for a chosen degree, or the proof of non-existence of APN permutations for the target degree. The methods developed as part of this project are constructive and they can be efficiently implemented via some standard computational algebra software such as Magma or Sage.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.