3
$\begingroup$

Is there a no-dealer secret sharing scheme that allows a threshold $k$ of $n$ parties (where $k<n$) to collaborate to reconstruct a secret, but in such a way that none of those $k$ parties are able to collaborate anonymously to reconstruct it?

Imagine a scenario where a group of people agree to keep a secret encrypted until a specific time in the future. They can't be prevented from reconstructing the secret early, but can a scheme be devised to prevent them from doing it anonymously? Thus, they will at least fear the consequences of their cheating being exposed by a fellow colluder.

For example, consider a 2 of 3 scheme with Alice, Bob and Charlie. Alice anonymously contacts Bob, in order to cheat and reconstruct the secret early. We need to ensure Alice can't do that without Bob becoming aware that he's communicating with Alice, no matter what scheme Alice proposes.

Even if Alice and Bob both find a way to mutually anonymously get in contact with one another, we need to be sure that both of them will learn the other's identity no matter what scheme is proposed for reconstructing the secret together.

More information about the motivation behind this can be found here: https://www.gwern.net/Self-decrypting-files#distributed-secret-sharing-with-smart-contracts

$\endgroup$
10
  • 2
    $\begingroup$ Can your question be stated as: Is there a no-dealer secret sharing scheme that allows a threshold ๐‘˜ of ๐‘› parties (where ๐‘˜<๐‘›) to collaborate to reconstruct a secret, but in such a way that none of those ๐‘˜ parties are able to collaborate anonymously? $\endgroup$
    – knaccc
    Dec 20, 2021 at 18:50
  • $\begingroup$ Yes, I think that is correct. There needs to be a way to "prove" which Key Holders collaborated. $\endgroup$
    – Alan Reed
    Dec 20, 2021 at 20:11
  • $\begingroup$ Not sure this question makes sense... in a more general context: how can you know that I "used" certain secret? For example, if I get to see an encrypted messages and it turns out I could decrypt it, how can anybody learn this? Only way is by some "outside" information that shows that I somehow used the underlying data, or if I somehow go around showing what I found. With signatures, you could prove I learned a key if you ever see me signing something, but if I don't use the key, I might still know it without anybody being aware of it. $\endgroup$
    – Daniel
    Dec 20, 2021 at 20:37
  • $\begingroup$ If k of n parties are needed to reconstruct the secret, then k parties must communicate some information with someone else in order to reconstruct the secret. Can a secret sharing scheme be created that prevents that communication from being anonymous? $\endgroup$
    – Alan Reed
    Dec 20, 2021 at 21:06
  • $\begingroup$ @AlanReed Again, still unclear. Maybe you can clarify why the following trivial solution does not satisfy what you want? Say I get a signed message from a party and I would like to claim this is their share. I can show it to the other parties and they can run a protocol that checks whether this share is indeed consistent with the underlying secret. If so, the party will be penalized. (PS use @ Daniel---and in general @ username---to get me notified). $\endgroup$
    – Daniel
    Dec 20, 2021 at 21:46

1 Answer 1

0
$\begingroup$

Naive example. I have no background in cryptography.

Let's assume the secret key is 9.

  • Alice has the set { -, 1, 2}
  • Bob has the set { 8, -, 3}
  • Charlie has the set {7, 6, -}

First scenario: Alice requests from Bob his set, Bob can send {8, -, 3} or {8, 3}. Bob will not know who requested the info. Alice will try 1+3, 2+3, 2+8 and 1+8. Alice can decrypt successfully using 8+1=9 and finds out that the anonymous person in Bob.

Second scenario: Alice requests from Bob the value for Alice. Bob will know that Alice has requested the info. Bob will send 8. Alice will try 2+8 and 1+8. Alice decrypts successfully using 8+1=9 and finds out that the anonymous person is Bob.

Edit for kelalaka:

You can use polynomials:

  • Alice has 3 polynomials: A1(x)=331+317X, A2(x)=331+333x, A3(x)=331+353x;
  • Bob has 3 polynomials: B1(x)=363+369x, B2(x)=363+383x, B3(x)=363+399x;
  • Charlie has 3 polynomials: C1(x)=421+419x, C2(x)=421+435x, C3(x)=421+443x;
  • The secret key is 331 + 363 + 421 = 1115.

Keys for Alice and Bob:

  • Alice will calculate A1(1)=648 and A1(2)=965. Alice will send 965 to Bob.
  • Bob will calculate B1(1)=732 and B1(2)=1101. Bob will send 732 to Alice.
  • Charlie will calculate C1(1)=840 and C1(2)=1259. Charlie will send 840 to Alice and 1259 to Bob.
  • Alice will add 648 + 732 + 840 = 2220. Alice key is (1, 2220).
  • Bob will add 965 + 1101 + 1259 = 3325. Bob key is (2, 3325).

Keys for Alice and Charlie:

  • Alice will calculate A2(1)=664 and A2(3)=1330. Alice will send 1330 to Charlie.
  • Bob will calculate B2(1)=746 and B2(3)=1512. Bob will send 746 to Alice and 1512 to Charlie.
  • Charlie will calculate C2(1)=856 and C2(3)=1726. Charlie will send 856 to Alice.
  • Alice will add 664 + 746 + 856 = 2266. Alice key is (1, 2266).
  • Charlie will add 1330 + 1512 + 1726 = 4568. Charlie key is (3, 4568).

Keys for Bob and Charlie:

  • Alice will calculate A3(2)=1037 and A3(3)=1390. Alice will send 1037 to Bob and 1390 to Charlie.
  • Bob will calculate B3(2)=1161 and B3(3)=1560. Bob will send 1560 to Charlie.
  • Charlie will calculate C3(2)=1307 and C3(3)=1750. Charlie will send 1307 to Bob.
  • Bob will add 1037 + 1161 + 1307 = 3505. Bob key is (2, 3505).
  • Charlie will add 1390 + 1560 + 1750 = 4700. Charlie key is (3, 4700).

If Bob and Charlie exchange keys:

  • Bob has (2, 3505) for Charlie;
  • Charlie has (3, 4700) for Bob;
  • 4700 - 3505 = 1195;
  • 3505 - 2*1195 = 1115 -> secret key;
  • 4700 - 3*1195 = 1115 -> secret key;

If Charlie tells Bob that he is Alice:

  • Bob has (2, 3325) for Alice;
  • Charlie has (3, 4568) for Alice and (3, 4700) for Bob;
  • 4568 - 3325 = 1243;
  • 4700 - 3325 = 1375;
  • 3325 - 2*1243 = 839 -> ERROR
  • 4568 - 3*1243 = 839 -> ERROR
  • 3325 - 2*1375 = 575 -> ERROR
  • 4700 - 3*1375 = 575 -> ERROR

You can add discrete logarithm for PVSS (Publicly Verifiable Secret Sharing).

$\endgroup$
1
  • $\begingroup$ The OP ask no dealer. How did they get the shares? $\endgroup$
    – kelalaka
    Oct 5, 2023 at 6:46

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.