1
$\begingroup$

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.

$\endgroup$
2
3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Also, this needs communication cost analysis, too as Mark did here. $\endgroup$
    – kelalaka
    Dec 20 '21 at 11:18
  • $\begingroup$ 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? $\endgroup$
    – kelalaka
    Dec 20 '21 at 16:04
  • $\begingroup$ @kelalaka Good point, I've elaborated on how the protocol would work to address this issue $\endgroup$
    – knaccc
    Dec 20 '21 at 16:30
  • $\begingroup$ For the $(n, k)$ scheme, a Shamir's Secret Sharing might make more sense than encrypting the secret with $\binom{n}{k}$ keys. $\endgroup$ Dec 21 '21 at 16:29
  • $\begingroup$ @AmanGrewal are you aware of a no-dealer Shamir Secret Sharing protocol that ensures publicly verifiable commitments to each share are known? $\endgroup$
    – knaccc
    Dec 21 '21 at 18:58

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.