Description
Reed-Solomon codes have optimal minimum distance and we know efficient encoding and decoding algorithms of quasi-linear complexity in the length. Their main drawback is that their lengths are bounded by the size of the alphabet, i.e. the field over which they are defined. Algebraic geometry codes are a generalisation allowing longer codes on the same alphabet, and one of the most interesting sub-families of these are the Hermitian codes. The price for the greater length is more complicated computations: so far, no decoding algorithm with sub-quadratic complexity in the length of the code was known. We show how to achieve this by building the decoder around the problem of finding a short vector in an F[x]-module, and performing this step using state-of-the-art algorithms from computer algebra. This approach follows recent trends in decoding of Reed-Solomon codes. Furthermore, our decoder is a "Power decoder", probabilistically capable of decoding errors beyond half-the-minimum distance for low-rate codes.
Next sessions
-
Schéma de signature à clé publique : Frobénius-UOV
Speaker : Gilles Macario-Rat - Orange
L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…] -
Yoyo tricks with a BEANIE
Speaker : Xavier Bonnetain - Inria
TBD-
Cryptography
-
Symmetrical primitive
-