Informations pratiques

Description de la ressource

Résumé

In this session, I am going to present the Courtois-Finiasz-Sendrier Construction of a code-based digital signature. In the previous session, we have seen that it is impossible to hash a document into decodable syndromes. But it is possible to hash onto the space of all syndromes. The document is not always decodable. And we are going to see two techniques to work around this problem. The first technique is to add a counter to the document. This way, we hash both the counter and the document and obtain a hash which is tied to both the document and the counter. We increment the counter until a decodable syndrome is found. The signature is the decoding of the syndrome but also contains the counter which is required for the verification. The second method is to perform complete decoding. Complete decoding is the idea of being able to decode any syndrome in the space. And for this, we need to modify the decoding algorithm. The idea is to add some exhaustive search to the decoding algorithm. For example, if we want to decode one more error in the decoding capacity of the code, we simply do an exhaustive search on one position. Add this error to the syndrome and try to decode it. We can do the same with two errors or up to ? errors by doing a search on ? positions. This way, we can reach the covering radius, which is the number of errors we need to correct to decode any element in the syndrome space. Both techniques are expensive. Decodable syndromes must have high enough density in the space of all syndromes. The covering radius and decoding capacity must be close to one another. If they are too distant, it will be too expensive to perform complete decoding. What are the requirements for code-based digital signatures? As for a public-key encryption, we need to be able to keep the decoding algorithm secret. So, we need codes where it is possible to hide the structure efficiently. Binary Goppa codes are one of very few candidates. And so, we will use this in the construction, exactly like in the original McEliece scheme. Then, to have some efficient signature schemes, we need the highest possible density of decodable syndromes.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Domaine(s)

• Cette ressource fait partie de
  • 5: Other cryptographic constructions relying on coding theory