# Shamir's scheme secret sharing

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

• "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? – poncho Oct 18 '17 at 14:17
• The problem is I need the minimum information for every participant to get S1+S2 but A shouldn't to know S1 nor S2. – drino Oct 18 '17 at 14:22
• 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. – drino Oct 18 '17 at 14:23
• "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... – poncho Oct 18 '17 at 14:32

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