mjhjmtu

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.

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.

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.