Resemblance of polynomials over finite fields and related topics
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
The main contribution of this dissertation is to develop the theory of resemblance. We introduce the concept of the resemblance of two functions over a finite group, defined by the number of images of their difference. This is a way to measure the distance of a polynomial over finite fields from being a certain type of polynomial. Our motivation is to provide a new approach to an important problem in cryptanalysis---the construction of permutation polynomials (bijections) over finite fields with low differential uniformity. We show that one of our notions, permutation resemblance, can be used to bound the differential uniformity of the permutation obtained by adding a function to a known optimal function. ☐ We also develop algorithms to compute the resemblance of a function. Our method is based on linear integer programming, and can be generalized to a linear integer program whose solution is a permutation polynomial with lowest differential uniformity. Independent to the theory of resemblance, we also work on two problems on polynomials over finite fields that are related to counting the number of solutions to some particular equations. ☐ This dissertation has three parts. The preliminaries are given in Chapters 1 and 2. We introduce the background, motivation, notation, and recall some previous results in Chapter 1. In Chapter 2, we present an expression of the number of non-images of a function between two finite sets in terms of all possible tuples from each preimage set. This leads to a lower and upper bound for the number of images of a function. ☐ Chapters 3 to 7 are focused on resemblance. We formally introduce resemblance, permutation resemblance, and linear resemblance in Chapter 3, and discuss their behavior under some well-known equivalence relations on functions. In Chapters 4 and 5, we present theoretical results on permutation resemblance and linear resemblance, respectively. We establish non-trivial upper and lower bounds of permutation resemblance, and determine the permutation resemblance of two infinite families of polynomials. We also explain why we think permutation resemblance is an important concept for constructing permutation polynomials with low differential uniformity. We also establish three lower bounds for the linear resemblance of some special classes of polynomials, and explore a possible direction for general cases. In Chapter 6, we present the algorithmic approaches for determining the resemblance. We mainly focus on computing the permutation resemblance, but we also show that our method for computing the permutation resemblance can be generalized to compute linear resemblance and differential uniformity. We implement our algorithm for permutation resemblance and present some computation results in Chapter 7. ☐ In Chapters 8 and 9, we present our work on two problems that are related to counting the number of solutions to some equations. These problems initially arose during the research on resemblance, but they are independent to the theory of resemblance. In Chapter 8, we completely determine the preimage distribution of a class of polynomials by evaluating exponential sums. In Chapter 9, we give upper bounds to the differential uniformity of the class of Wan-Lidl polynomials. In particular, our results imply that a subclass of such polynomials form an infinite family of permutation polynomials with differential uniformity at most five. ☐ Finally, we close this dissertation by listing some open problems and possible future directions. In the Appendix, we give some computer code samples that were used to obtain the data presented in this thesis. ☐ Parts of this thesis have been accepted for publication or submitted. Here is a list of these chapters and corresponding papers. • Chapter 9 is based on : Bounds on the differential uniformity of the Wan-Lidl permutation polynomials, with Robert S. Coulter, Cryptography and Communications (2023) https://doi.org/10.1007/s12095-023-00634-6. • Section 2.1, Chapter 4, and the discussion of permutation resemblance in Chapter 3 are based on: Permutation resemblance, with Robert S. Coulter, submitted. • Chapters 6 and 7 are based on: Algorithms for computing the permutation resemblance of functions over finite groups, with Robert S. Coulter, submitted.
Description
Keywords
Differential uniformity, Finite fields, Permutation polynomials