4
$\begingroup$

Alice and Bob publicly choose the messages $M_A$ and $M_B$ and independently sign them (Alice privately signs $M_A$, Bob signs $M_B$).

Now Alice and Bob are looking for a protocol that allows them to:

  1. Make sure the other party's signature is valid (in a malicious adversary model)

  2. Only reveal their own signature if they're guaranteed by the protocol to learn the other party's signature as well (atomic reveal)

  3. Not rely on a trusted dealer

Is there such a protocol possible to construct? Can it be extended to N parties instead of 2? Can it work with an ECDSA signature scheme?

Edit: After researching the topic more and thanks to the answers below, I found out this is commonly known as a (strong) fair-exchange protocol and it's impossible in the two-party setup without a trusted third party. However, optimistic fair exchange protocols are possible and they only rely on a trusted party if one of the participants attempts to cheat.

Improve this question
$\endgroup$
1
  • $\begingroup$ What's your adversary model: are parties malicious or honest-but-curious? $\endgroup$
    – Dragos
    Commented Aug 8, 2018 at 14:43

2 Answers 2

Reset to default
3
$\begingroup$

I believe this impossible. (Edit: Major edit below)

Let's assume this is implemented by Alice and Bob sending messages to each other, how many messages would it take.

We will show if it is possible with n messages then it must be possible with n-1.

If it is possible with n messages, without loss of generality let the last message be from Alice to Bob . At this point Alice no longer receives any information so she must have already everything she needs to reveal, she may therefor choose not to send the last message. If Bob is still able to reveal as well then it is possible to solve with n-1 messages.

Via induction it is possible with 0 messages which is obviously impossible.

Edit: My above answer is technically correct. Which is the worst kind of lie. As Dragos and Alpha Baravo point out, there is a lot of literature on fair exchange protocols.

So How do we work around the impossibility? Several options but the one which I believe matches most closely the question is to be more flexible with what it means to have everything needed to reveal.

The proof assumes you either can or can not reveal while in reality once you have a commitment you can reveal the underlying with enough computation. If we put a hard threshold on computational ability the above proof stands.If we make a weaker requirement, if Alice can reveal with some amount of work Bob can reveal without much more work the problem becomes solvable:

Each side has a random key protecting what is to be revealed, each side supplies a Zero Knowledge proof of having such a key. The keys are gradually revealed, each time with ZK proof the prefix is correct. If the proof doesn't pan out in one iteration the first diverging party has only a limited advantage in brute forcing the remaining key.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Spot on! This proves the impossibility of a larger definition of the problem, when Alice and Bob would attempt to atomically reveal a secret to each other. $\endgroup$
    – Lucian Boca
    Commented Aug 8, 2018 at 16:11
  • 1
    $\begingroup$ I think the answer is incorrect for n parties, partly because it contradicts a result saying that fairness (which is what the OP is looking for) can be achieved if we assume an honest majority of parties - see the debate on fairness and output delivery here: eprint.iacr.org/2014/668 $\endgroup$
    – Dragos
    Commented Aug 8, 2018 at 16:18
  • $\begingroup$ The proof above holds, There are many fair exchange protocols, each with their own compromise to work around the above impossibility, some might be reasonable. For example if we gradually reduce the work required to reveal with iterated exchanges. $\endgroup$
    – Meir Maor
    Commented Aug 8, 2018 at 17:05
4
$\begingroup$

This can be achieved using fair exchange protocols, which seek to ensure that either Alice and Bob both get what they want or neither of them does.

Improve this answer
$\endgroup$

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.