# PolSys seminar

# A new code based public key scheme based on list decoding

09/19/2014

Speaker(s) : Danilo Gligoroski (Dept of Telematics, Norwegian University of Science and Technology (NTNU), Norwa

I will present a new family of linear binary codes of length $n$ and dimension $k$ accompanied with a fast list decoding algorithm that can correct up to $frac{n}{2}$ errors in a bounded channel with an error density $rho$. The decisional problem of decoding random codes using these generalized error sets is NP-complete. Next, I will show how can we use the properties of these codes to design both an encryption scheme and a signature scheme. Although in the open literature there have been several proposals how to produce digital signatures from the McEliece public key scheme, as far as we know, this is the first public key scheme based on codes where signatures are produced in a straightforward manner from the decryption procedure of the scheme. I will briefly cover three parts of the security analysis of our scheme: 1. Attacks using the Information Set Decoding techniques adopted for our codes; 2. An analysis of the cost of a distinguishing attack based on rank attacks on the generator matrix of the code or on its dual code; 3. An analysis of the cost of cheap distinguishing attacks on the generator matrix of the code or on its dual code that have expensive list-decoding properties. Then I will explain the connection with Multivariate Quadratic systems and possible analysis of our scheme with Groebner bases. Based on the whole security analysis we suggest some concrete parameters for the security levels in the range of $2^{80} - 2^{128}$.

Elias.Tsigaridas (at) nulllip6.fr