Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Consider two paranoid parties Alice and Bob. Say Alice owns a secret vector $x=(x_1,\ldots,x_n) \in \mathbb R^n$ and Bob owns a secret vector $y=(y_1,\ldots,y_n) \in \mathbb R^n$.
Question. How can both parties compute the dot product $x\cdot y$ in time $\mathcal O(n)$ without leaking their respective secrets ?
I will assume you are in the honest-but-curious model. You can't represent real numbers in finite space, so I will assume all values are represented in fixed-point arithmetic, to $d$ bits of precision; thus $x$ is represented as $x = x'/2^d$ where $x'$ is an integer. Then $x \cdot y = x' \cdot y' / 2^{2d}$, so the problem is equivalent to computing $x \cdot y$ where $x,y \in \mathbb{Z}^n$. Here is a scheme for that.
Pick a sufficiently large prime, and let $E$ denote a public-key encryption algorithm that is additively homomorphic modulo $p$. Alice generates a public/private keypair for $E$, and computes $E(x_i)$ for each $i$. She sends these to Bob, along with the public key she generated. Bob computes $E(x_i y_i)$ for each $i$, using the homomorphic properties of $E$, and from them, computes $E(\sum_i x_i y_i) = E(x \cdot y)$, again using the homomorphic properties of $E$. Bob sends $E(x \cdot y)$ to Alice. Alice decrypts, and shares the result with Bob.
Note that if $E$ is additively homomorphic, given $E(x)$ you can compute $E(2x) = E(x+x)$. Therefore, given $E(x)$ and an integer $y$ you can compute $E(xy)$, using a double-and-add algorithm (analogous to square-and-multiply).
