3
$\begingroup$

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 ?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Mark
    Nov 25, 2020 at 19:37
  • $\begingroup$ Also, do you care about leaking their secrets to an evesdropper, or also to eachother? $\endgroup$
    – Mark
    Nov 25, 2020 at 19:43
  • $\begingroup$ 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). $\endgroup$
    – dohmatob
    Nov 26, 2020 at 6:56

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ 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 :) $\endgroup$
    – dohmatob
    Nov 26, 2020 at 7:52
  • $\begingroup$ 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. $\endgroup$
    – dohmatob
    Nov 26, 2020 at 7:55
  • $\begingroup$ @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.) $\endgroup$
    – Mark
    Nov 26, 2020 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.