Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm studying McEliece and Multivariate Public Key cryptographic systems. The main problem here is the huge key size.

Is there any restriction in using lossless compression algorithms to fix this problem?

share|improve this question
I suppose that there won't be much gains by such algorithms. – Paŭlo Ebermann Oct 11 '13 at 18:04
For storing the private key, you can store the seed that you used to get the key instead. You should be able to fit a pretty good seed in 24 bytes. – Nick ODell Oct 11 '13 at 20:32
Instead of storing public key, possibly you could store (strong enough) hash of public key and some address where to get get the actual key data. The large public key must be available somewhere. For instance, maybe the owner of the private key (see suggestion from Nick Odell above) will provide public key. Or maybe some TTP has it. – user4982 Oct 11 '13 at 21:48

The problem is that the key is essentially random data and thus cannot be meaningfully compressed. Several variations of the McEliece cryptosystem have tried modifying it to produce public keys with special structure which are compressable. However, all such systems have been broken (as far as I know), and it seems that in most cases, adding special structure like that makes it more vulnerable to attack.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.