Code-Based Cryptography

Description

We all use cryptography in our daily lives. The security of the most popular Public-Key Cryptosystems
are based either on the hardness of factoring or the presumed
intractability of the discrete logarithm problem. Advances on these
problems or the construction of large quantum computers would
dramatically change the landscape: Code-Based Cryptography is a powerful and promising alternative.

The objective of this course is to present the state of the art of these cryptosystems. This MOOC covers the essentials that you should know about this hot topic in Cryptography and Coding Theory: the security-reduction proofs, the possible attacks, several proposals to reduce the key-size, etc.

TARGETED AUDIENCE

This course is intended for undergraduate and Master’s degree students in mathematics or computer science.

Postgraduate students and researchers from the disciplines of computer algebra, coding theory and cryptography can also benefit from this course.

More widely, mathematicians, physicists or engineers interested in information and communication technologies and every person who wants to know more about cryptography, coding theory or code-based cryptography can be interested in this course.

PRE-REQUISITES

Knowledge about linear algebra, finite field and complexity theory is required.

COURSE SYLLABUS

Click on a link below to access the videos of the course.

Part 1: Error-Correcting Codes and Cryptography

Part 2: McEliece Cryptosystem

Part 3: Message Attacks (ISD)

Part 4: Key Attacks

Part 5: Other cryptographic constructions relying on coding theory

The material of this course come from a MOOC delivered on France Université Numérique : https://www.fun-mooc.fr/courses/inria/41006S02/session02/about

  

Vidéo pédagogique

5.1. Code-Based Digital Signatures
Collection
7 vidéos
5: Other cryptographic constructions relying on coding theory
  • MARQUEZ-CORBELLA Irene
  • SENDRIER Nicolas
  • FINIASZ Matthieu
Table of contents
5.1. The Courtois-Finiasz-Sendrier (CFS) Construction
5.2. Attacks against the CFS Scheme
5.3. Parallel-CFS
5.4. Stern’s Zero-Knowledge Identification Scheme
5.5. An Efficient Provably Secure One-Way Function
5.6. The Fast Syndrome-Based (FSB) Hash Function
05.05.2015
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3
  • document 1 document 2 document 3
4.1. Introduction
Collection
9 vidéos
4: Key Attacks
  • MARQUEZ-CORBELLA Irene
  • SENDRIER Nicolas
  • FINIASZ Matthieu
Table of contents 4.1.
Introduction
4.2.
Support Splitting Algorithm   
4.3.
Distinguisher for GRS codes   
4.4. Attack
against subcodes of GRS codes          
4.5.
Error-Correcting Pairs            
4.6. Attack
against GRS codes         4.7. Attack
against Reed-Muller codes     
4.8. Attack
against Algebraic Geometry codes    
4.9. Goppa
codes still resist            
05.05.2015
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3
  • document 1 document 2 document 3
3.1. From Generic Decoding to Syndrome Decoding
Collection
10 vidéos
3: Message Attacks (ISD)
  • MARQUEZ-CORBELLA Irene
  • SENDRIER Nicolas
  • FINIASZ Matthieu
Table of contents 3.1. From
Generic Decoding to Syndrome Decoding
3.2.
Combinatorial Solutions: Exhaustive Search and Birthday Decoding     
3.3.
Information Set Decoding: the Power of Linear Algebra   
3.4.
Complexity Analysis    
3.5. Lee
and Brickell Algorithm     3.6.
Stern/Dumer Algorithm         3.7. May,
Meurer, and Thomae Algorithm          
3.8.
Becker, Joux, May, and Meurer Algorithm   
3.9.
Generalized Birthday Algorithm for Decoding        
3.10.
Decoding One Out of Many
05.05.2015
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3
  • document 1 document 2 document 3
2.1. Formal Definition
Collection
9 vidéos
2: McEliece Cryptosystem
  • MARQUEZ-CORBELLA Irene
  • SENDRIER Nicolas
  • FINIASZ Matthieu
Tables of contents 2.1. Formal
Definition
2.2.
Security-Reduction Proof       
2.3.
McEliece Assumptions
2.4.
Notions of Security      
2.5.
Critical Attacks - Semantic Secure Conversions      
2.6.
Reducing the Key Size
2.7.
Reducing the Key Size - LDPC codes
2.8.
Reducing the Key Size - MDPC codes           
2.9.
Implementation
05.05.2015
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3
  • document 1 document 2 document 3
1.1. Introduction I - Cryptography
Collection
9 vidéos
1: Error-Correcting Codes and Cryptography
  • MARQUEZ-CORBELLA Irene
  • SENDRIER Nicolas
  • FINIASZ Matthieu
Table of contents 1.1.
Introduction I - Cryptography
1.2.
Introduction II - Coding Theory        
1.3.
Encoding (Linear Transformation)   
1.4. Parity
Checking            
1.5. Error
Correcting Capacity      
1.6.
Decoding (A Difficult Problem)         
1.7.
Reed-Solomon Codes   
1.8. Goppa
Codes     
1.9.
McEliece Cryptosystem
05.05.2015
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3
  • document 1 document 2 document 3