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$:
- $E'(E(m, pub_a), pub_b) = E'(E(m, pub_b), pub_a)$, where $E'$ is a re-encryption function
- $E(m + x, pub_a) = E(m, pub_a) ⊕ E(x, pub_a)$, where $⊕$ could be either $+$ or $*$
- $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}$