# The cost of the additive homomorphic encryption of McEliece cryptosystem

Let's have two integer-vectors $$v_1$$ and $$v_2$$ that are encrypted by McEliece public key. An intermediate node between the sender and receiver receives the two encrypted vectors $$\text{E}(v_1)$$ and $$\text{E}(v_2)$$ and it needs to add $$v_1$$ to $$v_2$$.

What will be the best choice in terms of computation cost, assuming that privacy is not important? Should the intermediate node decrypt the vectors first then add then encrypt again? Or shall it add $$\text{E}(v_1) + \text{E}(v_2)$$ homomorphically?

I'm asking this question because I noticed that the additive homomorphism of McEliece is just a XOR operation.

• Are you confusing it with Goldwasser–Micali cryptosystem? That is highly used for the x-or operation. Commented Feb 13 at 15:15
• Is there a reason you need McEliece specifically? Achiving additive homomorphism over $\mathbb{Z}$ (or properly over $\mathbb{Z}/n\mathbb{Z}$ for $n$ you get to pick) is easily done using several other cryptosystems. Commented Feb 13 at 20:13
• @Mark The reason is that McEliece is a post-quantum cryptosystem. Could you mention other post-quantum cryptosystems with low-cost additive homomorphism? Commented Feb 15 at 13:28
• @AnasAhmad most LWE (and RLWE/MLWE) cryptosystems can be made to be additively homomorphic atlow cost, and are post-quantum secure (and in fact, beat McEliece in the recent NIST standardization, mostly because McEliece's public keys are absolutely humongous). For particular schemes, looking at things such as B/FV or BGV (which additionally have multiplicative homomorphisms, but these are more expensive) is probably the thing to do. You should be able to find implementations of them here. Commented Feb 15 at 18:39

Let us take a simple McEliece set up where the public key is $$k\times n$$ matrix $$\hat G$$ and a $$k$$-long bit vector $$\mathbf m$$ is encrypted as $$\mathbf m\hat G\oplus \mathbf z$$ where $$\mathbf z$$ is a random $$n$$-bit vector with exactly $$t$$ non-zero entries.
Even if we only wanted to XOR plaintexts, the $$\mathbf z$$ vectors prohibit this for the set is not closed under XOR. So whereas it is true that we can write $$\mathbf m_1\hat G\oplus\mathbf m_2\hat G=(\mathbf m_1\oplus \mathbf m_2)\hat G$$ it is not true that $$\mathbf m_1\hat G\oplus \mathbf z_1\oplus\mathbf m_2\hat G\oplus\mathbf z_2=(\mathbf m_1\oplus \mathbf m_2)\hat G\oplus \mathbf z_3$$ where $$\mathbf z_3$$ has at most $$t$$ non-zeroes. Instead the weight of the error'' term could be as large as $$2t$$.
One should also be vary wary (i.e. avoid) trying to bypass this limitation by reducing the weight of $$\mathbf z_1$$ and $$\mathbf z_2$$. The security of the McEliece system depends very strongly on the Hamming weight of these vectors not being too small.
• @AnasAhmad It is possible to design a system where $t$ errors can be corrected by the decryptor and $t/k$ errors are secure against an adversary and so cope with at most $k$ XORs. However the costing of information set decoding attacks will require expert handling and the already painful bandwidth will become worse with these sorts of parameters. Commented Feb 15 at 14:27