EC-ElGamal scalar-to-point mapping for a secure multiparty computation setting

Question

The ElGamal cipher is additively homomorphic for points, but not for scalars. In a single party setting, people usually get around this by mapping the scalar m to points by just multiplying it with the generator (which effectively transfers the additive homomorphism from the point M to the underlying scalar):

M = m * G
C = encrypt(M, s)
// Perform some operations on our ciphertext
M' = decrypt(C,s)

Since going back from M' to m' requires solving the discrete log, all this is usually with the assumption that m is quite small (e.g. 32 bits or less). In a multiparty setting though, where the encryption key s is shared as additive shares amongst n peers, and the ciphertext is the point X,Y, this mapping breaks down:

• $\mathrm{DecryptWithShare}_i(s_i\!\in\!\mathbb{Z}_q,\; (X,Y)\!\in\! \mathbb{G}^2) \longrightarrow m_i$
  1. $M_i = - s_i\cdot X$
     • if i==0: $M_i = M_i + Y$
  2. Solve $M_i = m_i\cdot G$ to recover $m_i$. ????????
     • Requires $m_i$ to be small enough, but these are scalar shares and thus span the entire scalar field!
  3. Return $m_i$

Even if m is guaranteed to be small, an individual share m_i can be anything in Z_q since it depends on M_i which in turn depends on s_i and X, where X is effectively random. Is there a way to get around this that doesn't involve

a) reducing the field size that our s and X lie in to 32 bits or smaller (which would make the whole scheme insecure)

b) having all peers send their M_i to a single peer who computes m and redistributes it to its peers in shares (as this would mean a peer would learn what the plaintext is which we want to avoid)

e.g. through a different mapping from scalar to point that preserves additive homomorphism?

Answer 1

For the 2-party case, a solution is described in a paper of Boyle, Gilboa and Ishai, “Breaking the Circuit Size Barrier for Secure Computation Under DDH”, that basically explains how to obtain a secret sharing of the small plaintext from the ciphertexts under the shared key (see also this post for a short summary of the idea). As far as I know, doing the same for more than two parties is an open problem, unless you're happy with generic MPC techniques for the homomorphic decryption.

In practice, though, the reasonable solution is to use a bona fide additively homomorphic encryption scheme, like Paillier or one of the lattice-based ones (BGV, FV, etc.). ElGamal is not suitable for your application.