Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Alice and Bob respectively know a vector of $N$ real numbers $u$ and $v$. They would both like to know $\rho = \langle u,v \rangle/N$ but Alice does not want Bob to gain anymore information about $u$ than given by $\rho$ and vice versa.

The easy solution is that they go to a trusted third party that calculated $\rho$ for them and hands them the solution. That's not very interesting though.

Given that homomorphic encryption exists, we know there's a way to do this without a trusted third party, there may exist a simpler and more elegant solution to the problem though.

Let's relax the problem a little bit and allow for asymptotic solutions in three respects

  • The extra information can be made arbitrarily small by the protocol
  • The extra information can be made arbitrarily small by taking $N$ to infinity
  • $\rho$ can be calculated to an arbitrary degree of precision with an arbitrarily high probability

One road is for Alice and Bob to generate vectors $\epsilon$ and $\eta$ where every entry is a random normal number with a very large variance $\nu$.

Alice sends $u+\epsilon$ to Bob who computes and publishes $u.v + \epsilon.v$ Bob sends $v+\eta$ to Alice who computes and publishes $u.v + \eta.v$ They also compute $(u+\epsilon).(v+\eta)$. With all that, they can compute $(u.v - \epsilon.\eta)/N$.

There remains an error term, $\langle \epsilon.\eta \rangle/N$ which has standard deviation about $\nu/\sqrt{N}$

The problem is that there is a tradeoff here. If the $\nu$ is too small, too much about the vector is divulged, if it's too big there is too much noise in the result.

Another idea would be for Alice and Bob to agree on a random base of $\mathbf{R}^N$. Alice could then pick $\epsilon$ as a random linear combination of the first $N/2$ vectors, and Bob could pick $\eta$ as a linear combination of the last $N/2$ base vectors. This guarantees $\epsilon$ and $\eta$ will be orthogonal, but now Bob would know the projection of $u$ over a very large subspace. Not that good.

Thougths?

share|improve this question
    
By the way, you don't need fully homomorphic encryption to do this without a trusted third party; secure multiparty computation works, but the general techniques are still far from simple. –  Henry Cohn Jun 6 '12 at 14:56
2  
But whatever you do, you need to think about a security model. One of the big headaches is what happens if one of the participants stops following the protocol at all (and starts sending carefully chosen numbers for the sole purpose of learning about the other person's vector). One standard approach is to look first at the case of honest but curious participants. They always follow the protocol faithfully, but they may do other computation on the side to try to extract information. After solving that case, one can apply various techniques to reduce the general case to it. –  Henry Cohn Jun 6 '12 at 15:01
    
There seems to be an answer here cis.syr.edu/~wedu/Research/paper/duthesis.pdf –  Arthur B Jun 6 '12 at 15:16
add comment

1 Answer

up vote 4 down vote accepted

cis.syr.edu/~wedu/Research/paper/duthesis.pdf

My favorite protocol is the 2nd one. One variation of it would be:

Alice breaks down u as $u_1 + \ldots + u_p$ and transmits set $( \{u_1^0, u_1^1\}, \{u_2^0, u_2^1\} \ldots, \{u_p^0, u_p^1\} )$ to Bob where $u_i^1$ are just a random vectors. Bob computes the dot product of each vector with a $v$ and adds random number $\epsilon_i$. Using the oblivious transfer protocol Alice gets back $(u_1^0.v +\epsilon_1, \ldots, u_p^0.v + \epsilon_p)$ and thus can compute $u.v + \sum \epsilon_i$. Bob can then divulge $\sum \epsilon_i$ and $u.v$ is known.

I'm a little disappointed there isn't an answer that doesn't rely on modular arithmetic. I was hoping for a purely geometric protocol.

share|improve this answer
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.