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

2 Answers 2

1
$\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
1
$\begingroup$

This is a very important problem and in general it is very hard to solve (if you solve it, not only you get a very nice paper but also probably a very relevant real use-case!).

Overall, it seems impossible to solve. To see this, consider the following setting: $n$ parties hold shares of a decryption key, $t$ out of the $n$ parties know nothing about the key, and any $t+1$ of them can jointly reconstruct the key. Suppose an adversary wants to bribe a subset of $t+1$ into selling her the shares, so that the adversary can decrypt messages in the future. In principle, parties may be wary of doing so since there seem to be ways in which the adversary can "change her mind" and expose the fact that these parties accepted bribery! For example, the adversary could expose the logs of their communication. However, there are standard ways to communicate anonymously while satisfying some form of deniability (e.g. Tor). This is bad as this can promote bribing with no consequences.

A small light of hope is that anonymous communications are not enough: the adversary can go to the other non-bribed parties, show them the shares, and they can check that the shares are indeed consistent with what they hold internally, showing that somehow the other bribed parties leaked their shares (even better, they can execute an "equality-check protocol" where the leaked shares are not announced openly). However, even this elaborate approach is not sufficient! Instead of giving out their shares, the bribed parties can run an MPC protocol that only leaks the secret key, without leaking the shares. If the parties do this over anonymous channels, there is no way to accuse them! One might suggest that now the cheater can go somewhere and accuse all of the parties, proving she learned the secret key that was intended to be secret. Maybe she can obtain more reward with this accusation than by, say, decrypting messages secretly. This, also, does not work: the bribed parties can run an MPC protocol that instead of reconstructing the secret to the adversary, simply decrypts ciphertexts of her choice. This way, the adversary holds literally no proof that any party was bribed! All of the communication happened anonymously, and the only trace is the decrypted message, which of course is no proof on its own since anyone can claim to have decrypted a message they initially encrypted themselves.

Some relevant references that study this problem in one way or another:

$\endgroup$
4
  • $\begingroup$ Thank you. If this is possible then I think one can build a "time lock encryption" scheme using smart contracts. The person sending the secret into the future would pay for the service. Key holders would be paid for protecting their secret share until the specific time (or other predetermined condition is met). There would be a reward system for discovering someone's secret early to prevent key holders from revealing their key early. Sarcophagus is a similar project. Not sure how it works. $\endgroup$
    – Alan Reed
    Mar 7 at 3:38
  • $\begingroup$ @AlanReed this also won't work. The main point in my answer is that there is a lot of harm the parties can do without ever exposing their secrets. Again, the idea is to use MPC: if you can convince enough parties to give you an "illegal" or "unauthorized" service (say, reconstructing the secret to you, or a function of the secret), then they can run an MPC protocol so that you only learn that output and nothing else about their individual secrets, effectively protecting them from being accused. $\endgroup$
    – Daniel
    Mar 7 at 16:23
  • $\begingroup$ Here is another solution: Use "trusted" third-parties. blog.cloudflare.com/harnessing-office-chaos $\endgroup$
    – Alan Reed
    Mar 8 at 17:55
  • $\begingroup$ timelock.dev $\endgroup$
    – Alan Reed
    Mar 10 at 18:52

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.