4 ms·

This is a wonderfully simple scheme to split up keys between parties, but this still involves a party (the one that made the key) at some point knowing the key.

This is a wonderfully simple scheme to split up keys between parties, but this still involves a party (the one that made the key) at some point knowing the key. This scheme implies you trust this distributor not to make copies of the key for himself (queue sauron references...). I've wondered if there's a scheme that does NOT trust the distributor of the key. What if the only time they key was known was when the parties reached quorum after the fact?

thehumanmeat 4y ago
Plenty. Look into publicly verifiable secret sharing. https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sharing https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sha...
- anonymousDan 4y ago
  That doesn't seem to answer the question - the schemes on your link still have a dealer with access to the original secret I think? Is it possible to have each participant contribute an input that forms part of the original secret, such that they get combined to form the secret and then split into shares in a way that doesn't require a dealer?
  - lrvick 4y ago
    See my other comment in this thread which details a solution to this.
anonymousDan 4y ago
Interesting question. Are there any restrictions on the relationship between t and n, i.e. can I have 1 <= t <= n? I had a thought for solving your problem but it might not work for arbitrary t.
jbergknoff 4y ago
Yes, there are threshold cryptography schemes with "distributed key generation" [1] in which the parties end up holding shares but the full secret is never known to any party. Then, to your point about "the only time they key was known was when the parties reached quorum after the fact": in these schemes, some threshold of the parties can cooperate to compute a function of the secret (e.g. a signature, or a ciphertext) without any of them ever knowing the secret. FROST is one example of such a threshold scheme, for computing Schnorr signatures: https://eprint.iacr.org/2020/852.pdf https://eprint.iacr.org/2020/852.pdf [1] https://en.wikipedia.org/wiki/Distributed_key_generation https://en.wikipedia.org/wiki/Distributed_key_generation
- h0h0h0h0111 4y ago
  A similar scheme we use in drand is this: https://www.researchgate.net/publication/225722958_Secure_Distributed_Key_Generation_for_Discrete-Log_Based_Cryptosystems https://www.researchgate.net/publication/225722958_Secure_Di...
jesper_br 4y ago
You can do that using Multi Party Computation. There are a bunch of MPC protocols for generating Eliptic Curve private keys and doing DSA where the whole private key is never assembled. It uses Shamir Sharings as part of the magic, it's quite neat :)
plopilop 4y ago
Sure. One example is as follows: each party i generates a random polynomial P_i, and n secret shares of that polynomial (j, P_i(j)) for j in 1..n Then, party i sends (j, P_i(j)) to party j. Party i similarly receives shares (i, P_j(i)) for j=1..n. Party i stores the share (i, sum(P_j(i))). Then, parties reveal their shares as usual, the secret is then the sum_i P_i(0). Of course, if the parties are dishonest, you might want some additional safety mechanisms, which can be dealt with with Kate commitments. This papers https://eprint.iacr.org/2020/504.pdf https://eprint.iacr.org/2020/504.pdf goes into details, and much more.
gnarula 4y ago
Refer: https://github.com/dedis/kyber/blob/master/share/vss/rabin/vss.go https://github.com/dedis/kyber/blob/master/share/vss/rabin/v... and https://github.com/dedis/kyber/blob/master/share/vss/pedersen/vss.go https://github.com/dedis/kyber/blob/master/share/vss/pederse...
lrvick 4y ago
I build systems designed to distrust any single individual with cryptographic key material and SSSS needs a lot of careful handling and automation to accomplish this. Splitting the key safely is only part of the problem though, because you will then need a system that only -uses- the key in a way all parties consent to. Threshold signing is a much easier alternative for many use cases but sometimes a cryptosystem requires just one key and SSSS is all we can do. To avoid any single party accessing a complete SSSS split key you can: 1. Write an application that takes N public keys as input, and returns a newly generated key as SSSS shares encrypted to each respective public key as output. 2. Compile application deterministically as an immutable unikernel or firmware image targeting hardware that supports remote attestation (Nitro Enclave, Confidential VM, HSM, etc). 3. Publish source code such that all participants can access and review it, or confirm review was done by multiple parties they trust. 4. Have multiple parties trusted by all participants, or the participants themselves, build the application bundle and confirm they get the same hash 5. Any party deploys the bundle to a live remotely attestable system. 6. All parties use the remote attestation interface to confirm the target system is running the multi-party deterministically compiled application they expect. 7. All parties submit their public keys to the remote system. 8. The remote system generates new key, splits it, and returns SSSS shares to each party encrypted to their respective public key.
- generalizations 4y ago
  > This scheme implies you trust this distributor not to make copies of the key for himself (queue sauron references...). I've wondered if there's a scheme that does NOT trust the distributor of the key. What you describe still trusts the distributor - you just found a way to make the distributor easy to trust. I'd be more interested in a mechanism that is mathematically correct, like some of the papers referenced elsewhere in this thread.
  - lrvick 4y ago
    Even if you avoid trusting the distributor, the quorum of share holders still will end up having to reconstitute the shared key into the memory of a computer somewhere at some point to do cryptographic operations with it. There is no avoiding standing up computers all parties trust and if you are going to do that anyway then you might as well use them for key generation and distribution too.
chinchilla2020 4y ago
I have done this with other parties by brute force for crypto. You usually have a ring of people and need 3 out of the 7 to open the box. You simply encrypt the box in whatever combinations you want, and people run their keys against each layer of the box. You end up with a few different files but in the case of keys, and a small number of sharers this is not going to be a big data issue.

thehumanmeat 4y ago

Plenty. Look into publicly verifiable secret sharing. https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sharing https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sha...

anonymousDan 4y ago
That doesn't seem to answer the question - the schemes on your link still have a dealer with access to the original secret I think? Is it possible to have each participant contribute an input that forms part of the original secret, such that they get combined to form the secret and then split into shares in a way that doesn't require a dealer?
- lrvick 4y ago
  See my other comment in this thread which details a solution to this.

anonymousDan 4y ago

Interesting question. Are there any restrictions on the relationship between t and n, i.e. can I have 1 <= t <= n? I had a thought for solving your problem but it might not work for arbitrary t.

jbergknoff 4y ago

Yes, there are threshold cryptography schemes with "distributed key generation" [1] in which the parties end up holding shares but the full secret is never known to any party. Then, to your point about "the only time they key was known was when the parties reached quorum after the fact": in these schemes, some threshold of the parties can cooperate to compute a function of the secret (e.g. a signature, or a ciphertext) without any of them ever knowing the secret. FROST is one example of such a threshold scheme, for computing Schnorr signatures: https://eprint.iacr.org/2020/852.pdf https://eprint.iacr.org/2020/852.pdf [1] https://en.wikipedia.org/wiki/Distributed_key_generation https://en.wikipedia.org/wiki/Distributed_key_generation

h0h0h0h0111 4y ago
A similar scheme we use in drand is this: https://www.researchgate.net/publication/225722958_Secure_Distributed_Key_Generation_for_Discrete-Log_Based_Cryptosystems https://www.researchgate.net/publication/225722958_Secure_Di...

jesper_br 4y ago

You can do that using Multi Party Computation. There are a bunch of MPC protocols for generating Eliptic Curve private keys and doing DSA where the whole private key is never assembled. It uses Shamir Sharings as part of the magic, it's quite neat :)

plopilop 4y ago

Sure. One example is as follows: each party i generates a random polynomial P_i, and n secret shares of that polynomial (j, P_i(j)) for j in 1..n Then, party i sends (j, P_i(j)) to party j. Party i similarly receives shares (i, P_j(i)) for j=1..n. Party i stores the share (i, sum(P_j(i))). Then, parties reveal their shares as usual, the secret is then the sum_i P_i(0). Of course, if the parties are dishonest, you might want some additional safety mechanisms, which can be dealt with with Kate commitments. This papers https://eprint.iacr.org/2020/504.pdf https://eprint.iacr.org/2020/504.pdf goes into details, and much more.

gnarula 4y ago

Refer: https://github.com/dedis/kyber/blob/master/share/vss/rabin/vss.go https://github.com/dedis/kyber/blob/master/share/vss/rabin/v... and https://github.com/dedis/kyber/blob/master/share/vss/pedersen/vss.go https://github.com/dedis/kyber/blob/master/share/vss/pederse...

lrvick 4y ago

I build systems designed to distrust any single individual with cryptographic key material and SSSS needs a lot of careful handling and automation to accomplish this. Splitting the key safely is only part of the problem though, because you will then need a system that only -uses- the key in a way all parties consent to. Threshold signing is a much easier alternative for many use cases but sometimes a cryptosystem requires just one key and SSSS is all we can do. To avoid any single party accessing a complete SSSS split key you can: 1. Write an application that takes N public keys as input, and returns a newly generated key as SSSS shares encrypted to each respective public key as output. 2. Compile application deterministically as an immutable unikernel or firmware image targeting hardware that supports remote attestation (Nitro Enclave, Confidential VM, HSM, etc). 3. Publish source code such that all participants can access and review it, or confirm review was done by multiple parties they trust. 4. Have multiple parties trusted by all participants, or the participants themselves, build the application bundle and confirm they get the same hash 5. Any party deploys the bundle to a live remotely attestable system. 6. All parties use the remote attestation interface to confirm the target system is running the multi-party deterministically compiled application they expect. 7. All parties submit their public keys to the remote system. 8. The remote system generates new key, splits it, and returns SSSS shares to each party encrypted to their respective public key.

generalizations 4y ago
> This scheme implies you trust this distributor not to make copies of the key for himself (queue sauron references...). I've wondered if there's a scheme that does NOT trust the distributor of the key. What you describe still trusts the distributor - you just found a way to make the distributor easy to trust. I'd be more interested in a mechanism that is mathematically correct, like some of the papers referenced elsewhere in this thread.
- lrvick 4y ago
  Even if you avoid trusting the distributor, the quorum of share holders still will end up having to reconstitute the shared key into the memory of a computer somewhere at some point to do cryptographic operations with it. There is no avoiding standing up computers all parties trust and if you are going to do that anyway then you might as well use them for key generation and distribution too.

chinchilla2020 4y ago

I have done this with other parties by brute force for crypto. You usually have a ring of people and need 3 out of the 7 to open the box. You simply encrypt the box in whatever combinations you want, and people run their keys against each layer of the box. You end up with a few different files but in the case of keys, and a small number of sharers this is not going to be a big data issue.