Abstracts and slides
Daniel Augot (LIX and INRIA Saclay - Île de France):
Connections between decoding Reed-Solomon codes and solving
discrete logarithms over finite fields of small
characteristic.
slides
A connection between the discrete logarithm problem over Fq^h
and the problem of decoding Reed-Solomon codes over Fq has been
proposed and studied by Cheng, Wang at FOCS 2004, essentially in a
theoretical manner to study the hardness of decoding a Reed-Solomon codes
when a large number of errors occurs. We propose to study this
reduction in a reverse direction from a practical point of view : how do
decoding algorithms help in solving the discrete logarithm problem over
finite fields. The first step is to consider a unique decoding
algorithm, like Gao's algorithm, and to adapt it to the discrete logarithm
problem. We have implemented this approach in Magma and NTL and have made
numerical computations. Although the method seems less efficient than
the original Adleman index-calculus method, there are some original
directions that we will discuss.
This is joint work with François Morain (LIX and INRIA).
Peter Beelen (Technical University of Denmark):
Algebraic decoding of algebraic codes.
slides
In this talk I will give an overview of recent
developments in the (list)-decoding of algebraic geometry
codes. A fast way to execute the Guruswami-Sudan list decoder
will be discussed. Also an algebraic reformulation of the
Wu-decoder for Reed Solomon codes will be presented. The
former is joined work with Kristian Brander, while the latter
is joined work with Johan S.R. Nielsen.
Gérard Cohen (École Nationale Supérieure des
Télécommunications):
Combinatorial problems in coding and cryptography.
slides
We survey results and suggest open problems of combinatorial
nature with applications
to coding and cryptography. To mention a few: separation and
traitor-tracing, coset-coding
and biometry, permutation codes and flash memories.
Alexander Meurer (Ruhr Universität Bochum):
Improved Information Set Decoding.
slides
For many code-based cryptographic primitives, the
most efficient attacks are still generic decoding algorithms. The
most prominent class of such generic decoding algorithms is the
class of information set decoding algorithms (ISD for shorthand). In
this talk, we give a brief survey of recent progress in the
design of ISD algorithms. We start with the generalized ISD framework
of Finiasz and Sendrier (Asiacrypt 2009) and relate it to the novel
Ball-Collision technique of Bernstein, Lange and Peters (Crypto 2011).
Finally, we discuss how a neat representation technique (introduced by
Howgrave-Graham and Joux to improve generic algorithms for the subset
sum problem, Eurocrypt 2010) can be used to further improve the
asymptotic performance of ISD algorithms. This technique yields the
currently best asymptotic ISD algorithm as presented by Becker, Joux,
May and Meurer (Eurocrypt 2012).
Ayoub Otmani (Université de Caen):
On the Design of Code-Based Signatures.
slides
One important and challenging issue in modern cryptography is
to propose an efficient digital signature scheme based on
intractability assumptions from coding theory. This is in
contrast to what occurs on the encryption side where
immediately after Diffie and Hellman's suggestion to base
cryptographic primitives on one-way functions, McEliece
proposed an encryption scheme using linear codes. The
difficulty in the design of code-based signatures mainly rests
on the problem of discovering a family of codes for which one
is able to find in polynomial-time the closest vector in the
code for any message. This talk will give a survey of the
existing signature schemes, discuss their security,
efficiency, and will conclude with future directions towards
the design of an efficient scheme.
This is a joint work with Jean-Pierre Tillich.
Ruud Pellikaan (Technische Universiteit Eindhoven):
Error-correcting pairs for a public-key cryptosystem.
slides
Many families of codes have been proposed for public-key
cryptosystems.
The existence of an efficient t-bounded decoding algorithm is
one of the main requirements of such systems.
In this lecture the class of codes with a t-error-correcting
pair is proposed for the McEliece cryptosystem.
All classes of codes for the McEliece cryptosystem that have
been proposed so far have an t-ECP.
The hardness of retrieving a t-ECP for a given code is
considered. Distinguishers of several classes of codes are
given.
This is joint work with Irene Marquez-Corbella.