Conference Agenda

The focus of this proposal is on coding theory and cryptography, with emphasis on the algebraic aspects of these two research fields. Error-correcting codes are mathematical objects that allow reliable communications over noisy/lossy/adversarial channels. Constructing good codes and designing efficient decoding algorithms for them often reduces to solving algebra problems, such as counting rational points on curves, solving equations, and classifying finite rings and modules. Cryptosystems can be roughly defined as functions that are easy to evaluate, but whose inverse is difficult to compute in practice. These functions are in general constructed using algebraic objects and tools, such as polynomials, algebraic varieties, and groups. The security of the resulting cryptosystem heavily relies on the mathematical properties of these. The sessions we propose feature experts of algebraic methods in coding theory and cryptography. All levels of experience are represented, from junior to very experienced researchers.

It was discovered in 2007 that a quantum channel is asymmetric with respect to errors. Namely, the bit-flip errors are more likely than the phase-flip errors. This motivates the study of asymmetric weight enumerators. We restrict ourselves to quantum stabilizer codes over Frobenius rings, for which we use character theory to prove asymmetric versions of the MacWilliams Identity.

Deployment of high-confidence code-based cryptography is hampered by the large keys associated with Goppa codes.This talk shows how to make use of the structure of encryption in code-based cryptography and how to combine this with tree hashing for confirming the integrity of the public key to use code-based cryptography for tiny, stateless network servers.

In this talk I will present a work in progress on structured linear block codes. The investigation starts from well-known examples and generalizes them to a wide class of codes that we call reproducible codes. These codes have the property that they can be entirely generated from a small number of signature vectors, and consequently admit matrices that can be described in a very compact way. I will show some cryptographic applications of this class of codes and explain why the general framework introduced may pave the way for future developments of code-based cryptography.

The problem of counting points on hyperelliptic curves defined over finite fields has been studied for decades by number theorists and cryptographers. This work studies the case of large characteristic, using methods inspired by Schoof and Pila's algorithms. The cornerstone of this approach is to carefully model the torsion by polynomial systems and solve them using appropriate methods (resultants, geometric resolution, Groebner bases). In practice, the exponential dependency in the genus makes it hard to use these point-counting algorithms in genus larger than 2. Restricting to curves with explicit real multiplication, however, we can drastically reduce the size of our polynomial systems, even in arbitrary genus. In genus 3, the subsequent complexity gain allowed us to achieve a record computation over a 64-bit prime field. Part of this is joint work with P. Gaudry and P.-J. Spaenlehauer.