2
$\begingroup$

This question is related to the question I asked here. I'm looking for encryption scheme with the following properties:

Given $m$ is a 256-bit value, $pub_a$ and $pub_b$ are public keys, and $priv_a$ is a private key for $pub_a$:

  1. $E'(E(m, pub_a), pub_b) = E'(E(m, pub_b), pub_a)$, where $E'$ is a re-encryption function
  2. $E(m + x, pub_a) = E(m, pub_a) ⊕ E(x, pub_a)$, where $⊕$ could be either $+$ or $*$
  3. $D(E(m, pub_a), priv_a) = m$

It seems like non-randomized "exponential" version of EC El Gamal (as described here) satisfies conditions 1 and 2, but 3 would be difficult to do for large values of $m$. There are potential ways to get around this, but I'm wondering if there is another encryption scheme that could be used instead. (note: using non-randomized version should not compromise security because messages would be randomly padded prior to encryption).

Specifically, I came across this paper which in section 3.2 describes something that might work for my purposes. Unfortunately, my ability to read scientific literature is not advanced enough for me to fully understand the proposed scheme.

Explanation of how a modified EC El Gamal satisfies conditions 1:

Assuming $G$ is a generator point, $m$ is a padded message, $x_a$ and $x_b$ are private keys, and $X_a$ and $X_b$ are corresponding public keys, we can do:

  • $k_a = H(X_a)$, $k_b = H(X_b)$, where $H$ is some hash function
  • Encrypting $m$ with $X_a$ we get: $C_a = (k_aG, mG + k_aX_a)$
  • Encrypting $m$ with $X_b$ we get: $C_b = (k_bG, mG + k_bX_b)$

We can then define re-encryption as follows:

  • $C_{ab} = (k_aG + k_bG, mG + k_aX_a + k_bX_b)$
  • $C_{ba} = (k_bG + k_aG, mG + k_bX_b + k_aX_a)$

So, we have $C_{ab} = C_{ba}$

|improve this question
$\endgroup$
  • $\begingroup$ Ohh, I missread the question and assumed you wanted $\oplus$ be applied on the plaintexts (instead of standard sum). Obviously you don't care what happens with the ciphertexts. $\endgroup$ – SEJPM♦ Jun 16 '18 at 18:12
  • $\begingroup$ Does $+$ mean addition of integers $\bmod n$ for some $n\in\mathbb N$? (eg you don't want addition of points on an elliptic curve?) $\endgroup$ – SEJPM♦ Jun 16 '18 at 18:13
  • $\begingroup$ Yes, it should be integer addition. Just to give a concrete example using numbers: $E(9, pub_a) = E(2, pub_a) ⊕ E(7, pub_a)$. $\endgroup$ – irakliy Jun 16 '18 at 18:36
  • 1
    $\begingroup$ I don't see how "exponential" EC ElGamal satisfies point 1. The message space and ciphertext space are different, so you can't re-encrypt a ciphertext. Assuming that you don't really care about point 1, the standard way to construct an additive homomorphic cryptosystem is to use Paillier: en.wikipedia.org/wiki/Paillier_cryptosystem $\endgroup$ – djao Jun 16 '18 at 20:56
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jun 17 '18 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.