Algebraic Curves and Finite Fields: Cryptography and Other Applications (Radon Series on Computational and Applied Mathematics 16) (Radon Computational and Applied Mathematics, 16)

Algebra and number theory have always been counted among the most beautiful and fundamental mathematical areas with deep proofs and elegant results. However, for a long time they were not considered of any substantial importance for real-life applications. This has dramatically changed with the appearance of new topics such as modern cryptography, coding theory, and wireless communication. Nowadays we find applications of algebra and number theory frequently in our daily life. We mention security and error detection for internet banking, check digit systems and the bar code, GPS and radar systems, pricing options at a stock market, and noise suppression on mobile phones as most common examples. This book collects the results of the workshops "Applications of algebraic curves" and "Applications of finite fields" of the RICAM Special Semester 2013. These workshops brought together the most prominent researchers in the area of finite fields and their applications around the world. They address old and new problems on curves and other aspects of finite fields, with emphasis on their diverse applications to many areas of pure and applied mathematics. Introduction Contents Generic Newton polygons for curves of given p-rank 1 Introduction 2 Structures in positive characteristic 2.1 The p-rank 2.2 Newton polygons 2.3 Semicontinuity and purity 2.4 Notation on stratifications and Newton polygons 3 Stratifications on the moduli space of Abelian varieties 3.1 The p-ranks of Abelian varieties 3.2 Newton polygons of Abelian varieties 4 The p-rank stratification of the moduli space of stable curves 4.1 The moduli space of stable curves 4.2 The p-rank stratification of Mg 4.3 Connectedness of p-rank strata 4.4 Open questions about the p-rank stratification 5 Stratification by Newton polygon 5.1 Newton polygons of curves of small genus 5.2 Generic Newton polygons 6 Hyperelliptic curves 7 Some conjectures about Newton polygons of curves 7.1 Nonexistence philosophy 7.2 Supersingular curves 7.3 Other nonexistence results Good towers of function fields 1 Introduction 2 The Drinfeld modular towers (X0(Pn))n≥0 3 An example of a classical modular tower 4 A tower obtained from Drinfeldmodules over a different ring 4.1 Explicit Drinfeld modules of rank 2 4.2 Finding an isogeny 4.3 Obtaining a tower Correlation-immune Boolean functions for easing counter measures to side-channel attacks 1 Introduction 2 Preliminaries 2.1 The combiner model of pseudo-random generator in a stream cipher and correlation-immune functions 2.2 Side-channel attacks 2.3 Masking counter measure 3 Methods for allowing masking to resist higher order side-channel attacks 3.1 Leakage squeezing for first-order masking 3.2 Leakage squeezing for second-order masking 3.3 Rotating S-box masking 4 New challenges for correlation-immune Boolean functions 4.1 Basic facts on CI functions, orthogonal arrays and dual distance of codes 4.2 Known constructions of correlation-immune functions 4.3 Synthesis of minimal weights of d-CI Boolean functions The discrete logarithm problem with auxiliary inputs 1 Introduction 2 Algorithms for the ordinary DLP 2.1 Generic algorithms 2.2 Nongeneric algorithms 3 The DLPwAI and Cheon’s algorithm 3.1 p - 1 cases 3.2 Generalized algorithms 4 Polynomials with small value sets 4.1 Fast multipoint evaluation in a blackbox manner 4.2 An approach using polynomials of small value sets 5 Approach using the rational polynomials: Embedding to elliptic curves 6 Generalized DLPwAI 6.1 Representation of a multiplicative subgroup of Z×p-1 6.2 A group action on Z*p and polynomial construction 6.3 Main result 7 Applications and implications 7.1 Strong Diffie–Hellman problem and its variants 7.2 Attack on the existing schemes using Cheon’s algorithm 8 Open problems and further work Garden of curves with many automorphisms 1 Introduction 2 Notation and background 3 Upper bounds on the size of G depending on g 4 Upper bounds on the size of the p-subgroups of G depending on the p-rank 5 Examples of curves with large automorphism groups 5.1 Curves with unitary automorphism group 5.2 Curves with Suzuki automorphism group 5.3 Curves with Ree automorphism group 5.4 The Giulietti–Korchmáros curve 5.5 The generalized GK curve 5.6 A curve admitting SU(3, p) as an automorphism group 5.7 General hyperelliptic curves with a K-automorphism 2-group of order 2g + 2 5.8 A curve with genus g = (2h - 1)2 admitting a K-automorphism 2-group of order of order 2(g - 1) + 2h+1 - 2 5.9 General bielliptic curves with a dihedral K-automorphism 2-group of order 4(g - 1) 5.10 A curve of genus g with a semidihedral K-automorphism 2-group of order 2(g - 1) 6 Characterizations 6.1 Curves with many automorphisms with respect to their genus 6.2 Curves with a large nontame automorphism group 6.3 Theorem 6.2 and some generalizations of Deligne–Lusztig curves 6.4 Group-theoretic characterizations 7 The possibilities for G when the p-rank is 0 8 Large automorphism p-groups in positive p-rank 8.1 p = 2 8.2 p = 3 8.3 p > 3 Nonlinear shift registers – A survey and challenges 1 Introduction 2 Nonlinear shift registers 2.1 The binary de Bruijn graph 2.2 The pure cycling register 2.3 The complementary cycling register 2.4 De Bruijn sequences 3 Mykkeltveit’s proof of Golomb’s conjecture 4 The D-morphism 5 Conjugate pairs in PCR 6 Finite fields and conjugate pairs 6.1 Cycle joining and cyclotomy 7 Periodic structure of NLFSRs 8 Conclusions Permutations of finite fields and uniform distribution modulo 1 1 Introduction 2 Preliminaries 3 Good and weak families of permutations 4 Existence of good families 5 Permutation polynomials of Carlitz rank 3 6 Bounds for f(Sσp) 7 Computational results 8 Concluding remarks Semifields, relative difference sets, and bent functions 1 Introduction 2 Semifields 3 Relative difference sets 4 Relative difference sets and semifields 5 Planar functions in odd characteristic 6 Planar functions in characteristic 2 7 Component functions of planar functions 8 Concluding remarks and open problems NTRU cryptosystem: Recent developments and emerging mathematical problems in finite polynomial rings 1 Introduction 2 Notation and preliminaries 2.1 Notation 2.2 Probability and algorithms 2.3 Rings 2.4 Lattices 3 Review of the NTRU cryptosystem 3.1 The NTRU construction 3.2 Security of NTRU: Computational/statistical problems and known attacks 4 Recent developments in security analysis of NTRU 4.1 Overview 4.2 Gaussian distributions modulo lattices and Fourier analysis 4.3 Statistical hardness of the NTRU decision key cracking problem 4.4 Computational hardness of the ciphertext cracking problem 5 Recent developments in applications of NTRU 5.1 NTRU-based homomorphic encryption 5.2 NTRU-based multilinearmaps 6 Conclusions Analog of the Kronecker–Weber theorem in positive characteristic 1 Introduction 2 The classical case 3 A proof of the Kronecker–Weber theorem based on ramification groups 4 Cyclotomic function fields 5 The maximal Abelian extension of k 6 Reciprocity law 7 The proof of David Hayes 8 Witt vectors and the conductor 8.1 The conductor 8.2 The conductor according to Schmid 9 The Kronecker–Weber–Hayes theorem 10 Final remarks Index This bookcollects the results of the workshops on Applications of Algebraic CurvesandApplications of Finite Fieldsat the RICAMin 2013. These workshopsbrought together the most prominet researchers in the area of finite fields and their applications around the world, addressing old and new problems on curves and other aspects of finite fields, with emphasis on their diverse applications to many areas of pure and applied mathematics