Distinguisher-based attacks on public key cryptosystems using Generalised Reed-Solomon codes
Vortrag von Dr. Alain Couvreur
Datum: 22.04.13 Zeit: 11.00 - 12.00 Raum:
Given an error-correcting code C, we denote by C^2 the "square of C", which is the code generated by words of the form c*c', where c,c' are codewords of C and * denotes the coordinatewise product. Many codes obtained by evaluation of algebraic functions such that Reed-Solomon codes, Reed-Muller codes, algebraic geometry codes, and so on, meet the property that the dimension of their square is smaller than that of a random code with the same dimension. This feature of algebraic codes has been used by Faugere et al to distinguish some alternant codes from random ones in [FGO+11].On the other hand, after the work of Sidelnikov and Shestakov [SS92] which proved that Generalised Reed-Solomon (GRS) codes were unsecure for McEliece's Cryptosystem, several attempts to repair this scheme have been proposed in order to reintroduce GRS codes in systems which resist to Sidelnikov-Shestakov's attack.
In this talk, after introducing some basic notions on GRS codes and their squares and on McEliece's cryptosystem, I'll describe distinguisher-based attacks, i.e. attacks involving square of codes which break recent cryptosystems using GRS codes.
This is a joint work with Philippe Gaborit, Valerie Gautier, Ayoub Otmani and Jean-Pierre Tillich. It will be presented at the conference WCC 2013.
References:
[FGO+11] J.-C. Faugère, V. Gautier, A. Otmani, L. Perret and J.-P. Tillich. A distinguisher for high rate McEliece cryptosystems. Proceedings of the Informations Theory Workshop, 282--286, Paraty Brazil, 2011.
[SS92] V.M. Sidelnikov and S.O. Shestakov. On the insecurity of cryptosystems based on generalised Reed-Solomon codes. Discrete mathematics and Applications, 1(4):439--444, 1992.