2
$\begingroup$

At the time of this writing, there are 3 sources for parameters for the McEliece public-key cryptosystem out there.

The first paper is the original McEliece paper ("A Public-Key Cryptosystem based on Algebraic Coding Theory" by McEliece), which only specifies $(n,k,t)=(1024,524,50)$, which is known to be broken as of today with an effort of around $2^{60}$ in "Attacking and defending the McEliece cryptosystem" by Bernstein, Lange and Peters (2008).

The next source is the exact same paper that broke McEliece, by Bernstein, Lange and Peters. They propose $(1632,1269,33)$ (80-bit), $(2960,2288,56)$ (128-bit) and $(6624,5129,118)$ (256-bit) as $(n,k,t)$.

"Selecting Parameters for Secure McEliece-based Cryptosystems" by Niebuhr , Meziani, Bulygin, Buchmann, as of 2010, proposes new sets of parameters, based on Lenstra-Verheul-Style modelling. The authors also mention the above paper, but only for their attack. They propose $(1702,1219,45)$ (80-bits) and (computed by myself with same parameters) $(3807,2891,77)$ (128-bits).

So you may note that there's some difference between those recommended parameters. The difference between the public keys of the two 80-bit sets is 230,000 bits, so here comes my question:

Why is there this difference in the parameters and which ones should rather be used?


$\endgroup$
  • $\begingroup$ I'm not sure if this is "primarily opinion based". I hope the question is objective enough, although "use the more conservative" may be a valid answer in case, "it's all about trust in the authors and their analysis". $\endgroup$ – SEJPM Jul 5 '15 at 20:11
  • $\begingroup$ It might be "what are the best known-results"; that'd certainly be an on-topic question. $\endgroup$ – poncho Jul 5 '15 at 20:28
  • $\begingroup$ The paper Daniel J. Bernstein, Tung Chou, and Peter Schwabe: McBits: fast constant-time code-based cryptography lists a bunch of parameterizations as well. Since the paper is from 2013, the security estimates should take the attacks you mentioned into account. $\endgroup$ – CodesInChaos Jul 5 '15 at 20:51
  • $\begingroup$ @CodesInChaos, the security levels they mention in the table at page 5 are a result of the 2009 by Peters, which uses Bernstein et al's value for 128-bits. Apparently the number from the McBits paper just check strength against the new attack by Peters, which is only slightly better than Bernstein et al's previous attack, so these should basically be the same numbers. $\endgroup$ – SEJPM Jul 5 '15 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.