Niederreiter / Ostafe / Panario Algebraic Curves and Finite Fields

Cryptography and Other Applications
1. Auflage 2014
ISBN: 978-3-11-031791-6
Verlag: De Gruyter
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, Band 16, 251 Seiten

Reihe: Radon Series on Computational and Applied MathematicsISSN

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.

Zielgruppe

Researchers in Mathematics and Computer Science; Academic libraries

Autoren/Hrsg.

Niederreiter, Harald

Ostafe, Alina

Panario, Daniel

Winterhof, Arne

Weitere Mitwirkende

Achter, Jeffrey D.

Bassa, Alp

Beelen, Peter

Cheon, Jung Hee

Claude, Carlet

Giulietti, Massimo

Guilley, Sylvain

Helleseth, Tor

Kim, Taechan

Korchmaros, Gabor

Nguyen, Nhut

Pausinger, Florian

Pott, Alexander

Pries, Rachel

Schmidt, Kai-Uwe

Song, Yongsoo

Steinfeld, Ron

Topuzoglu, Alev

Villa-Salvador, Gabriel D.

Zhou, Yue

Fachgebiete

• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik Mathematik Algebra Zahlentheorie

Inhaltsverzeichnis

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

Über Autor(innen)

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