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ö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 at item ntnu no, hakoja at item ntnu no, bsv at 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