# Secure Secret Sharing to a Distributed Key

Setup

There are two groups, $$A$$ and $$B$$. Each group is in a Shamir's secret sharing scheme ($$t_A$$ of $$N_A$$ and $$t_B$$ of $$N_B$$). Each group has a public key that is associated with the identity of the group. The corresponding private keys are distributed among the members and are never reconstructed on any device. Each group has additional secrets as well. Every member has its own public/private key.

Problem

$$A$$ wants to share a secret to $$B$$, without reconstructing it and (assuming a threshold number of members in $$B$$ aren't compromised) without $$B$$ being able to reconstruct it.

If $$A$$ knows the scheme and the members of $$B$$, this is straightforward. $$A$$ performs a redistribution (like the one described in Verifiable Secret Redistribution for Archive Systems by Wong, Wang, and Wing), encrypting shares for each member in $$B$$. However, this is annoying because everytime the members or scheme of $$B$$ changes, $$A$$ needs to be informed of it.

Instead, $$A$$ can encrypt shares with $$B$$'s public key. In this case, how do the members of $$B$$ know that no member of $$B$$ can gain access to secret?$$^1$$

More concretely, there needs to be a group decryption operation for each share, with each decrypted share being available to a different member, such that no other member can see it.$$^2$$ The issue is assigning shares to different members in a way that replay attacks won't work, i.e., the entire protocol starting over with the same or a different set of $$t_B$$ members.

Replay Attack 1

Imagine a simple situation where $$B$$ is in a 2-of-3 scheme. Call the members $$b_1$$, $$b_2$$, and $$b_3$$. $$A$$ provides two shares in a 2-of-2 scheme, both encrypted with $$B$$'s public key. $$b_1$$ initiates the protocol with $$b_1$$ and $$b_2$$, gaining access to share 1. $$b_1$$ then initiates the scheme with $$b_1$$ and $$b_3$$, gaining access to share 2. So now $$b_1$$ knows the full secret without either $$b_2$$ or $$b_3$$ having approved of it.

Replay Attack 2

Now imagine a situation where $$B$$ is in a 2-of-2 scheme. $$b_1$$ initiates the protocol with $$b_2$$, getting access to share 1. $$b_1$$ initiates the protocol again, but this time gets access to share 2. In this application, the member initiating the protocol is the one who has access to the encrypted shares. The initiator provides the data to the other members, who do not have an independent way to get that data from $$A$$.

$$^1$$ More precisely, the honest members of $$B$$ don't want any group with fewer than $$t_B$$ members to be able to collude together to get the secret.

$$^2$$ This is a simplification. Since $$A$$ doesn't know $$t_B$$, members may end up with multiple shares. This is fine. I'm also assuming there's a max value $$t_B$$ can take that $$A$$ can share to, so that at the end of all the decryptions, there's no group of fewer than $$t_B$$ members that can reconstruct the secret.

• It still doesn't help. $b_1$ can initiate the protocol three times, ensuring that it gets each share. Having $b_2$ or $b_3$ keep track of what they've approved doesn't work because each time $b_1$ can claim that they're trying to open a different secret. Feb 13, 2021 at 17:50