Algebraic Geometry for Coding Theory and Cryptography

February 22 - 26, 2016

Group Topics

Codes with network-constrained generator matrices

Co-leaders: Emina Soljanin (Rutgers University) and Judy Walker (University of Nebraska, Lincoln).
Group members: Sarah Anderson (University of St. Thomas), Wael Halbawi (California Institute of Technology), Nathan Kaplan (University of California, Irvine), Hiram López Valdez (Center for Research and Advanced Studies of NPI), and Felice Manganiello (Clemson University).

In networks that implement linear network coding, edges carry linear combinations of their parent node inputs.  In turn, this implies that edges carry linear combinations of the source symbols.  The network coding multicast problem asks: How should nodes combine their inputs to ensure that the edges observed by a receiver carry independent combinations of the source symbols?  Moreover, what is the minimum field size necessary to realize combinations with this property?  This problem is completely solved in the case of two sources and arbitrarily many receivers, but in no other cases.  It is strongly related to problems in other areas of coding theory as well, such as the classical problem of finding MDS generator matrices over small fields with zeros in certain prescribed entries, and the more recent problem of locality in coding for distributed storage.

Isogenies for genus-2 curves

Co-leaders: Benjamin Smith (Ecole Polytechnique, Lix / INRIA) and Jaap Top (University of Groningen).
Group members: Sean Ballentine (University of Maryland), Aurore Guillevic (INRIA), Elisa Lorenzo-García (Leiden University), Chloe Martindale (Leiden University), and Maike Massierer (University of New South Wales).

Modular polynomials (which parametrize elliptic curve isogenies,  in a sense) are a key ingredient in the Schoof–Elkies–Atkin algorithm, which is the most efficient point counting algorithm for elliptic curves over finite fields of large characteristic. As such, they are crucial in the construction of secure elliptic curve cryptosystems.  We are now starting to see the first calculations of modular polynomial ideals for genus 2 Jacobians. In this project, we will look at algorithmic applications of these polynomials to genus 2 point counting, in the hope of improving the efficiency of constructing secure hyperelliptic cryptosytems.

Code-based crypto

Co-leaders: Kristin Lauter (Microsoft Research) and Joachim Rosenthal (University of Zurich).
Group members: Jessalyn Bolkema (University of Nebraska, Lincoln), Heide Gluesing-Luerssen (University of Kentucky), Christine Kelley (University of Nebraska, Lincoln), and Beth Malmskog (Villanova University).

Code-based crypto had its beginning in a 1978 three page paper by Robert McEliece where he showed how the hardness of decoding a general linear code up to half the minimum distance can be used as the basis for a public key crypto system. At the time the system was not implemented in practice as the required public key was relatively large. With the realization that a quantum computer would make many practically used systems obsolete, coding based systems became an important research subject in the area of post-quantum cryptography.

Both the NSA and NIST have encouraged during the last months the research community to come up with new post-quantum crypto systems and investigate the suitability of the existing ones. The working group will study several of the recently proposed variants  of coding based systems.

Trace-zero subgroups

Co-leaders: Elisa Gorla (University of Neuchatel) and Christophe Ritzenthaler (Université de Rennes 1).
Group members: Alp Bassa (Bogaziçi University), Nils Bruin (Simon Fraser University), Daniel Katz (California State University, Northridge), and Michela Mazzoli (Alpen-Adria-Universität Klagenfurt).

Given an elliptic curve defined over a finite field F and a finite extension K of prime degree n, one can define the trace zero subgroup of E(K) as the kernel of the trace endomorphism from E(K) to E(F), which sends each point P to the sum of its Frobenius conjugates. A similar definition can be given also for hyperelliptic curves and/or arbitrary n. Trace zero subgroups of elliptic and hyperelliptic curves are of interest within pairing based cryptography. In this working group, we will discuss constructions of pairing friendly trace zero subgroups.

Codes with locality constraints

Co-leaders: Alexander Barg (University of Maryland) and Gretchen Matthews (Clemson University).
Group members: Kathryn Haymaker (Villanova University), Everett Howe (Center for Communications Research, La Jolla), and Anthony Varilly-Alvarado (Rice University).

An (n, k) code with locality r encodes k data symbols into n symbols in such a way that the value of any symbol of the encoding can be found by accessing at most r other stored symbols. If for every symbol there are t such groups of r symbols, the code is said to have locality r and availability t. Recently it has been shown that codes with locality and availability can be constructed as evaluation codes on algebraic curves. The goal of this project is to examine properties of these code families and to construct new codes by a detailed study of properties of algebraic curves.

Number of points of algebraic sets

Co-leaders: Sudhir Ghorpade (IIT Bombay) and Gilles Lachaud (Institut de Mathématiques de Luminy).
Group members: Yves Aubry (Université de Toulon), Wouter Castryck (Universiteit Gent) , Michael O’Sullivan (San Diego State University), and Samrith Ram (IIS Bangalore).

The topic concerns determination of the maximum number of points with coordinates in a finite field F that a given (affine or projective) algebraic set defined by polynomial equations over F or its algebraic closure can have. There have been some exciting recent developments here owing partly to the complete or partial settlement of conjectures of Lachaud and of Tsfasman-Boguslavsky that were open for about two decades. There are also direct applications to coding theory by way of the determination of generalized Hamming weights of certain classes of linear codes, and to cryptography by way of authentication systems defined using finite geometry. We will review the classical results and several of the recent developments in this area, and discuss a number of problems that still remain open.