-3
$\begingroup$

Shamir's scheme for implementing an $(n, k)$ sharing of a secret $S$ involves a random polynomial $F$ of degree $k-1$ such that $F (0) = S$. Each of the $n$ shares of $S$ is a pair $(x, F (x))$ for $x$ between $1$ and $n$. Consider a setting with $n$ participants $P_1, P_2, \dots, P_n$, and 2 secrets $S1$, $S2$. Each participant $P_i$ is given a distinct share $S1_i$ of secret $S1$ based on a suitable polynomial $F1$ for an $(n, t)$ sharing and a distinct share $S2_i$ for secret $S2$ based on a suitable polynomial $F2$ for an $(n, t)$ sharing. Show how a new principal $A$ can communicate with existing participants to learn $S1 + S2$, without learning either $S1$ or $S2$.

$\endgroup$
  • 1
    $\begingroup$ "Show how a new principal A can communicate with existing participants to learn S1 + S2, without learning either S1 or S2"; easy, A asks t participants for S1+S2; they recover both S1, S2, add them, and give the sum to A. This meets all the requirements you gave; if this is insufficient, then what additional requirements do you have? $\endgroup$ – poncho Oct 18 '17 at 14:17
  • $\begingroup$ The problem is I need the minimum information for every participant to get S1+S2 but A shouldn't to know S1 nor S2. $\endgroup$ – drino Oct 18 '17 at 14:22
  • $\begingroup$ A cannot request the exact shares from each participant, as that would enable A to reconstruct S1 and S2, and we want to avoid that. The participants need to send A a piece of information that enables A to reconstruct S1 + S2, but not S1 or S2. You need to figure out what is that piece of information that each participant needs to send to A. $\endgroup$ – drino Oct 18 '17 at 14:23
  • $\begingroup$ "The participants need to send A a piece of information that enables A to reconstruct S1 + S2"; if they send A the value S1+S2, A can reconstruct S1+S2 from that. The t participants jointly know the values S1, S2, , can reconstruct them and then add them (without A overhearing, obviously), and then transmit A the sum; problem solved... $\endgroup$ – poncho Oct 18 '17 at 14:32
2
$\begingroup$

You can use the fact that Shamir secret sharing is linear. Each participant $P_i$ adds their two shares locally $S1_i+S2_i$, then sends this value to $A$.

Because of the linearity of Shamir secret sharing, this will allow $A$ to reconstruct to get $S1+S2$. Furthermore, none of the participants learns the sum (not a stated requirement in your question, but presumably something that you are looking).

$\endgroup$

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.