Minimal Message Complexity of Asynchronous Multi-Party Contract Signing

Contract signing protocols deal with the situation where parties wish to sign a publicly-known contract text C, in a fair manner. Informally, fairness means that either every honest party obtains the signature of all the other á−1 parties on C, or none of the parties obtain the signature of any honest party on C. This definition is made precise in the following sections. Deterministic fair contract signing protocols cannot be constructed in asynchronous systems with no presumed trust. One way to circumvent this impossibility is to resort to randomized protocols.