Algebraic Curves and Finite Fields (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Harald Niederreiter, JKU Linz, Austria;Alina Ostafe, Macquarie University, NSW, Australia; Daniel Panario, Carleton University, Ottawa, Ontario, Canada; Arne Winterhof, JKU Linz, Austria.

Introduction 5
Contents 7
Generic Newton polygons for curves of given p-rank 13
1 Introduction 13
2 Structures in positive characteristic 15
2.1 The p-rank 15
2.2 Newton polygons 16
2.3 Semicontinuity and purity 19
2.4 Notation on stratifications and Newton polygons 20
3 Stratifications on the moduli space of Abelian varieties 21
3.1 The p-ranks of Abelian varieties 21
3.2 Newton polygons of Abelian varieties 22
4 The p-rank stratification of the moduli space of stable curves 23
4.1 The moduli space of stable curves 23
4.2 The p-rank stratification of Mg 24
4.3 Connectedness of p-rank strata 25
4.4 Open questions about the p-rank stratification 25
5 Stratification by Newton polygon 26
5.1 Newton polygons of curves of small genus 26
5.2 Generic Newton polygons 27
6 Hyperelliptic curves 28
7 Some conjectures about Newton polygons of curves 30
7.1 Nonexistence philosophy 31
7.2 Supersingular curves 32
7.3 Other nonexistence results 32
Good towers of function fields 35
1 Introduction 35
2 The Drinfeld modular towers (X0(Pn))n=0 37
3 An example of a classical modular tower 44
4 A tower obtained from Drinfeldmodules over a different ring 45
4.1 Explicit Drinfeld modules of rank 2 45
4.2 Finding an isogeny 48
4.3 Obtaining a tower 50
Correlation-immune Boolean functions for easing counter measures to side-channel attacks 53
1 Introduction 54
2 Preliminaries 57
2.1 The combiner model of pseudo-random generator in a stream cipher and correlation-immune functions 57
2.2 Side-channel attacks 61
2.3 Masking counter measure 63
3 Methods for allowing masking to resist higher order side-channel attacks 65
3.1 Leakage squeezing for first-order masking 65
3.2 Leakage squeezing for second-order masking 67
3.3 Rotating S-box masking 68
4 New challenges for correlation-immune Boolean functions 70
4.1 Basic facts on CI functions, orthogonal arrays and dual distance of codes 70
4.2 Known constructions of correlation-immune functions 73
4.3 Synthesis of minimal weights of d-CI Boolean functions 77
The discrete logarithm problem with auxiliary inputs 83
1 Introduction 84
2 Algorithms for the ordinary DLP 85
2.1 Generic algorithms 85
2.2 Nongeneric algorithms 88
3 The DLPwAI and Cheon’s algorithm 90
3.1 p - 1 cases 91
3.2 Generalized algorithms 92
4 Polynomials with small value sets 94
4.1 Fast multipoint evaluation in a blackbox manner 94
4.2 An approach using polynomials of small value sets 95
5 Approach using the rational polynomials: Embedding to elliptic curves 96
6 Generalized DLPwAI 97
6.1 Representation of a multiplicative subgroup of Z×p-1 97
6.2 A group action on Z*p and polynomial construction 98
6.3 Main result 98
7 Applications and implications 99
7.1 Strong Diffie–Hellman problem and its variants 99
7.2 Attack on the existing schemes using Cheon’s algorithm 100
8 Open problems and further work 101
Garden of curves with many automorphisms 105
1 Introduction 105
2 Notation and background 106
3 Upper bounds on the size of G depending on g 107
4 Upper bounds on the size of the p-subgroups of G depending on the p-rank 108
5 Examples of curves with large automorphism groups 109
5.1 Curves with unitary automorphism group 109
5.2 Curves with Suzuki automorphism group 110
5.3 Curves with Ree automorphism group 111
5.4 The Giulietti–Korchmáros curve 111
5.5 The generalized GK curve 112
5.6 A curve admitting SU(3, p) as an automorphism group 113
5.7 General hyperelliptic curves with a K-automorphism 2-group of order 2g + 2 113
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 113
5.9 General bielliptic curves with a dihedral K-automorphism 2-group of order 4(g - 1) 114
5.10 A curve of genus g with a semidihedral K-automorphism 2-group of order 2(g - 1) 116
6 Characterizations 117
6.1 Curves with many automorphisms with respect to their genus 117
6.2 Curves with a large nontame automorphism group 118
6.3 Theorem 6.2 and some generalizations of Deligne–Lusztig curves 119
6.4 Group-theoretic characterizations 121
7 The possibilities for G when the p-rank is 0 122
8 Large automorphism p-groups in positive p-rank 124
8.1 p = 2 124
8.2 p = 3 128
8.3 p > 3
Nonlinear shift registers – A survey and challenges 133
1 Introduction 133
2 Nonlinear shift registers 135
2.1 The binary de Bruijn graph 136
2.2 The pure cycling register 138
2.3 The complementary cycling register 138
2.4 De Bruijn sequences 138
3 Mykkeltveit’s proof of Golomb’s conjecture 141
4 The D-morphism 144
5 Conjugate pairs in PCR 146
6 Finite fields and conjugate pairs 147
6.1 Cycle joining and cyclotomy 149
7 Periodic structure of NLFSRs 151
8 Conclusions 154
Permutations of finite fields and uniform distribution modulo 1 157
1 Introduction 157
2 Preliminaries 158
3 Good and weak families of permutations 162
4 Existence of good families 163
5 Permutation polynomials of Carlitz rank 3 164
6 Bounds for f(Ssp) 
166 
7 Computational results 168
8 Concluding remarks 169
Semifields, relative difference sets, and bent functions 173
1 Introduction 173
2 Semifields 174
3 Relative difference sets 177
4 Relative difference sets and semifields 179
5 Planar functions in odd characteristic 183
6 Planar functions in characteristic 2 184
7 Component functions of planar functions 185
8 Concluding remarks and open problems 187
NTRU cryptosystem: Recent developments and emerging mathematical problems in finite polynomial rings 191
1 Introduction 191
2 Notation and preliminaries 193
2.1 Notation 193
2.2 Probability and algorithms 193
2.3 Rings 194
2.4 Lattices 194
3 Review of the NTRU cryptosystem 195
3.1 The NTRU construction 195
3.2 Security of NTRU: Computational/statistical problems and known attacks 197
4 Recent developments in security analysis of NTRU 201
4.1 Overview 201
4.2 Gaussian distributions modulo lattices and Fourier analysis 204
4.3 Statistical hardness of the NTRU decision key cracking problem 207
4.4 Computational hardness of the ciphertext cracking problem 210
5 Recent developments in applications of NTRU 212
5.1 NTRU-based homomorphic encryption 212
5.2 NTRU-based multilinearmaps 216
6 Conclusions 219
Analog of the Kronecker–Weber theorem in positive characteristic 225
1 Introduction 225
2 The classical case 227
3 A proof of the Kronecker–Weber theorem based on ramification groups 228
4 Cyclotomic function fields 231
5 The maximal Abelian extension of k 233
6 Reciprocity law 235
7 The proof of David Hayes 236
8 Witt vectors and the conductor 237
8.1 The conductor 240
8.2 The conductor according to Schmid 240
9 The Kronecker–Weber–Hayes theorem 241
10 Final remarks 247
Index 251