Overview of Code-Based Crypto Assumptions

Explore code-based cryptography assumptions in this 50-minute lecture by Tanja Lange from Technische Universiteit Eindhoven. Delve into topics such as Hamming codes, parity check matrices, and coding theory. Examine code-based encryption, security analysis consequences, and the decoding problem from various perspectives. Learn about the Niederreiter cryptosystem and security notions related to codes. Investigate generic attacks, including brute force and information-set decoding methods like the Lee-Brickell and Stern's attacks. Gain insights into binary Goppa codes and techniques for concealing code structures. This talk, part of the Quantum Cryptanalysis of Post-Quantum Cryptography series at the Simons Institute, provides a comprehensive overview of fundamental concepts in code-based cryptography.

Intro
Hamming code Parity check matrix (n=7,k= 4)
Coding theory
Code-based encryption
Consequence of security analysis
Decoding problem
Different views on decoding
The Niederreiter cryptosystem 11
Note on codes
Security notions and codes
Generic attack: Brute force Given K and s=ke, find e with wt(e) = t.
Generic attack: Information-set decoding, 1962 Prange
Lee-Brickell attack
Stern's attack
Binary Goppa code
How to hide nice code?