Mappings and Sequences over Finite Fields

点击翻译按钮获取中文摘要

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.