5
$\begingroup$

Wikipedia on its page for Shamir's secret sharing scheme provides a python implementation that applies the idea. This algorithm will generate a (k, n) threshold scheme so for example we could split a secret in 6 parts and we would need only 3 of them to recreate it.

But isn't the idea of this scheme to be used by a number of various agents that each one will generate only a part of the key and share it? This way each agent can then create the secret key by combining the parts he will receive.

What would be the proper way to make this algorithm distributed and not generating everything in one computer?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ It might help to be more specific about what you hope to accomplish with the secret once it is generated. For example, do you want to make signatures with it? if so, you might actually want a threshold signature scheme instead. Do you want to make a public key that anyone can use to encrypt messages, which require a quorum of agents to collaborate for decryption? If so, you might want distributed key generation. Either of these keywords will turn up various literature that you might use to refine your question. $\endgroup$
    – Squeamish Ossifrage
    Jun 4, 2018 at 19:01
  • 1
    $\begingroup$ Is this question about the share generation, or the share recombination step? If the former, how do you decide what the ultimate secret is (and does anyone hold that value)? Or, is it sufficient to generate a random secret (with the constraint that any $k$ shares would reconstruct the same secret)? $\endgroup$
    – poncho
    Jun 4, 2018 at 20:37
  • $\begingroup$ @SqueamishOssifrage I am not trying to do anything in particular other than re-writing wikipedia's example to make it distributed, but I was sure that other people have thought the exact same thing, and probably done it better. $\endgroup$
    – dearn44
    Jun 5, 2018 at 8:49
  • $\begingroup$ @poncho no I think I have a grasp on how the shamir shares aregenerated, its the distributed proper recombination that is confusing. $\endgroup$
    – dearn44
    Jun 5, 2018 at 8:50
  • $\begingroup$ Will someone ultimately hold the secret in its entirety after recombination? If so, what's the issue with everyone passing them their share, and having that ultimate holder doing the computation? What is the security problem that straight-forward solution doesn't address, and that you're trying to solve? "I want to make do it in a distributed manner" isn't a problem; it's a potential solution to a problem. $\endgroup$
    – poncho
    Jun 5, 2018 at 12:13

3 Answers 3

Reset to default
3
$\begingroup$

Each participant can create his own random k,n secret sharing and send one share to each other participant. Each participant can then add up his sub-shares to get his final share.

Due to linearity the resulting is also a valid shamir secret sharing.

This produces a random shared secret. If there is something you want to protect with it, we need to ask who knows it initially?

Improve this answer
$\endgroup$
4
  • $\begingroup$ That requires $n(n-1)$ secure communications and trust in all $n$ participants. If one sends haphazard values, the result obtained when joining $k$ shares will depend on what shares that is. $\endgroup$
    – fgrieu ♦
    Jun 5, 2018 at 5:02
  • $\begingroup$ So if I combine the required number of various share parts from different independent shamir shares of a different secret key for each server I will get the same final secret key in each server? $\endgroup$
    – dearn44
    Jun 5, 2018 at 8:54
  • $\begingroup$ @dearn44: not exactly: to recover the shared secret number, you combine the required number $k$ of pseudo-shares each obtained by summing $n$ Shamir shares, that each of the $n$ participant obtained as the one of $n$ shares left after generating $n$ shares and sending (and forgetting) one for each other $n-1$ participants, with the shares s/he received from the other participants (one for each other $n-1$ participants). $\endgroup$
    – fgrieu ♦
    Jun 5, 2018 at 12:21
  • $\begingroup$ We can validate the results with secure multi party computation. As for communication this may or may not be a practical issue. I would love to hear something better. $\endgroup$
    – Meir Maor
    Jun 5, 2018 at 16:43
-1
$\begingroup$

The purpose of Shamir's (k,n)-threshold secret sharing is to be able to distribute a secret amongst a group of agents such that no single participant knows the secret and that the secret can be reconstructed only via a cooperation of all or some of the group members.

A single point of generation is necessary for this type of secret sharing and it is used in multiple real world applications today.

For example: ICANN has a contingency plan to "restart" the internet should the current root keys be compromised in some fashion. The key which must be used to trigger this plan was distributed using a (5,7)-threshold scheme with the keys given to member organizations in Britain, the US, Trinidad and Tobago, Canada, China, and the Czech Republic.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This doesn't answer the question, which is of how to perform the computation and distribute shares without a single point of generation. $\endgroup$
    – Squeamish Ossifrage
    Jun 4, 2018 at 13:47
-2
$\begingroup$

Each user $i=1,\ldots,n,$ could randomly generate a share $K_i$ of the right bitlength to give the desired security and transmit hers share to a trusted third party, $T.$

$T$ could generate the secret as, say, $$ S=H(K_1\oplus \cdots\oplus K_n) $$ with a hash function and then use Shamir(n,t) to generate the shares and distribute to the users $i.$

Note that it would be less secure to generate shorter shares and have the TTP concatenate them before hashing.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This answers a different question: How do the users prevent the dealer from manipulating the shares? It doesn't answer the question above: How do you generate the shares without a single point of generation that has the unilateral power to compromise the whole system? $\endgroup$
    – Squeamish Ossifrage
    Jun 4, 2018 at 18:56
  • $\begingroup$ @SqueamishOssifrage, that is your reading of the question. As poncho says, the question is a bit unclear. $\endgroup$
    – kodlu
    Jun 4, 2018 at 21:29

Your Answer

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

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