Is there a practical homomorphic encryption scheme that can give reasonable execution time results in computing a dot product: $$a_1*b_1 + a_2*b_2 +a_3*b_3 +\ldots+ a_n*b_n$$ I imagine the scheme will need to support additions and multiplications to achieve this, so I assume we will need something that is fully homomorphic. Is there any scheme that can do this efficiently?
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ cstheory.stackexchange.com/a/14062/6973 $\:$ $\endgroup$– user991Mar 21, 2013 at 16:29
-
$\begingroup$ @RickyDemer in my case there is not secure multiparty computation. I have $m$ nodes. Each node is giving its $n$ integer values to another party who computes the dot product of all pairs of $m$ nodes.Also the cited reference at the link says for a public key construction with 1 multiplication but for dot product i need $n$ $\endgroup$– curiousMar 21, 2013 at 17:24
-
$\begingroup$ Can you edit your question to be more clear? $\:$ Right now, my suggestion would be $\hspace{1.2 in}$ "decrypt the ciphertexts and then use fused multiply-add". $\:$ For dot product, the aren't any $\hspace{.65 in}$ encrypted messages that need more than 1 multiplication. $\;\;$ $\endgroup$– user991Mar 21, 2013 at 19:25
-
$\begingroup$ @RickyDemer. I misunderstood the scheme. I thought that you were able to do just one multiplications but after D.W explanation it's clear that you can do more unless you want to multiply them together. Thank you $\endgroup$– curiousMar 22, 2013 at 9:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Yes, there is a solution. Ricky Demer pointed to it. (Thank you, Ricky!)
In particular, the following paper provides an elegant and efficient solution to your problem:
- Evaluating 2-DNF Formulas on Ciphertexts, Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.
They show how to build a public-key encryption algorithm $E(\cdot)$ with the following two useful properties:
Additively homomorphic. Given $E(x)$ and $E(y)$, anyone can compute $E(x+y)$.
Can multiply (once). Given $E(x)$ and $E(y)$ (neither of which was generated as a result of a multiplication operation), anyone can compute $E(x \cdot y)$. You can use the result in addition operations, but you cannot use it in any multiplication operations (the result of a multiplication is tainted, and tainted values cannot be used as the input to another multiplication).
This is enough to let you compute the inner product.
Here how this is helpful. Suppose you are given encryptions of $a_1,\dots,a_n,b_1,\dots,b_n$, where each ciphertext was encrypted using the scheme mentioned above. So, you have $E(a_1),\dots,E(a_n),E(b_1),\dots,E(b_n)$. By using the "multiply (once)" scheme, you can compute $E(a_1 b_1), \dots, E(a_n b_n)$, i.e., an encryption of $a_i * b_i$ for each $i$. Now you can use the "additively homomorphic" property to compute the sum of these, i.e., to compute $E(a_1 b_1 + \dots + a_n b_n)$. This is an encryption of the inner product, as you requested.
In short: given encryptions of the $a_i,b_i$ values, you can compute an encryption of the inner product, using the above scheme. This solves your problem. The encryption algorithm is pretty efficient (vastly more efficient than fully homomorphic cryptography). Incidentally, you don't need fully homomorphic encryption to solve your problem, which means that you should be able to obtain a much more efficient solution (using the above scheme) than if you tried to use fully homomorphic crypto.
-
$\begingroup$ Thank now it's clear to me. I thought as i commented to @Ricky that you can only do one multiplication. Your clarification was very helpful. You can do as many multiplications you want and you only can add them. $\endgroup$– curiousMar 22, 2013 at 9:07
-
$\begingroup$ Can i obtain the encryption of $E(x \cdot y)$ where $y=E(a)+E(b)=E(a+b)$ and x is $E(x)$ from the aforementioned scheme? $\endgroup$– curiousMar 22, 2013 at 10:41
-
$\begingroup$ That is is the other way around i think. Instead of $a_1 \cdot b_1 + a_2 \cdot b_2 +a_3 \cdot b_3 +\ldots+ a_n \cdot b_n$ i need $(a_1+b_1) \cdot c_1 + (a_2+b_2) \cdot c_2 + \ldots + (a_n+b_n) \cdot c_n$ $\endgroup$– curiousMar 22, 2013 at 10:50
-
$\begingroup$ It's stupid what i said. Of course itis because $(a + b) \cdot c = a \cdot c +b \cdot c$ $\endgroup$– curiousMar 22, 2013 at 18:16