The security analysis of our scheme have four 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; 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; 4. We interpret our scheme as multivariate quadratic system and discuss difficulties of solving that system using algebraic approaches such as Gr\"{o}bner bases.
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.
Category / Keywords: Public Key, Cryptography, McEliece PKC, Error Correcting Codes, List Decoding Date: received 22 May 2014, last revised 24 Sep 2014 Contact author: danilog at item ntnu no, simonas@item ntnu no, hakoja@item ntnu no, bsv@aanet ru Available format(s): PDF | BibTeX Citation Note: The same material as previously, but restructured in a form of monograph. The cheap distinguisher attack section is updated to cover signatures. Version: 20140924:111811 (All versions of this report) Short URL: ia.cr/2014/360