Algebraic Geometry for Coding Theory and Cryptography

IPAM, Los Angeles, CA, February 2016

herausgegeben von: Everett W. Howe, Kristin E. Lauter, Judy L. Walker

Verlag: Springer International Publishing

Buchreihe : Association for Women in Mathematics Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Covering topics in algebraic geometry, coding theory, and cryptography, this volume presents interdisciplinary group research completed for the February 2016 conference at the Institute for Pure and Applied Mathematics (IPAM) in cooperation with the Association for Women in Mathematics (AWM). The conference gathered research communities across disciplines to share ideas and problems in their fields and formed small research groups made up of graduate students, postdoctoral researchers, junior faculty, and group leaders who designed and led the projects. Peer reviewed and revised, each of this volume's five papers achieves the conference’s goal of using algebraic geometry to address a problem in either coding theory or cryptography. Proposed variants of the McEliece cryptosystem based on different constructions of codes, constructions of locally recoverable codes from algebraic curves and surfaces, and algebraic approaches to the multicast network coding problem are only some of the topics covered in this volume. Researchers and graduate-level students interested in the interactions between algebraic geometry and both coding theory and cryptography will find this volume valuable.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Representations of the Multicast Network Problem

Abstract

We approach the problem of linear network coding for multicast networks from different perspectives. We introduce the notion of the coding points of a network, which are edges of the network where messages combine and coding occurs. We give an integer linear program that leads to choices of paths through the network that minimize the number of coding points. We introduce the code graph of a network, a simplified directed graph that maintains the information essential to understanding the coding properties of the network. One of the main problems in network coding is to understand when the capacity of a multicast network is achieved with linear network coding over a finite field of size q. We explain how this problem can be interpreted in terms of rational points on certain algebraic varieties.

Sarah E. Anderson, Wael Halbawi, Nathan Kaplan, Hiram H. López, Felice Manganiello, Emina Soljanin, Judy L. Walker

Chapter 2. Hypersurfaces in Weighted Projective Spaces Over Finite Fields with Applications to Coding Theory

Abstract

We consider the question of determining the maximum number of \(\mathbb{F}_{q}\)-rational points that can lie on a hypersurface of a given degree in a weighted projective space over the finite field \(\mathbb{F}_{q}\), or in other words, the maximum number of zeros that a weighted homogeneous polynomial of a given degree can have in the corresponding weighted projective space over \(\mathbb{F}_{q}\). In the case of classical projective spaces, this question has been answered by J.-P. Serre. In the case of weighted projective spaces, we give some conjectures and partial results. Applications to coding theory are included and an appendix providing a brief compendium of results about weighted projective spaces is also included.

Yves Aubry, Wouter Castryck, Sudhir R. Ghorpade, Gilles Lachaud, Michael E. O’Sullivan, Samrith Ram

Chapter 3. Isogenies for Point Counting on Genus Two Hyperelliptic Curves with Maximal Real Multiplication

Abstract

Schoof’s classic algorithm allows point-counting for elliptic curves over finite fields in polynomial time. This algorithm was subsequently improved by Atkin, using factorizations of modular polynomials, and by Elkies, using a theory of explicit isogenies. Moving to Jacobians of genus-2 curves, the current state of the art for point counting is a generalization of Schoof’s algorithm. While we are currently missing the tools we need to generalize Elkies’ methods to genus 2, recently Martindale and Milio have computed analogues of modular polynomials for genus-2 curves whose Jacobians have real multiplication by maximal orders of small discriminant. In this chapter, we prove Atkin-style results for genus-2 Jacobians with real multiplication by maximal orders, with a view to using these new modular polynomials to improve the practicality of point-counting algorithms for these curves.

Sean Ballentine, Aurore Guillevic, Elisa Lorenzo García, Chloe Martindale, Maike Massierer, Benjamin Smith, Jaap Top

Chapter 4. Locally Recoverable Codes from Algebraic Curves and Surfaces

Abstract

A code \(\mathcal{C}\) of length n over a finite field F _q is a subset of the linear space F _q ⁿ. The code is called linear if it forms a linear subspace of F _q ⁿ. The minimum distance d of a code is the minimum pairwise separation between two distinct elements of \(\mathcal{C}\) in the Hamming metric, and if the code \(\mathcal{C}\) is linear, then d is equal to the minimum Hamming weight of a nonzero codeword of \(\mathcal{C}\). We use the notation (n, k, d) to refer to the parameters of a linear k-dimensional code of length n and minimum distance d.

Alexander Barg, Kathryn Haymaker, Everett W. Howe, Gretchen L. Matthews, Anthony Várilly-Alvarado

Chapter 5. Variations of the McEliece Cryptosystem

Abstract

Two variations of the McEliece cryptosystem are presented. The first is based on a relaxation of the column permutation in the classical McEliece scrambling process. This is done in such a way that the Hamming weight of the error, added in the encryption process, can be controlled so that efficient decryption remains possible. The second variation is based on the use of spatially coupled moderate-density parity-check codes as secret codes. These codes are known for their excellent error-correction performance and allow for a relatively low key size in the cryptosystem. For both variants the security with respect to known attacks is discussed.

Jessalyn Bolkema, Heide Gluesing-Luerssen, Christine A. Kelley, Kristin E. Lauter, Beth Malmskog, Joachim Rosenthal

Titel: Algebraic Geometry for Coding Theory and Cryptography
herausgegeben von: Everett W. Howe
Kristin E. Lauter
Judy L. Walker
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-63931-4
Print ISBN: 978-3-319-63930-7
DOI: https://doi.org/10.1007/978-3-319-63931-4