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

分组密码和散列函数是密钥密码学的基本构建块。几乎完美非线性（APN）函数，即在有限域上定义的尽可能非线性的函数，用于设计抗差分攻击的分组密码和散列函数。该项目支持对APN功能构建的研究，这些APN功能影响下一代密码的设计，这些密码需要在约束环境中运行（轻量级密码学），并具有大密钥，以提供针对量子对手的高级别比特安全性。该项目更广泛的影响包括组织学术界和工业界的研讨会，在USF开发新的密码学课程，组织夏令营，以及设计以密码学重要概念为主题的动画视频。为了实现新APN功能的构建，该项目支持伽罗瓦理论方法的发展，以确定APN是否起作用对于给定的参数，例如有限域的大小和APN函数的次数，存在APN置换（更具体地说，APN置换）。特别是，找到APN函数的问题被转换成求解由群论产生的多项式方程组的问题。这生成多个多项式系统，每个多项式系统允许为所选度构造给定的APN函数，或者证明目标度的APN排列不存在。作为该项目的一部分开发的方法是建设性的，它们可以通过一些标准的计算代数软件，如岩浆或Sage有效地实施。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.