Reed-Solomon codes are a well-known technique to represent data in the form of vectors, such that the data can be recovered even if some vector coordinates are corrupted. These codes have many properties. They allow reconstructability of coordinates which have been erased. They ensure the privacy of the data against an adversary learning many coordinates. They are compatible with the addition and the multiplication of data. Nevertheless, they suffer from some limitations. For instance, the storage size of vector coordinates grows logarithmically with the number of coordinates. So-called algebraic geometry (AG) codes are a generalization of Reed-Solomon codes that enjoys the same properties, while being free of these limitations. Therefore, the use of AG codes provides complexity gains, and turns out to be useful in several applications such as distributed storage, distributed computation on secrets, and zero-knowledge proofs.
Algebraic geometry codes are constructed by evaluating spaces of functions, called Riemann-Roch spaces, at the rational points on a curve. It follows that the computation of these spaces is crucial for the implementation of AG codes. In this talk, I will present a recent work joint with S. Abelard, A. Couvreur and G. Lecerf on the effective computation of bases of Riemann-Roch spaces of curves. I will discuss the ideas behind our algorithm, including in particular Brill-Noether theory.
The curves used in the construction of AG codes were for the most part limited to those for which the Riemann-Roch bases were already known. This new work and the ones that will follow will allow the construction of AG codes from more general curves.