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.
Prochains exposés
-
Séminaire C2 à INRIA Paris
Emmanuel Thomé et Pierrick Gaudry Rachelle Heim Boissier Épiphane Nouetowa Dung Bui Plus d'infos sur https://seminaire-c2.inria.fr/ -
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Orateur : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-