# Fast private computation of dot product

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 ?

• Do you need the exact value, or does some approximation suffice? It's worth mentioning that there's a (randomized) communication complexity lower bound of $\Omega(n)$ to compute the inner product (mod 2), so there is "not much slack" to work with compared to the best (non-private) protocol one can use.
– Mark
Nov 25, 2020 at 19:37
• Also, do you care about leaking their secrets to an evesdropper, or also to eachother?
– Mark
Nov 25, 2020 at 19:43
• I'm worried about leaking secrets to each other. You may assume that the communications are otherwise secure (no 3 parties). Also concerning accuracy, I'm realy only interested in testing whether $x^\top y \ge b$ (for some threshold $b \in \mathbb R$ which is known only to Alice). Nov 26, 2020 at 6:56

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).
• BTW, do you think the problem is much simplified If but parties are only interested in securely testing whether $x^\top y \ge b$ (where $b$ is a threshold only known to Alice) ? That's if they don't really care about the actual value of $x^\top y$ beyond the fact that it is positive or not. Nov 26, 2020 at 7:55
• @dohmatob it depends on how much "slack" you allow. For example, if you're OK with the computation failing sometimes (say returning YES when $x^ty\geq (1+\epsilon)b$ for $\epsilon >0$, "NO" when $x^ty<b$, and some indeterminate answer in the "middle region"), I suspect you can apply dimensionality reduction techniques to get a decently-sized speedup (the Johnson-Lindenstrauss lemma is the relevant thing to look up, but it is for a slightly different problem.)