Public key size?

[iheartlasers]

First of all, let me say that codecrypt is great and I couldn't be more impressed. Thank you for creating it!

I noticed that the public keys generated (even the largest with the "enc-strongest" option) seem to be much smaller in size than I thought they would be for McEliece. For example, Wiki says at https://en.wikipedia.org/wiki/McEliece_cryptosystem that the keys would be around 512kbit. Could anyone please help me see what I'm misunderstanding?

[cfcs]

You're reading about the wrong McElice variant :-)

Codecrypt is the author's bachelor project, an implementation of a variant of the original McElice system (the original being subject to some flaws). Bachelor thesis: http://e-x-a.org/codecrypt/mk_bachelor.pdf

More reading on the crypto: https://eprint.iacr.org/2011/179.pdf https://eprint.iacr.org/2009/187.pdf

Website: http://e-x-a.org/codecrypt/

[iheartlasers]

Ah, thank you.

I'm trying my best to understand that and the paper written by discussed here https://en.wikipedia.org/wiki/McEliece_cryptosystem#Information_set_decoding, but can't say I'm really getting it yet. Are the McEliece parameters used by codecrypt susceptible to the attack that takes about 2^60.55, as discussed in that link?

I was guessing the answer to that question is "no", based upon the "ALGORITHMS" section of the man page at http://e-x-a.org/codecrypt/ccr.1.html that suggests as of 2013 the work factor is much higher, while that attack is from several years prior to 2013.

[exaexa]

Hello,

thanks for your interest in codecrypt and well, sorry for late answer. :D

"Original" McEliece approach is extremely useless for practice - not only the keys get much larger than it was suggested in original paper, but it has all kinds of other drawbacks, notably big matrix inversion in key generation (that takes "forever", much longer than hash keys :] ) and the key size, which is around O(n^3) where n is "bit security".

We use Quasi-Dyadic McEliece variant with Fujisaki-Okamoto padding. All is described in the "papers" here:

https://github.com/exaexa/codecrypt/raw/master/doc/papers/187.pdf -- trapdoor

https://github.com/exaexa/codecrypt/raw/master/doc/papers/Gerhard_Hoffmann.bachelor.pdf --implementation details for the trapdoor (notably the hadamard transform multiplication trick is groovy)

https://github.com/exaexa/codecrypt/raw/master/doc/papers/fujisaki-okamoto.pdf --padding (applicable to all other "modern McEliece" variants that don't use scramble matrix for avoding most of key size bloat)

There's also some other undocumented nontrivial stuff in codecrypt (blockwise quasidyadic gauss-jordan elimination is cool as well) but not that much, there's more focus on getting things together and working.

Rough complexity guesses are taken in the QD paper, and I have increased them by some small margin just for safety. Not sure whether there hasn't been some improvement in decoding algorithms lately, but I guess that using 2^256 variants is still more than safe.

-mk