Error detection and correction

Presentation

In our communication-based society, besides confidentiality of the exchanged information, a reliable cerfication of correctness of received data is a crucial proble. Indeed, reading or transmission errors appear regularly, and it is important to add redondancy in sent messages in order to be able to obtain the message in correct form. The code correction theory is the art of introducing such a redondacy with maximal efficiency and correction rate. As such, we introduce

• productivity R<1 equal to the ratio of the number of symbol of each significant word of the message with the total number of symbols of the sent message,
• the ration between the minimal distance between two words of the code and the size of the code.

A code is called excellent when the couple (R_n,d_n), indexed by the size n of the code is larger, for n large enough, to the Gilbert-Varshamov bound. Goppa codes are codes of finite fields that attain that bound, but the introduction of algrebraic geometry was necessary to overtake it.

The lecture will be split into theoretical ingredients needed from the algebraic geometry and the implementation of the codes on computer.

• Algebraic geometry tools : the idea is to be able to construct algebraic curves with many rational points. We introduce algebraic curves, their field of functions, their space and their divisor. The Riemann-Roch theorem will be the high point of the theoretical part of this lecture.
• We will then study Goppa codes, generalized Reed-Solomon codes and Sidelnikov-Shestakov attack, as well as McEliece and Nederreiter cryptosystems.
• We also present the basic, but important tools that are hash funsion, then the concept of electronic signatures and blockchain, that are based on that tool.