<p>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 <span class="math-container">$d$</span> bits of precision; thus <span class="math-container">$x$</span> is represented as <span class="math-container">$x = x'/2^d$</span> where <span class="math-container">$x'$</span> is an integer.  Then <span class="math-container">$x \cdot y = x' \cdot y' / 2^{2d}$</span>, so the problem is equivalent to computing <span class="math-container">$x \cdot y$</span> where <span class="math-container">$x,y \in \mathbb{Z}^n$</span>.  Here is a scheme for that.</p>
<p>Pick a sufficiently large prime, and let <span class="math-container">$E$</span> denote a public-key encryption algorithm that is additively homomorphic modulo <span class="math-container">$p$</span>.  Alice generates a public/private keypair for <span class="math-container">$E$</span>, and computes <span class="math-container">$E(x_i)$</span> for each <span class="math-container">$i$</span>.  She sends these to Bob, along with the public key she generated.  Bob computes <span class="math-container">$E(x_i y_i)$</span> for each <span class="math-container">$i$</span>, using the homomorphic properties of <span class="math-container">$E$</span>, and from them, computes <span class="math-container">$E(\sum_i x_i  y_i) = E(x \cdot y)$</span>, again using the homomorphic properties of <span class="math-container">$E$</span>.  Bob sends <span class="math-container">$E(x \cdot y)$</span> to Alice.  Alice decrypts, and shares the result with Bob.</p>
<p>Note that if <span class="math-container">$E$</span> is additively homomorphic, given <span class="math-container">$E(x)$</span> you can compute <span class="math-container">$E(2x) = E(x+x)$</span>.  Therefore, given <span class="math-container">$E(x)$</span> and an integer <span class="math-container">$y$</span> you can compute <span class="math-container">$E(xy)$</span>, using a double-and-add algorithm (analogous to <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow noreferrer">square-and-multiply</a>).</p>

CC BY-SA 4.0
2020-11-26T07:52:02.063Z
Yep, indeed I was about to add a comment to you previous answer saying that things could be remedied via FPA, but you deleted it just in time :)
dohmatob
CC BY-SA 4.0
2020-11-26T07:55:02.570Z
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.
dohmatob
CC BY-SA 4.0
2020-11-26T20:58:54.777Z
@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.)
Mark Schultz-Wu
CC BY-SA 4.0
2020-11-26T07:49:36.560Z
2020-11-26T07:53:15.640Z
2020-11-26T07:53:15.640Z
D.W.
<p>Consider two paranoid parties Alice and Bob. Say Alice owns a secret vector <span class="math-container">$x=(x_1,\ldots,x_n) \in \mathbb R^n$</span> and Bob owns a secret vector <span class="math-container">$y=(y_1,\ldots,y_n) \in \mathbb R^n$</span>.</p>
<blockquote>
<p><strong>Question.</strong> How can both parties compute the dot product <span class="math-container">$x\cdot y$</span> in time <span class="math-container">$\mathcal O(n)$</span> without leaking their respective secrets ?</p>
</blockquote>

CC BY-SA 4.0
2020-11-25T19:37:55.457Z
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 Schultz-Wu
CC BY-SA 4.0
2020-11-25T19:43:40.613Z
Also, do you care about leaking their secrets to an evesdropper, or also to eachother?
Mark Schultz-Wu
CC BY-SA 4.0
2020-11-26T06:56:59.093Z
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).
dohmatob
<cr.crypto-security><privacy>
Fast private computation of dot product
dohmatob
# Fast private computation of dot product

(Asked by: username_0 on 2020-11-25)

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 ?

**Tags:** cr.crypto-security, privacy

> **Comments:**
> **username_1**: 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.  
> **username_1**: Also, do you care about leaking their secrets to an evesdropper, or also to eachother?  
> **username_0**: 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).  

---

## 1 answers

### Answer by username_2 on 2020-11-26. Score: 3 | Accepted answer

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](https://en.wikipedia.org/wiki/Exponentiation_by_squaring)).

> **Comments:**
> **username_0**: Yep, indeed I was about to add a comment to you previous answer saying that things could be remedied via FPA, but you deleted it just in time :)  
> **username_0**: 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.  
> **username_1**: @username_0 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.)  

---

