An important step in the design of secure cryptographic primitives consists in identifying hard algorithmic problems. Despite the fact that several problems have been proposed as a foundation for public-key primitives, those effectively used are essentially classical problems coming from integer factorisation and discrete logarithm. On the other hand, coding theory appeared with the goal to solve the challenging problem of decoding a random linear code. It is widely admitted as a hard problem that has led McEliece in 1978 to propose the first code-based public-key encryption scheme. The key concept is to focus on codes that come up with an efficient decoding algorithm. McEliece recommended the use of binary Goppa codes which proved to be, up to now, a secure choice. This talk will explore the important notion underlying code-based cryptography in order to understand its strengths and weaknesses. We then look at different extensions that lead to a wide range of variants of the McEliece scheme. This will give the opportunity to describe efficient and practical key-recovery cryptanalysis on these schemes, and to show the large diversity in the design of these attacks.
展开▼
