23
$\begingroup$

Let's say that there is a message which is considered valid if signed by both Alice and Bob.

Alice could sign the message and then give it to Bob, so that he can sign it and give it back to her.

But, for various reasons, Alice doesn't want Bob to have a fully-signed message that she doesn't also have. If she just signs it and sends it, he could sign it and not send it back.

Is there some way that both of them can sign the message (maybe interactively?) so that it doesn't become valid for Bob if it isn't also valid for Alice?

(This could be done by a trusted third party who would simply escrow the message until it had received both signatures, and then release both signatures to Alice and Bob. Of course, I want a solution without a third party.)

$\endgroup$
  • 1
    $\begingroup$ Look into fair contract signing protocols. $\endgroup$ – DrLecter Jun 4 '16 at 6:34
16
$\begingroup$

This is one of the earliest questions that was asked in modern cryptography. There is a proof that you cannot achieve completely fair contract signing. However, there are some reasonable alternatives. There is one direction called "gradual release" which I personally do not like. A model that I think has a lot of promise is called the "optimistic model". In this model, there is a trusted third server that is only invoked in case one of the parties cheats and may obtain a signature without the other. This model is very nice in the sense that once the server exists, there is no motivation to cheat since anyway an adversary knows that it cannot gain anything. I note that the server is trusted to answer when a party asks for its "help", but does not learn anything. This model was introduced by Silvio Micali in Fair Electronic Exchange with Invisible Trusted Parties. You can read more about this model in Optimistic Fair Secure Computation by Cachin and Camenisch, and Analysis of a Fair Exchange Protocol by Shmatikov and Mitchell.

Another direction which I really like is called Concurrent Signatures. In this model, one party gets the signature first. However, if the other party sees the signature then it can use that to complete its own signature. So, it's actually not fair (one has the signature first) but if the first ever wants to enforce anything with its signature then it would have to show it to the second, in which case the second can complete the signature it is supposed to receive. In most practical cases that I can think of this is sufficient, and it elegantly bypasses the impossibility results that exist. This model has the advantage that you don't need a (minimally) trusted third party (which is problematic in practice).

Finally, I'll point to the recent use of Bitcoin to ensure fairness. The paper How to Use Bitcoin to Design Fair Protocols shows how to do this (albeit theoretically). The idea here is very very nice.

$\endgroup$
  • 1
    $\begingroup$ Very interesting. I will read through this stuff. Incidentally, I'm asking this because we are using such a system for payment channels, which sound a lot like the fair exchange thing: altheamesh.com/documents/universal-payment-channels.pdf $\endgroup$ – Jehan Jun 5 '16 at 17:25
  • $\begingroup$ I am certainly confused. Isn't what you describe as "concurrent signatures" in essence exactly the same as the 2nd sentence of OP (a scenario which OP wished to be eventually able to avoid)? $\endgroup$ – Mok-Kong Shen Jun 6 '16 at 7:20
  • $\begingroup$ No, the scenario you want to avoid is where Alice signs and sends to Bob and then Bob doesn't send back. If Bob refuses to sign back then Alice can never get the signature. In concurrent signatures, even if Bob doesn't answer, the signature he holds actually contains the information that Alice needs in order to complete the signature she is supposed to receive. It's a bit confusing, so best to read the paper. $\endgroup$ – Yehuda Lindell Jun 6 '16 at 7:22
  • $\begingroup$ Thanks. I have another question: With visual cryptography a document could be separated into two pieces such that both are needed in order to obtain the original, if I don't err. Would letting Alice and Bob each to sign a different piece of the pair work fine for the present purpose or are there on the contrary defects, risks and serious problems? $\endgroup$ – Mok-Kong Shen Jun 6 '16 at 13:30
  • $\begingroup$ If you need them to physically be in the same room to get the signature together then this works, but then there are much more simple solutions for that case. $\endgroup$ – Yehuda Lindell Jun 6 '16 at 13:32
0
$\begingroup$

When a contract in digital from is to be signed online by Alice and Bob, an issue concerning the fairness of the signing process crops up as follows: If Alice first signs the document and sends it to Bob, it means she has committed to something (e.g. ready to purchase an article from Bob at a certain price), Bob can however, if he desires, to some extent delay giving his digital signature and thus have a certain finite time interval during which he has no corresponding commitment. This is obviously unfair and hence to be avoided, if possible.

Noting that with visual cryptography a document can be separated into two pieces such that they jointly can reproduce the original but neither piece alone provides any information of the document, we propose the following protocol which well fulfills the requirements of fairness in the present context.

In the following the convention is that signed(A, U) denotes U (as a single piece) digitally signed by A and that A thereby commits to U and that nothing else, e.g. simply a V in a message which as a whole is signed, has the meaning of a commitment.

Step 1: Alice formulates a contract document C, generates with visual cryptography a pair (X, Y), sends a message containing signed(Alice,X) and Y to Bob and asks him to accept C before a certain day T in the future and promises to complete the contract formality within a certain time period TP in case Bob commits to C in step 2.

Step 2: Bob obtains C from (X, Y). If he can't accept C, he informs Alice and the protocol begins again at step 1. Otherwise he sends a message containing signed(Bob,X) and signed(Bob,Y) to Alice and asks her to release C. (If Bob does nothing before T is reached, the protocol begins again at step 1.)

Step 3: Alice examines whether Bob has signed the correct stuff, i.e. whether he hadn't e.g. by mistake sent signed(Bob,Z) in place of signed(Bob,X) with Z != X. If Bob had signed the wrong stuff, she informs Bob and the protocol begins again at step 1. Otherwise she releases C, signed(Alice,X), signed(Alice,Y), signed(Bob,X) and signed(Bob,Y) to the public. (Alice is responsible to complete step 3 within TP.)

The messages of step 1 and 2 are to be sent with signcryption, i.e. encrypted with reciever's public key and signed by the sender, and with authentication (integrity check). Receipt acknowledgments are to be requested for resolving eventual timing issues.

Note that:

(a) In step 1 Alice has not committed to C. Thus there can be no unfairness of the nature mentioned above.

(b) If Bob commits to C in step 2, then Alice is immediatly obliged to commit to C as well, since the pair (X, Y) stems from herself (hence she couldn't eventually claim that C corresponds to (X, Z) with Z != Y). That is, C is virtually already a valid document. Hence there can be also here no unfairness of the nature mentioned above.

(c) Our protocol doesn't involve/need any trusted third party, which is an advantage.

[Edited 18.06.2016]

[Addendum 19.06.2016] There are literatures wich claim (if I have not misinterpreted) that protocols of our genre are impossible. My humble knowledge is unfortunately insufficient to study them in details so as to resolve the apparent contradiction between our result and the impossibility claims. Readers interested in probing the causes of that contradiction may eventually desire to read a paper by H. Pagnia and F. C. Gaertner of 1999 entitled "On the Impossibility of Fair Exchange without a Trusted Third Party" which is however currently not online accessible from the institution where the paper was originally published. In that case I could send over a copy. (My address: mok-kong.shen@t-online.de)

$\endgroup$
  • $\begingroup$ I don't see how your protocol gets around the fundamental impossibility proof cited by Yehuda Lindell. In particular, if all four signatures (signed(Alice,X), signed(Alice,Y), signed(Bob,X) and signed(Bob,Y)) are needed for the document to be considered signed, then Alice can cheat in step 3 and keep signed(Alice,Y) to herself; if signed(Alice,Y) is optional, then Bob can do the same in step 2 and keep both of his signatures to himself. Either way, one of the parties ends up with a valid, usable signature while the other one does not. $\endgroup$ – Ilmari Karonen Jun 17 '16 at 7:16
  • $\begingroup$ I worte that after Bob commits, Alice is obliged to commit to Y, because the pair(X,Y) stems from her herself (she couldn't now say that the document corresponds to (X,Z)). Isn't that clear? $\endgroup$ – Mok-Kong Shen Jun 17 '16 at 14:15
  • $\begingroup$ @IlmariKaronen: Addendum to my above comment: I guess that the "fundamental impossibility proof" might have assumed something additionally in comparison to my scheme or there was an error in it somewhere. $\endgroup$ – Mok-Kong Shen Jun 17 '16 at 14:29
  • 1
    $\begingroup$ Yes. ​ Adversarial-Alice performs step 1 honestly, receives the Step 2 message from Bob, and then doesn't send anything else. ​ Now the adversary has [X,Y,signed(Bob,X),signed(Bob,Y)], which the signature verification algorithm presumably accepts as a signature of C, but Bob does not have anything that the signature verification algorithm accepts as a signature of C (if I understand your proposed signature verification algorithm correctly). ​ ​ ​ ​ $\endgroup$ – user991 Jun 21 '16 at 3:03
  • 2
    $\begingroup$ No, since adversaries are perfectly capable of breaking promises. ​ ​ $\endgroup$ – user991 Jun 21 '16 at 18:26

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.