Since the McEliece cryptosystem is linear, if matrix G is kept constant for different plaintexts, it can be used for linearly combining the corresponding ciphertexts. In that case, what are the advantages of McEliece over Paillier encryption?

  • 1
    $\begingroup$ I don't think McEliece is homomorphic because I think that if you add two ciphertexts, you get the added errors from both and as the only the errors from a single message are at the maximal capacity of the correcting code, decryption would fail. $\endgroup$
    – SEJPM
    Oct 7, 2017 at 9:20
  • 1
    $\begingroup$ @SEJPM: well, obviously, you would do the same trick as you do with Lattice-based homomorphic systems; you make the initial error quite small (and enlarge the size of the system to keep security...); that way, you stay under the bounds of what the correcting code could handle... $\endgroup$
    – poncho
    Oct 7, 2017 at 20:34
  • $\begingroup$ McEliece is (candidate) post-quantum. ​ Pallier will trivially fall to Shor's algorithm. $\hspace{1.28 in}$ $\endgroup$
    – user991
    Oct 8, 2017 at 5:05

1 Answer 1


In that case, what are the advantages of McEliece over Paillier encryption?

It's not that easy to think of any specific advantages; the public key will be huge (because you would need to expand the code to allow the relatively small initial error vectors to be secure), and those keys are already large enough to begin with.

About the only thing that springs to mind is the addition operation; for Pallier, the addition operation is addition modulo $\mathbb{Z}_n$, with the homomorphic McEliece, it would be addition in some field $GF(2^n)$, for some relatively large $n$, and perhaps some application would prefer that addition.

On the other hand, there are other cryptosystems (such as Goldwasser-Micali) which are homomorphic over addition in $GF(2)$, and running $n$ parallel copies would give you addition in $GF(2^n)$. It would appear likely that the homomorphic operation in McEliece is cheaper than the homomophic in $n$-ways parallel Goldwasser-Micali; however, to me, that sounds like a minor advantage (given the other disadvantages, such as Goldwasser-Micali has no bound on the number of homomorphic operations you can do before the ciphertext becomes undecryptable)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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