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.

  • 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 May 9 '16 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 May 9 '16 at 13:45
  • $\begingroup$ @poncho, As the last phrase reads one cannot deduce $P$ or $Q$. $\endgroup$ – Tal-Botvinnik May 9 '16 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$ – Tal-Botvinnik May 9 '16 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 May 9 '16 at 15:13

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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