[Cryptography] Proposal of a fair contract signing protocol

mok-kong shen mok-kong.shen at t-online.de
Wed Jun 22 20:03:58 EDT 2016


Am 22.06.2016 um 22:54 schrieb Ron Garret:
>
> On Jun 22, 2016, at 12:06 PM, Jon Callas <jon at callas.org> wrote:
>
>> Signed PGP part
>> I apologize in advance if I'm being clueless on some piece of this, because I have *not* spent enough time to thoroughly understand Mok-Kong's protocol. (Furthermore, I have picky questions that I don't know if they're relevant about parts the protocol, like what properties should "signcryption" have?)
>>
>> But anyway...
>>
>> There are plenty of unsolvable problems that you can solve is useful ways. Yeah, they're "limited" but they're often limited to the real world and often because the full problem is unsolvable.
>>
>> For example, it's often completely reasonable to solve the halting problem by setting a timeout. Split-brain problems are solved all the time with a quorum system. You can solve the Generals/Agreement problems either by allowing it to go a wait state or declaring an exit condition, etc. In short, these unsolvable problems are solvable when you put in an escape valve that says that when you get into the unsolvable state, you declare a solution.
>>
>> Mok-Kong has this note at the end of the protocol:
>>
>>    Note that after step (2) Alice cannot innocently refuse to perform
>>    step (3), since the pair (X,Y) stems from her. In other words, after
>>    step (2) the contract is de facto completed.
>>
>> To me, it appears that "de facto completed" means there's an escape valve. If the protocol says that Alice does X, Bob does Y, and Alice is supposed to do Z, but if she doesn't, tough -- then the protocol terminates.
>>
>> Of course, this might be unsatisfactory on some level and there may need to be software duct tape and chicken wire to make it work. But it sounds to me like there's the escape clause here.
>>
>> Am I right or not?
>
> Not.
>
> Here is Mok-Kong’s problem statement:
>
>> 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.
>
> Mok-Kong’s claim is that his protocol is *fair* in the sense that there is never a time when Alice is committed and Bob isn’t, or vice-versa.  But this cannot possibly be the case if Alice and Bob’s actions are interleaved in time and there is no trusted third party.
>
> This is not quite the same as the two-generals problem.  The 2G problem is solvable if you have reliable communications.  The fair commitment problem is not solvable even with reliable communications.
>
> Proof by reductio: assume that the problem is solvable, i.e. there is some sequence of interleaved actions taken by A and B that results in fair commitment, i.e. at some point there is some key action K where neither A or B are committed before the action but both are committed after.  Since actions are interleaved, K must be performed either by A or by B.  Let us assume WOLOG that K is performed by A.  A, by assumption, is uncommitted before performing K, and so can choose to perform K or not.  But B can no longer make this choice.  B’s commitment (or lack thereof) hinges entirely on a choice made by A.  Therefore the protocol cannot be fair.

Allow me anyway an attempt to counter-argue. Would you please point
out what's defective in my thought below?

If the contract C is as such directly to be signed and Alice and Bob
are to sign it online, then it is naturally the case that both
signatures couldn't be done at the same moment and consequently the
unfairness occurs. What the virtual cryptography does is to split C
into two pieces X and Y to be signed. Alice initiates the signing
process through first signing only X, but promises to sign Y in case
Bob signs both X and Y. As long as Bob's action is not done, Alice has
not signed C. That's trivial. After Bob signs X and Y, Alice must sign
Y within a time period TP, for otherwise she would have broken her
promise. Thus either C never comes into being, or C becomes valid in
step 3 but there is no time point in the entire processing where one
party is commited to C while the other party has the freedom to commit
to C or not. Isn't this sufficient to consider the protocol to be fair?

M. K. Shen



More information about the cryptography mailing list