1
$\begingroup$

Let's say there are $n$ participants each with their own secret key $x_i$. Is it possible for them somehow to build a shared key which is an arithmetic sum of all their secret keys ($x_0 + x_1 + ... + x_n$) but without revealing their individual keys to each other.

Also, ideally, this would be done non-interactively. Meaning, each participant shares something about their secret key with everyone else, and once everyone has shared this "something", the shared key can be constructed.

$\endgroup$
3
  • $\begingroup$ If you use summing, parties can collude to reveal a key by subtracting all their keys from the shared secret, it is best to use multi-party DH, see crypto.stackexchange.com/questions/1025/… $\endgroup$ Sep 27 '18 at 1:38
  • $\begingroup$ For my purposes collusion is not a significant problem. Also, the number of parties is really large (10K+) - so, I'm not sure DH would be practical. Lastly, for my purposes the shared key must be an arithmetic sum of all secret keys - I don't think that would be the outcome with DH. $\endgroup$
    – irakliy
    Sep 27 '18 at 1:51
  • 2
    $\begingroup$ why must they be a sum? that is a very unusual requirement $\endgroup$ Sep 27 '18 at 2:31
1
$\begingroup$

Secret sharing is a perfect tool for this application. Under any linear secret sharing scheme, individuals can generate shares of secret values to distribute to other parties involved in the scheme. Once each individual has distributed shares of their secret value to all the other parties, due to the linearity of the scheme they can each locally sum the set of received shares and the collectively hold a valid share of the summation. This is because, by definition, linear secret sharing schemes possess and additive homomorphism, meaning that adding shares yields shares of a value which, if revealed in a reconstruction process, is identical to the value of the summed secrets.

In a more detailed manner, illustrated with additive secret sharing, every party $P_i\ \forall i\in Z_{n+1}$ generates $n$ random values in some valid group denoted by $m$ which will serve as shares of the secret $x_i$ for all the other player i.e. $[x_i]_{\mathbb{Z_m}}^{P_j}\in_R\mathbb{Z}_m \ \forall i,j\in Z_{n} $ and the final share satisfies the following equation $[x_i]_{\mathbb{Z_m}}^{P_n}=x_i-\sum_{j=0}^{n-1}[x_i]_{\mathbb{Z_m}}^{P_j} \mod m$. Then every party $P_i$ sends $[x_i]_{\mathbb{Z}_m}^{P_j}$ to all other parties such that $i\neq j$. Finally, the parties all locally compute the following summation locally in which $x_\Sigma$ denotes the summed secrets. $$ [x_\Sigma]_{\mathbb{Z}_m}^{P_i} = \sum_{j=0}^{n}[x_j]_{\mathbb{Z}_m}^{P_i}\mod m$$

Now each party holds uniformly random and information theoretically secure shares of the sum of their individual secrets and all parties must cooperate to reveal the underlying value. Specifically they would have to communicate all their individual shares to one another then they could each locally calculate: $$x_\Sigma = \sum_{i=0}^{n}[x_\Sigma]_{\mathbb{Z}_m}^{P_i} \mod m$$

I encourage you to look deeper into secret sharing in general as well as other schemes, Shamir's secret sharing scheme in particular, due to the resilience it can introduce to a system in the presence of active adversaries or component failures.

$\endgroup$
3
  • $\begingroup$ Thank you! If I understood correctly, this requires 2 rounds of communication: (1) to distribute all but one shares of each secret $x_i$, and (2) to distribute all locally summed up shares from the first round - right? If so, is there any way to reduce communications to a single round? $\endgroup$
    – irakliy
    Sep 27 '18 at 4:25
  • $\begingroup$ @irakliy Yes, two rounds would be required for the construction of the shared secret and then revealing it to one another, but the operations themselves locally are fairly trivial, being simple modular additions in the given example. $\endgroup$
    – Ken Goss
    Sep 27 '18 at 14:58
  • $\begingroup$ Thank you! I'm wondering if there is a scheme that allows constructing a public sum out of secret parts in a single round. But I'll create a separate question for this. $\endgroup$
    – irakliy
    Sep 27 '18 at 16:53

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.