5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

From what I understand, you want to share a secret to B in such a way that every single member of B is required to reconstruct the secret. In that case just use a threshold secret sharing scheme where the threshold is the number of players in B. This ensures that no subset of players in B can reconstruct the secret.

I’m not convinced you need encryption here (as secret sharing is already information-theoretically secure. But if you do, then encrypting under public key and sharing to B such that the threshold is equal to the number of shares should suffice.

$\endgroup$
7
  • 1
    $\begingroup$ No, I do want to require every member of B to participate. I also want to avoid transmitting that data from B to A. It doesn't address my main concern. I'll edit the question to elaborate the attack. $\endgroup$ Feb 13 at 16:40
  • $\begingroup$ Thanks for editing, I just read the attack. Why doesn’t A just share its secret in a 3 out of 3 scheme so that all players in B are required to obtain the secret? $\endgroup$
    – hlz2103
    Feb 13 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 13 at 17:50
  • $\begingroup$ A different secret would have a different share so the other players would know to just share once $\endgroup$
    – hlz2103
    Feb 13 at 17:53
  • $\begingroup$ Exactly. There's no way for the other players to know that the shares they received actually open to the secret they wanted to get. By the time you're able to verify that information, it's too late. $\endgroup$ Feb 13 at 17: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.