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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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:
They show how to build a public-key encryption algorithm $E(\cdot)$ with the following two useful properties:
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.