2
$\begingroup$

Suppose Alive and Bob have shares of two polynomials $P,Q$, say, Alice knows $P_A,Q_A$, Bob knows $P_B,Q_B$ s.t. $P=P_A+P_B$ and $Q=Q_A+Q_B$. They perform some operation $f$ over the shared values, to obtain shares of $f(P,Q)$.

If they reveal the shares of $f(P,Q)$, will this give hints on their individual shares of $P,Q$?

I am supposing that one cannot deduce $P$ or $Q$ with the knowledge of $f(P,Q)$. I just want Alice and Bob to know $f(P,Q)$ without leaking shares.

$\endgroup$
6
  • 1
    $\begingroup$ Wouldn't this depend on how the operation $f$ works? Trivial example: if $f(P,Q)=P$, and they generate shares of $f(P,Q)$ just by taking their shares of $P$, then revealing the shares of $f(P,Q)$ will also reveal their shares of $P$. $\endgroup$
    – poncho
    Commented May 9, 2016 at 13:15
  • $\begingroup$ Is $f$ computed using an information-theoretically secure MPC protocol? It shouldn't give any more information than what is provided by having just the output itself. $\endgroup$
    – mikeazo
    Commented May 9, 2016 at 13:45
  • $\begingroup$ @poncho, As the last phrase reads one cannot deduce $P$ or $Q$. $\endgroup$ Commented May 9, 2016 at 14:27
  • $\begingroup$ @mike, I don't see how the computation of $f$ affects the result, as soon as the computation does not reveal shares of $P,Q$. Also, note that this is different than the MPC protocol to compute $f(P,Q)$ where A holds $P$ and B holds $Q$. $\endgroup$ Commented May 9, 2016 at 14:31
  • 1
    $\begingroup$ I'm confused, they have additive shares of polynomials. Are these polynomials over the reals or something else? They compute compute on their shares to get shares of some function of the polynomials. You want to know whether or not given the shares of the output polynomial could reveal information about the shares of the input polynomials. The secret sharing method is additive, but the method for computing the output shares is not-specified and I don't see how it can be answered generically for any method of computing the output shares. $\endgroup$
    – mikeazo
    Commented May 9, 2016 at 15:13

1 Answer 1

1
$\begingroup$

It depends on how you make shares out of a polynomial. Consider for example Shamir secret sharing, using which a party can share a secret $s \in F$ (where $F$ is a finite field) with $n$ parties by doing the following:

  • Construct a polynomial $f(x) = s + a_1x+a_2x^2+\dots + a_nx^t$, for some $t$, where $a_i \in_R F$ for all $1 \leq i \leq n$.
  • Send the value of $f(i)$ to party $P_i$ for all $1 \leq i \leq n$.

The above mentioned secret sharing scheme is linear and it further allows us to perform multiplication of shared values as well. When using Shamir secret sharing for evaluating an arithmetic circuit securely, we release the shares of the final output in public, from which the final output can be constructed. The proof for the fact as to why the shares donot leak anything more than the described output can be found in the Chapter 3 of the textbook titled "Secure Multiparty Computation and Secret Sharing".

$\endgroup$

Your Answer

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

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