You are looking at a specific version 20140526:100737 of this paper. See the latest version.

Paper 2014/360

McEliece in the world of Escher

Danilo Gligoroski and Simona Samardjiska and Håkon Jacobsen and Sergey Bezzateev

Abstract

We 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 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. The security analysis of our scheme have two main parts: 1. An extensive list of 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. Based on this security analysis we suggest some concrete parameters for the security levels in the range of $2^{80} - 2^{128}$. An additional feature of the decryption process is that it admits massive and trivial parallelization that could potentially make our scheme in hardware as fast as the symmetric crypto primitives.

Note: Added one new Subsection 5.4 A Cheap Distinguishing Attack

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Public Key CryptographyMcEliece PKCError Correcting CodesList Decoding
Contact author(s)
danilog @ item ntnu no
simonas @ item ntnu no
hakoja @ item ntnu no
bsv @ aanet ru
History
2014-09-24: last of 4 revisions
2014-05-23: received
See all versions
Short URL
https://ia.cr/2014/360
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.