# Public key homomorphic encryption based on secret key homomorphic

Let $(E,D)$ be a secret-key bit-encryption scheme that is homomorphic to xor, and assume that each bit encryption is of size n (this concerns both fresh encryption and encryptions that have been homomorphically manipulated). For two ciphertexts $ct$ and $ct'$, we abuse notation and will denote by $ct \oplus ct'$ the ciphertext resulting from their homomorphic xor. Consider the following suggestions for a public-key encryption scheme:

• $G'$ sample $r \gets \{0,1\}^{2n}, sk \gets \{0,1\}^n$.
• $pk = (r, ct_1, . . . , ct_{2n})$, where $ct_i = E_{sk}(r_i)$. The secret key is sk.
• $E'_{pk}(m) = (\oplus_{i:x_i =1} ct_i, m \oplus_{i:x_i=1} r_i)$ is done by sampling $x \gets \{0,1\}^{2n}$
• $D'_{sk}(a, b) = D_{sk}(a) \oplus b$.

I already proved that $(E',D')$ is CPA secure based on $(E,D)$ CPA secure. Now I want to prove that if $(E,D)$ is fully homormorphic encryption scheme, so does $(E',D')$. In order to do so, I think that it is enough to show support of homomorphically $\times, \oplus$ in $(E',D')$.

Let $(a_1,b_1),(a_2,b_2)$ denote 2 encryptions. The problem I encounter is the second term $b_j$ in the encryption: $m_j \oplus_{i:x_i = 1} r_i$.

Supporting homomorphic xor in $(E',D')$ can be made simply by outputting $(a_1 \oplus a_2, b1 \oplus b2)$. In order to support $\times$ homomorphically, I defined $b_j = m_j \oplus R_j$, and tried to set: $$(a_1 \times a_2, b_1 \times b_2) = (a_1 \times a_2, (m_1 \oplus R_1) \times (m_2 \oplus R_2)) = (a_1 \times a_2, m_1m_2 + R_1R_2 + m_1R_2 + m_2R_1)$$

where + is like $\oplus$ in our case (mod 2). Trying now to decrypt, we get $m_1m_2 + m_1R_2 + m_2R_1$ which is wrong, and in general this is my problem: how can set homomorphically "the correct" value, which should be $(SOMETHING, m_1\times m_2 \oplus SOMETHING)$.

I'd appreciate any suggestions.

Clarification:

1. Please note that I want to prove it based on the above, and not modify the scheme.
2. The scheme is initially assumed to be xor homomorphic, and next assumed to be FHE.
• @EllaRose it means xor all the ct_i for i's which satisfy x_i=1 Jan 30, 2018 at 15:18
• 'I already proved that $(E',D')$ is CPA secure based on $(E,D)$ CPA secure'; I believe that to do this, you need to make additional assumptions on the $ct \oplus ct'$ operation. For example, if it is linear in $GF(2)$ (e.g. xoring two ciphertexts will xor the corresponding plaintext), then it is easy to decrypt by anyone with the public key (and hence not CPA secure) Jan 30, 2018 at 15:19
• Few clarifications: @GeoffroyCouteau: 1) there was a mistake, $sk \gets \{0,1\}^n$. 2) the initial encryption is first assumed to be only XOR homomorphic. Moving forward, assuming it's FHE, but staying with the same construction, I want to prove the new scheme is FHE (so I can't modify the building). Jan 30, 2018 at 15:22
• I think the more standard procedure would be to have n encryptions of 0 and 1 encryption of 1 as the public key. Then you sum a random subset of the encryptions of 1 and add the encryption of 1 if and only if you want to encrypt 1. Then you inherit all the homomorphic properties of the underlying secret-key scheme because you ciphertext is basically a ciphertext from the first scheme. You just have to show the CPA security, which is left as an exercise to the reader Jan 30, 2018 at 15:25
• if b1 is 1 you substract a2 otherwise you don't. Also, note that the neutral elements for homomorphic additions and multiplications are automatically public because you can take an encryption of 1 and substract it to itself or divide it by itself Jan 30, 2018 at 16:44

What you found out is really close to the result you want. In fact, your $SOMETHING$ will be $m_1R_2+m_2R_1+R_1R_2$.

The only missing step is giving out an encryption of $SOMETHING$ as the first component of your ciphertext.

In order to do so, notice that you can easily multiply $a_1$ by $b_2$, since $b_2$ is a bit:
$a_1 \times b_2 = a_1$ if $b_2 = 1$, and $0$ otherwise. (this $0$ can be computed as $a_1⊕a_1$, and $b_2$ is a public value)

Now, $a_1 \times b_2$ encrypts $m_2 R_1 + R_1 R_2$. By symmetry, you can remove $a_2 \times b_1$ that encrypts $m_1 R_2 + R_1 R_2$.

Finally, notice that $a_1 \times a_2$ encrypts $R_1R_2$.

We are now ready to give $a_1\times b_2 + a_2\times b_1 - a_1 \times a_2$ which encrypts $m_2R_1+R_1R_2+m_1R_2+R_1R_2-R_1R_2=SOMETHING$.

$$(a_1,b_1)\times(a_2,b_2) = (a_1\times b_2 + a_2\times b_1 - a_1 \times a_2,\, b_1 \times b_2)$$