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 Fp
slides
We propose a new, efficient decoding algorithm for square-free
(irreducible or otherwise) Goppa codes over Fp
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 = 2r/3
syndromes, it reduces (up to a non negligible polynomial factor)
the attack cost from 2r/2 (classical birthday
attack) to 2r/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.