[tahoe-dev] Hash based Signatures for Tahoe LAFS

[Samuel Neves]

> Hi there Julian! I was just looking at this new stackexchange site for
> crypto, and someone (named Anthony "ninefingers" Vennard) had asked
> why McEliece wasn't more popular, since it is post-quantum, and they
> wondered if it was because of the large public keys. Below is my
> reply.

To reply to the "why isn't McEliece more popular" question, well it's a
long story. Back in the 70s, when McEliece was proposed, storage was
much more precious that it is today. McEliece's original parameters (now
insecure) required the storage of a 32 KB key. In the 80s and early 90s,
when public-key cryptography was beginning to get adopted, memory was
scarce, and RSA had much smaller keys, despite slower encryption. Add in
the fact that McEliece had no good way to produce digital signatures,
and it quickly fell into obscurity.

So why isn't it used now? No one cares about a few kilobytes anymore,
computers are (too) fast, and quantum computers could kill all the
abelian hidden subgroup cryptosystems. There are even McEliece-style
(CFS) digital signatures! Well, that's too little too late; elliptic
curves are able to provide us with a plethora of cryptographic
primitives that few mathematical structures can even begin to match,
they are very fast, and they have strong support from large
organizations. Plus, progress on quantum computer engineering seems to
be painfully slow, so there is not much concern about Shor's algorithm
in practice.

What about McEliece for "100-year cryptography"? Well, we need
signatures. The CFS signature scheme solves the inability of producing
signatures (i.e., finding message representatives that are t bits away
from some valid codeword) by changing drastically the recommended
parameters of the Goppa code used (n=2^{14,15,16,17}, t={8,9,10}),
raising once again the key size to ~1 MB.

The main drawback is, however, signature time: CFS requires an average
of factorial(t) signature attempts (read: applications of Patterson's
decoding) to find a signature. Once we are trying to protect against
actual quantum attacks, keys quadruple in size [2], thus increasing the
runtime of Patterson's algorithm (quadratic in the size of the code).
The original CFS paper reported times of over a minute to sign a message
on a Pentium 4; today it will probably be much better, but it's still
quite unacceptable performance-wise.

Regards,
Samuel Neves

[1] "How to achieve a McEliece-based Digital Signature Scheme."
http://eprint.iacr.org/2001/010
[2] "Grover vs McEliece." http://cr.yp.to/codes/grovercode-20091123.pdf