2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you confusing it with Goldwasser–Micali cryptosystem? That is highly used for the x-or operation. $\endgroup$
    – kelalaka
    Feb 13 at 15:15
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Feb 13 at 20:13
  • $\begingroup$ @Mark The reason is that McEliece is a post-quantum cryptosystem. Could you mention other post-quantum cryptosystems with low-cost additive homomorphism? $\endgroup$
    – Anas Ahmad
    Feb 15 at 13:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mark Schultz-Wu
    Feb 15 at 18:39

1 Answer 1

2
$\begingroup$

You should decrypt and add.

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.

The XOR operation does seem a natural way to combine ciphertexts, but integer addition of bit representations cannot be implemented only using XOR gates.

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.

$\endgroup$
2
  • $\begingroup$ @Denial thanks for your answer. Could you justify your last sentence? If we choose t large enough, then we can't say that t/2 is sufficient. Thanks again. $\endgroup$
    – Anas Ahmad
    Feb 15 at 13:32
  • $\begingroup$ @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. $\endgroup$
    – Daniel S
    Feb 15 at 14:27

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.