Algebraic Geometry for Coding Theory and Cryptography (eBook)

Preface 7
Contents 10
Contributors 11
1 Representations of the Multicast Network Problem 14
1.1 Introduction 15
1.1.1 Achieving Multicast Network Requirements 15
1.2 Coding Points and Reduced Multicast Networks 17
1.3 Code Graphs 23
1.4 Fq-Vector Labelings and Matrices 27
1.4.1 Fq-Vector Labelings and Rational Points 31
1.4.2 Fq-Vector Labelings and Grassmannians 32
1.4.3 An Open Question on Fq-Vector Labelings of Code Graphs 34
References 36
2 Hypersurfaces in Weighted Projective Spaces Over Finite Fields with Applications to Coding Theory 37
2.1 Introduction 38
2.2 Polynomials with Many Zeros 42
2.3 Hypersurfaces in Weighted Projective Planes P(1,a1,a2) 44
2.4 Weighted Projective Reed–Muller Codes 49
2.4.1 Generalized Reed–Muller Codes, Projective Reed–Muller Codes, and Projective Nested Cartesian Codes 49
2.4.2 Weighted Projective Reed–Muller Codes 51
2.4.2.1 Length and Dimension 51
2.4.2.2 Minimum Distance 52
2.4.2.3 A Particular Case 52
2.4.2.4 Another Particular Case 53
2.4.2.5 Relative Parameters 53
References 55
2.A Appendix: Weighted Projective Spaces 56
2.A.1 Definitions of Weighted Projective Spaces 57
2.A.1.1 WPS as a Proj Functor 57
2.A.1.2 Quotients 57
2.A.1.3 WPS as a Quotient of the Punctured Affine Space 58
2.A.1.4 WPS as a Finite Quotient of the Projective Space 58
2.A.2 The Singular Locus 60
2.A.3 Affine Parts 61
2.A.3.1 Quotient of the Affine Space by a Cyclic Group 61
2.A.3.2 Affine Parts 61
2.A.3.3 A Special Case 65
2.A.3.4 Action of Gm 65
2.A.4 Rationality 66
2.A.5 Weighted Forms 68
2.A.5.1 Definition 68
2.A.5.2 Weighted Binary Forms 69
2.A.5.3 Weighted Ternary Forms 70
References 72
3 Isogenies for Point Counting on Genus Two Hyperelliptic Curves with Maximal Real Multiplication 74
3.1 Introduction 75
3.1.1 The State of the Art 75
3.1.2 Our Contributions, and Beyond 76
3.1.3 Vanilla Abelian Varieties 77
3.2 Genus One Curves: Elliptic Curve Point Counting 78
3.2.1 Schoof's Algorithm 79
3.2.2 Frobenius Eigenvalues and Subgroups 80
3.2.3 Modular Polynomials and Isogenies 80
3.2.4 Elkies, Atkin, and Volcanic Primes 81
3.2.5 Computing the Type of a Prime 82
3.2.6 Atkin's Improvement 83
3.2.7 Elkies' Improvement 83
3.3 The Genus-2 Setting 84
3.3.1 The Jacobian 84
3.3.2 Frobenius and Endomorphisms of JC 85
3.3.3 Real Multiplication 85
3.3.4 From Schoof to Pila 86
3.3.5 The Gaudry–Schost Approach 86
3.3.6 Point Counting with Efficiently Computable RM 88
3.3.7 Generalizing Elkies' and Atkin's Improvements to Genus-2 89
3.3.8 mu-Isogenies 90
3.4 Invariants 90
3.4.1 Invariants for RM Abelian Surfaces 91
3.4.2 Hilbert Modular Polynomials for RM Abelian Surfaces 91
3.4.3 Invariants for Curves and Abelian Surfaces 93
3.4.4 Pulling Back Curve Invariants to RM Invariants 94
3.5 Atkin Theorems in Genus 2 94
3.5.1 Roots of Gmu and the Order of Frobenius 95
3.5.2 The Factorization of Gmu 96
3.5.3 The Characteristic Polynomial of Frobenius 97
3.5.4 Prime Types for Real Multiplication by OF 98
3.5.5 The Parity of the Number of Factors of Gmu 99
3.6 The Case F = Q(sqrt5): Gundlach–Müller Invariants 99
3.7 Experimental Results 101
References 103
4 Locally Recoverable Codes from Algebraic Curves and Surfaces 106
4.1 Introduction 107
4.2 The General Construction 110
4.3 Locally Recoverable Codes from Elliptic Curves 112
4.4 Locally Recoverable Codes from Plane Quartics 115
4.5 Locally Recoverable Codes from Higher Genus Curves 120
4.6 The Availability Problem 124
4.7 Using Algebraic Surfaces in the General Construction 127
4.8 Locally Recoverable Codes from Cubic Surfaces 129
4.9 Locally Recoverable Codes from K3 Surfaces 132
4.10 Locally Recoverable Codes from Surfaces of General Type 134
4.11 Conclusion 135
References 136
5 Variations of the McEliece Cryptosystem 139
5.1 Introduction 140
5.2 Coding-Theoretic Preliminaries 142
5.3 The McEliece Cryptosystem 143
5.4 Variation Based on Weight-2 Masking 148
5.5 A Variation Based on Spatially Coupled MDPC Codes 151
References 156