CBC 2012
9–11 May 2012
Lyngby, Denmark
Code-based Cryptography Workshop
Code-based Cryptography Workshop 2012

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.

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.

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.

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.

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.

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.

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.

Picture: Wiki Media http://www.imagefree.org/