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?
