Vidéo pédagogique
Notice
Sous-titrage
Anglais
Langue :
Anglais
Crédits
Irene Marquez-Corbella (Intervention), Nicolas Sendrier (Intervention), Matthieu Finiasz (Intervention)
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
DOI : 10.60527/qth2-xc64
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 5.2. The Courtois-Finiasz-Sendrier (CFS) Construction , in 5: Other cryptographic constructions relying on coding theory. [Vidéo]. Canal-U. https://doi.org/10.60527/qth2-xc64. (Consultée le 17 juillet 2025)
RF-Inria-logo-RVB
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

5.2. The Courtois-Finiasz-Sendrier (CFS) Construction

Réalisation : 5 mai 2015 - Mise en ligne : 21 février 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

In this session, I amgoing to present the Courtois-Finiasz-SendrierConstruction of a code-based digital signature. In the previous session,we have seen that it is impossible to hash adocument into decodable syndromes. But it is possible to hashonto the space of all syndromes. The document is not always decodable. And we are going to see twotechniques to work around this problem. The first technique is toadd a counter to the document. This way, we hash both thecounter and the document and obtain a hash which is tied toboth the document and the counter. We increment the counter untila decodable syndrome is found. The signature is thedecoding of the syndrome but also contains the counter which isrequired for the verification. The second method is toperform complete decoding. Complete decoding is theidea of being able to decode any syndrome in the space. Andfor this, we need to modify the decoding algorithm.The idea is to add some exhaustive search tothe decoding algorithm. For example, if we want todecode one more error in the decoding capacity of thecode, we simply do an exhaustive search on one position. Add this errorto the syndrome and try to decode it. We can do the same with twoerrors or up to δ errors by doing a search on δ positions. This way, we can reach thecovering radius, which is the number of errors we need tocorrect to decode any element in the syndrome space. Both techniques are expensive. Decodable syndromes musthave high enough density in the space of all syndromes. Thecovering radius and decoding capacity must beclose to one another. If they are too distant,it will be too expensive to perform complete decoding. What are the requirements forcode-based digital signatures? As for a public-keyencryption, we need to be able to keep the decoding algorithm secret. So, we need codes where it ispossible to hide the structure efficiently. Binary Goppa codes areone of very few candidates. And so, we will use thisin the construction, exactly like in the original McEliece scheme. Then, to have someefficient signature schemes, we need the highest possibledensity of decodable syndromes.

Intervention
Thème
Disciplines :
Documentation
Support de présentation au format PDF

Dans la même collection

Voir tout

Avec les mêmes intervenants et intervenantes

Sur le même thème