Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
3  
cstheory.stackexchange.com/a/14062/6973 $\:$ –  Ricky Demer Mar 21 '13 at 16:29
    
@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$ –  curious Mar 21 '13 at 17:24
    
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. $\;\;$ –  Ricky Demer Mar 21 '13 at 19:25
    
@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 –  curious Mar 22 '13 at 9:03
add comment

1 Answer 1

up vote 4 down vote accepted

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:

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

share|improve this answer
    
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. –  curious Mar 22 '13 at 9:07
    
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? –  curious Mar 22 '13 at 10:41
    
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$ –  curious Mar 22 '13 at 10:50
    
It's stupid what i said. Of course itis because $(a + b) \cdot c = a \cdot c +b \cdot c$ –  curious Mar 22 '13 at 18:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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