2
$\begingroup$

Let's say that there are two parties. Party $A$ has ciphertexts $c_1, c_2$ encrypting data $m_1,m_2$ respectively. $A$ does not know the secret key to decrypt $c_1, c_2$. Party $B$ has the secret key.

$A$ wants to compute $(m_1m_2)/(m_1+m_2).$ So, it chooses two uniformly random values $k_1,k_2$ and sends $k_1\cdot c_1\cdot c_2$ and $k_2\cdot(c_1+c_2)$ to $B$. $B$ decrypts the ciphertexts, resulting in $p_1,p_2$ respectively. $B$ does not learn the original data $m_1,m_2$ since $A$ has blinded them. $B$ computes $p_1/p_2$ and sends the result back to $A$ after encrypting.

I want to use this scenario in my implementation and I have not decided on any scheme, have thought about Paillier though. However, I am not sure how secure it is and how to implement it.

  • Can you suggest me some articles and example implementations?
$\endgroup$
  • 1
    $\begingroup$ The question seems unclear. What kind of encryption scheme are you using? Also your description is confusing as you seemingly use c1,c2 to refer to both the plaintexts and the corresponding ciphertexts. $\endgroup$ – Maeher Nov 15 '18 at 9:59
  • $\begingroup$ A wants to calculate $(p_1p_2)/(p_1+p_2).$ So, it sends $c_1 = k_1 p_1 p_2$ and $c_2 = k_2(p_1+p_2)$... It performs $c_1/c_2$ and after decrypting sends back to $A$....[lots of unlcear as Maeher said] $\endgroup$ – kelalaka Nov 15 '18 at 10:28
  • $\begingroup$ @dtoprakhisar I edited the question to what I think you are asking. Could you verify that this is actually what you meant? $\endgroup$ – Maeher Nov 15 '18 at 10:55
  • $\begingroup$ Yes, exactly it is. Sorry for inconsistency. $\endgroup$ – dilot Nov 15 '18 at 12:24
2
$\begingroup$

Your approach does not work, at least with Paillier. You're trying to homomorphically compute both $m_1m_2$ and $m_1 + m_2$, by computing $c_1c_2$ and $c_1 + c_2$. Three things:

  • first, even if you have a fully homomorphic encryption scheme (which can support both homomorphic additions and multiplications), it is in general not the case that the homomorphic multiplication of plaintext is just the multiplication of the ciphertexts, and that the homomorphic addition of plaintexts is just the addition of the ciphertexts (although the latter happens to be the case in most lattice-based schemes). Instead, you have some specific algorithms for computing each of the homomorphic operations.
  • Second, you want to use Paillier, but Paillier does only support homomorphic additions (computing $c_1c_2 \bmod N^2$ gives an encryption of $m_1 + m_2$, where $N$ is the Paillier modulus)
  • Third, your blinding approach fails. A first reason is that it does not suffice to hide the plaintexts only: you must also rerandomize the ciphertexts in general, otherwise they might leak information of the intermediate values of the plaintexts throughout the homomorphic operations. Typically with Paillier, this is done by multiplying the final ciphertexts with a random encryption of zero. Second, you only use multiplicative blinding on the plaintext; note that this leaks wether the values $m_1m_2$ and $(m_1+m_2)$ were equal to 0 or not.

Here is a better approach with Paillier. I assume that both parties are semi-honest (they do not actively cheat), and that A should not learn the individual plaintexts, but only $m_1m_2/(m_1+m_2)$, B should not learn anything.

  • A homomorphically adds a random value $r_i$ (picked over $\mathbb{Z}_N$, the plaintext space of Paillier) to the plaintext of $m_i$ for $i=1,2$, and randomizes the resulting ciphertexts. He sends the results $c'_1, c'_2$ to B.
  • B decrypts, obtaining $(m_1+r_1)$ and $(m_2+r_2)$. He computes the product of the two, and returns a random encryption $c$ of this product, which is $m_1m_2 +r_1m_2 + r_2m_1 + r_1r_2$.
  • A homomorphically computes an encryption of $r_1m_2$ from $r_1$ and $c_2$ (by computing $c_2^{r_1}\bmod N^2)$, and an encryption of $r_2m_1$ from $r_2$ and $c_1$ (by computing $c_1^{r_2}\bmod N^2)$. Then, he homomorphically substracts to $c$ these two encryptions, as well as $r_1r_2$, which he knows in the clear. More formally, he computes: $$c/(c_1^{r_2}c_2^{r_1}(1+N)^{r_1r_2}) \bmod N^2,$$ which is an encryption $c'$ of $m_1m_2$.
  • A homomorphically computes from $c_1$ and $c_2$ an encryption of $r(m_1+m_2)$ for a uniformly random $r$, randomizes the resulting ciphertext, and send the result $c''$ to B. B decrypts, inverts the output, re-encrypts it, and sends it back to A (note that since you want to compute $m_1m_2/(m_1+m_2)$, I'm assuming that we already know that $m_1+m_2$ is not 0 and is invertible, hence $r(m_1+m_2)$ does mask it perfectly).
  • A homomorphically multiplies the ciphertext he receives by $r$, getting an encryption of $(m_1+m_2)^{-1}$.
  • We're almost done: A now has encryptions of $m_1m_2$ and $(m_1+m_2)^{-1}$, and wants in the end to know their product. A can apply exacty the same strategy as he used to obtain an encryption of the product $m_1m_2$ from encryptions of $m_1$ and $m_2$, masking then by random values, etc. So, A sends encryptions of $m_1m_2+r'_1$ and $(m_1+m_2)^{-1}+r'_2$ for random masks $r'_1,r'_2$, B decrypts, multiplies, reencrypt, and A can homomorphically recover from that an encryption of $m_1m_2(m_1+m_2)^{-1}$.
  • To obtain the final result, we need one more interaction: A additively masks $m_1m_2(m_1+m_2)^{-1}$ by some random $R$ and randomizes the ciphertext; B decrypts and gets $m_1m_2(m_1+m_2)^{-1} + R$, which he sends back to A, who substracts $R$ and gets the final plaintext $m_1m_2(m_1+m_2)^{-1}$.

I'm too lazy to write a detailed security proof, but trust me, this securely allows to compute $m_1m_2(m_1+m_2)^{-1}$ in the semi-honest model (in the stand-alone setting), and this seems to be the right way to do it from Paillier (it's much simpler from fully-homomorphic encryption, but also probably much more involved computationally). As for implementing that, well, there are solutions around to implement Paillier encryptions and homomorphic operations, and it should not be too hard to implement this protocol - although, I usual, you should let that to professionals if it's for anything else that educational purpose.

$\endgroup$
  • $\begingroup$ Thank you, it is pretty clear to understand. But, if I say that A should not learn the content of m1 and m2, how should I rearrange this? $\endgroup$ – dilot Nov 15 '18 at 12:27
  • $\begingroup$ Here A only learns $m_1m_2/(m_1+m_2)$, not any individual values. If you want A to only learn an encryption of this value, then simply remove the last step of my protocol above: A has such an encryption in my protocol, the last step is only to let him recover the plaintext securely. $\endgroup$ – Geoffroy Couteau Nov 15 '18 at 18:59

Your Answer

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

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