2
$\begingroup$

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.
Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ @EllaRose it means xor all the ct_i for i's which satisfy x_i=1 $\endgroup$
    – Florian Bourse
    Jan 30, 2018 at 15:18
  • 1
    $\begingroup$ '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) $\endgroup$
    – poncho
    Jan 30, 2018 at 15:19
  • 1
    $\begingroup$ 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). $\endgroup$
    – Napoleon
    Jan 30, 2018 at 15:22
  • 1
    $\begingroup$ 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 $\endgroup$
    – Florian Bourse
    Jan 30, 2018 at 15:25
  • 1
    $\begingroup$ 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 $\endgroup$
    – Florian Bourse
    Jan 30, 2018 at 16:44

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Your final homomorphic multiplication for your public key scheme is thus:

$$(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)$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.