Mappings and Sequences over Finite Fields

我们寻求进一步理解代数映射发生在算法的设计和分析中，特别是在密码学和组合学中。长期计划有三个研究轴：******(1)对实际相关的映射迭代进行深入分析。有限域上函数迭代的动力学问题近年来引起了人们的广泛关注，部分原因是其在密码学和波拉德算法等整数分解方法中的应用。有限域上函数迭代的研究主要集中在：周期和周期前；平均rho长度；连接组件数；周期长度（最大、最小、平均）；不动点的个数和构成排列的条件；等等......。我们的利益是双重的。首先，我们将从理论上研究具有实际意义的多项式和有理函数的特定族的行为，特别是在密码和哈希函数中。其次，我们的目标是进一步研究带约束的随机映射作为模型来理解密码应用中函数的迭代。我们将研究这些模型的精度与二次多项式的实际迭代（如波拉德算法）、哈希函数的迭代和s盒函数的迭代之间的关系。******(2)继续努力设计特殊的函数和有效的算法，特别注意加密应用。这一努力将是双重的。首先，我们将集中讨论函数的微分均匀性。引入这个概念是为了防止差分密码分析。具有低差分均匀性的功能是理想的；它们包括PN（完全非线性）和APN（几乎完全非线性）函数。作为这项工作的一部分，我们将寻找具有低差分一致性的新功能，以及相关的概念，如良好的模糊性和缺陷。我们还打算在考虑到其他攻击时研究这些以及类似的措施。其次，我们将继续设计和分析有限域算法的有效算法。对于这些实际应用程序来说，尽可能优化实现和尽可能高效的实现是至关重要的。******(3)基于有限域序列的新组合数组的发展在应用中是有用的。我们建议使用来自线性和非线性反馈移位寄存器（FSRs）的有限域上的广泛类别的序列来构建新的记录实现组合数组。特别是，我们建议进一步使用fsr来构建可用于软件测试的覆盖阵列。我们还将研究fsr在相关组合对象中的使用，例如基于不同类型度量的有序正交阵列，包括Hamming， Lee和偏置度量。

We seek to further the understanding of algebraic mappings that occur in the design and analysis of algorithms, specially in cryptography and combinatorics. The long-term plan has three axes of research:******(1) The in-depth analysis of iterations of mappings that are practically relevant. The dynamics of iterations of functions over finite fields have attracted much attention in recent years, in part due to their applications in cryptography and integer factorization methods like Pollard rho algorithm. Studies of iterations of functions over finite fields have centered on: period and preperiod; (average) rho length; number of connected components; length of cycles (largest, smallest, average); number of fixed points and conditions to be a permutation; and so on. Our interest is two-fold. First, we will investigate, theoretically, the behaviour of particular families of polynomials and rational functions of practical interest, especially in ciphers and hash functions. Second, we aim to further the study of random mappings with restrictions as models to understand the iterations of functions in cryptographic applications. We will study the relationship between the accuracy of these models and practical iterations of quadratic polynomials (like in Pollard rho algorithm), iterations of hash functions, and iterations of S-box functions. ******(2) The continued effort to design special functions and efficient arithmetic, with particular attention given to cryptographical applications. This effort will be two-fold. First, we will concentrate on differential uniformity of functions. This concept was introduced to defend against differential cryptanalysis. Functions with low differential uniformity are desired; these include PN (perfect nonlinear) and APN (almost perfect nonlinear) functions. As part of this effort, we will search for new functions with low differential uniformity, as well as related concepts such as good ambiguity and deficiency. We also aim to study these and similar measures when other attacks are taken into account. Second, we will continue the design and analysis of efficient algorithms for finite fields arithmetic. Optimal implementations when possible, and otherwise as efficient as possible, are paramount for these practical applications.******(3) The development of new combinatorial arrays coming from sequences over finite fields useful in applications. We propose to use broad classes of sequences over finite fields coming from Linear and Nonlinear Feedback Shift Registers (FSRs) to construct new record achieving combinatorial arrays. In particular, we propose to further the use of FSRs to build covering arrays that could be used in software testing. We will also investigate the use of FSRs in related combinatorial objects such as ordered orthogonal arrays based on different types of metrics, including Hamming, Lee, and poset metrics.