Score:1

Split prvate key without Private Key Holder knowing the key shards?

kz flag

Is is possible to split a private key into shards and distribute the shards to Key Holders such that (1) k of n key shards are required to recover the private key and (2) the private key holder does not know what the key shards are?

I am thinking about a situation where a number of Key Holders are trusted to keep their key shard secret. Then if a key shard is leaked we want to know which Key Holder to blame. In this scenario, if the original private key holder also knows the key shards then we can't know who leaked the key shard.

Alan Reed avatar
kz flag
The point of re-constructing the private key would be to decrypt a secret that was previously encrypted. Not looking for multi-sig signing scheme.
kelalaka avatar
in flag
the keyword is [no dealer](https://crypto.stackexchange.com/search?q=%5Bsecret-sharing%5D+no+dealer), like this one [Shamir secret sharing with no dealer](https://crypto.stackexchange.com/q/84143/18298) and this one [Secret sharing - no dealer, modifiable, verifiable](https://crypto.stackexchange.com/q/13185/18298)
Score:3
es flag

Let $E$ be a secure elliptic curve, and $G$ is the basepoint with order $\ell$.

  • $(n,n)$ scheme:

    $n$ key holders each randomly pick a private key $x_i$, compute a public key $X_i = [x_i]G$ and a hash commitment $H(X_i)$.

    The key holders first exchange hash commitments, and only when all hash commitments have been shared do they then share their public keys with each other.

    The secret is then encrypted using ECIES with the joint public key $\sum_{i=1}^n X_i$.

    The secret can then only be decrypted if all key holders get together to combine their private keys to establish the joint private key $$\sum_{i=1}^n x_i \bmod \ell$$ corresponding to the joint public key.

    If anyone leaks their private key, it can easily be observed which public key that private key correlates to.

  • $(n,k)$, $k$-threshold scheme:

    For each possible choice of $k$ of $n$ private keys (the number of total possibilities will be the binomial coefficient$\binom{n}{k}$), encrypt the secret with a joint public key formed by the summation of that combination of public keys.

A coordinator can be used in order to reduce the number of communications required between parties. All messages sent to the coordinator need to be signed by each private key holder's well-established general communications public key (this is not the same public key as the one generated for each private key holder during this scheme). Relayed information (such as relayed commitments and relayed public keys) will retain the signature of the party that produced it, so that recipients do not have to trust the coordinator.

The key agreement stage of the protocol would require a total of $5n$ communications as follows:

  1. The coordinator generates a message $m$ containing a nonce which identifies this particular invocation of the protocol, and sends $m$ to each private key holder. All communications transmitted by any party after this point must include $m$ so that communications cannot be mixed and matched between invocations of the protocol. All private key holders must remember each nonce used, in order to avoid providing two different responses for the same nonce value (at the same stage of the protocol).

  2. All private key holders send their commitments to the coordinator

  3. The coordinator transmits the collection of commitments to each private key holder

  4. Each private key holder transmits their public key to the coordinator

  5. The coordinator transmits the collection of public keys to each private key holder.

When the secret holder is ready to encrypt a secret, it will be encrypted with the joint public key and transmitted to all $n$ private key holders, thus requiring a further $n$ communications. As with all prior steps, the message $m$ containing the nonce is included in order to bind this communication to this particular invocation of the protocol.

kelalaka avatar
in flag
Also, this needs communication cost analysis, too as [Mark did here](https://crypto.stackexchange.com/a/84214/18298).
kelalaka avatar
in flag
In this case, your scheme has a trusted center. If you look at Mark's answer until the secret key is needed for construction there is no secret holder. All holders are the same. This requires distributing all commits... Doesn't this contradict your first (n,n)-scheme?
knaccc avatar
es flag
@kelalaka Good point, I've elaborated on how the protocol would work to address this issue
Aman Grewal avatar
gb flag
For the $(n, k)$ scheme, a Shamir's Secret Sharing might make more sense than encrypting the secret with $\binom{n}{k}$ keys.
knaccc avatar
es flag
@AmanGrewal are you aware of a no-dealer Shamir Secret Sharing protocol that ensures publicly verifiable commitments to each share are known?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.