Code-based Cryptography

Abstract and slidess

Henk C.A. van Tilborg (Technische Universiteit Eindhoven):
Error-correcting codes and the McEliece cryptosystem in a nutshell
slides

This presentation consists of five parts, each being an elementary introduction:

• error-correcting codes,
• quasi-cyclic codes,
• cyclic codes,
• the McEliece cryptosystem,
• burst-correcting array codes (demo).

It is intended for cryptographers, being unfamiliar with the theory of error-correcting codes.

Richard Lindner (Technische Universität Darmstadt):
Decoding square-free Goppa codes over F_p
slides

We propose a new, efficient decoding algorithm for square-free (irreducible or otherwise) Goppa codes over F_p for any prime p. If the code in question has degree t and its average code distance is at least (4/p)t + 1, the proposed decoder can uniquely correct up to (2/p)t errors with high probability. The correction capability is higher if the distribution of error magnitudes is not uniform, approaching or reaching t errors when any particular error value occurs much more often than others or exclusively. This makes the method interesting for (semantically secure) cryptosystems based on the decoding problem for permuted and punctured Goppa codes.

Nicolas Sendrier (INRIA Paris-Rocquencourt):
Decoding One Out of Many
slides

The security of code-based cryptosystems relies heavily on the hardness of the computational syndrome decoding problem CSD(H, s, w): given a parity check matrix H, a weight w and a syndrome s, find w columns of H adding to s.
Given H and w, solving CSD for one out of N > 1 syndromes cannot be harder than solving it for a single instance. We investigate the algorithmic gain for both Information Set Decoding (ISD) and the Generalized Birthday Algorithm (GBA). We prove that a gain around √N can be achieved in general.
Applied to GBA this leads to the (unpublished) Bleichenbacher attack efficient against the CFS digital signature scheme. For syndromes of r bits, and considering N = 2^r/3 syndromes, it reduces (up to a non negligible polynomial factor) the attack cost from 2^r/2 (classical birthday attack) to 2^r/3 (GBA with four lists).
Applied to ISD, it relates to the work of Johansson and Jönsson (IEEE-IT 2002) which we revisit completely. We give a more precise description of the algorithm and an estimation of the gain. Unlike GBA the improvement do not fully apply for large values of N.

Daniel J. Bernstein (University of Illinois at Chicago):
Decoding random codes: asymptotics, benchmarks, challenges, and implementations
slides

The top threats against the McEliece cryptosystem have always been generic decoding algorithms that decode random linear codes. There is a long history of clever improvements in these algorithms, but there is also an unpleasant history of progress being obscured by excessively optimistic algorithm analyses, excessively pessimistic algorithm analyses, and nonsensical machine models. I will discuss some recent advances in generic single-target decoding algorithms, and some ways that continued progress can be recognized and encouraged, inspired by good and bad examples from other areas of algorithm design.

Stefan Heyse (Ruhr-Universität Bochum):
Implementational aspects of code-based cryptography for embedded systems
slides

The presentation gives an short introduction into the McEliece and Niederreiter scheme from an engineer's point of view. Afterwards the different steps of the encryption and decryption will be discussed and optimizations and time-memory-tradeoffs will be shown. The focus lies on embedded systems like micro controllers and small FPGAs.

Jean-Pierre Tillich (INRIA Paris-Rocquencourt):
A Distinguisher for High Rate McEliece Cryptosystems (joint work with J.C. Faugère, V. Gauthier Umana, A. Otmani, L. Perret)
slides

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it was a rather classical belief to consider it as a hard computational problem. Its assumed hardness was used in cryptography to prove the security of the McEliece's cryptosystem. We first recall in this talk how this problem arises in the cryptographic context. Then we present a polynomial time distinguisher for alternant and Goppa codes of high rate over any field. This applies to the Goppa codes used in the CFS signature scheme and also to some realistic secure parameters of McEliece.
The key ingredient is to consider the dimension of the solution space of a linearized system coming from a polynomial system which is itself derived from the public key. It turns out that experimentally this dimension depends on the type of code. We provide explicit formulas derived from extensive experimentations for the value of the dimension for ``generic" random, alternant, and Goppa code over any alphabet. Eventually, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes.