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.

Ferrers diagram codes play a crucial role in the construction of large subspace codes. They are defined as rank-metric codes where all matrices have support in a given Ferrers diagram. A Singleton-like bound for such codes is known, but to this day it is an open problem whether the bound can be attained for all possible parameter sets. In this talk some constructions leading to optimal Ferrers diagram codes (codes attaining the bound) will be presented. Thereafter, the proportion of optimal Ferrers diagram codes within the set of all codes with the same Ferrers shape and the same dimension will be discussed. We will see that for certain shapes, optimal Ferrers diagram codes are dense (for growing field size) in the space of all codes with the same shape and dimension, while for other shapes the limiting proportion is known to be quite small, but not zero.
The general case is still open.

In [Rudolph 1967], a simple decoding method for linear codes based on majority decision using combinatorial designs is presented. This method is called "one-step majority logic decoding" and it's attraction lies in the easy realization in hardware. It requires that the dual code has to contain the blocks of a t-design as codewords. Ever since then, people studied the linear codes generated by the blocks of t-designs. For a good code it is desirable that the rank of the block-point incidence matrix of the design is small over some finite field. The famous Hamada conjecture states that so called "classical or geometric designs" which consist of the set of all k-flats in PG(v,q) or AG(v,q), minimize the p-rank for a prime power q. The codes generated by these designs are called Euclidean Geometry (EG) codes and Projective Geometry (PG) codes. In case p = q = 2, the codes are the well known Reed-Muller codes. We report a few observations on the codes generated by "subspace designs" - also known as q-analogs of designs. The blocks of these designs generate essentially the same linear codes as the geometric designs but with sometimes much improved complexity of the one-step majority logic decoder. This may be of interest when implementing error correction with nano-scale technologies. Further, we will look at Chen's two-step majority logic decoder and the connection to rank metric codes.

I will discuss some recent joint work with Christophe Petit and Daniela Mueller, in which we give upper bounds for the complexity of computing a Groebner basis of the polynomial system associated to the HFE (Hidden Field Equations) cryptosystem.

The present-day method for setting up a secure communication channel over the internet makes use of the Diffie-Hellman key exchange protocol, which is based on exponentiation in groups. However its security breaks down if an adversary would be given access to a large universal quantum computer. It is unclear whether such a device will see the light of day in the near future, but the threat alone is enough reason to make the transition to so-called "post-quantum key exchange", which is an actively ongoing process. One attractive line of thought is to replace exponentiation in groups by other commutative group actions. Currently, the only working such proposal goes back to Couveignes and uses the CM torsor, which is an action of the class group of an imaginary quadratic ring on a certain set of elliptic curves. I will explain this idea and report on a tweak called CSIDH, which was recently developed in collaboration with Lange, Martindale, Panny and Renes and leads to a considerable speed-up, from minutes to milliseconds.