Minimal Message Complexity of Asynchronous Multi-party Contract Signing

Sjouke Mauw, Saša Radomirović, Mohammad Torabi Dashti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)
245 Downloads (Pure)

Abstract

Multi-party contract signing protocols specify how a number of signers can cooperate in achieving a fully signed contract, even in the presence of dishonest signers. This problem has been studied in different settings, yielding solutions of varying complexity. Here we assume the presence of a trusted third party that will be contacted only in case of a conflict, asynchronous communication, and a total ordering of the protocol steps. Our goal is to develop a lower bound on the number of messages in such a protocol. Using the notion of abort chaining, a specific type of attack on fairness of signing protocols, we derive the lower bound α 2 + 1, with α > 2 being the number of signers involved. We obtain the lower bound by relating the problem of developing fair signing protocols to the open combinatorial problem of finding shortest permutation sequences. This relation also indicates a way to construct signing protocols which are shorter than state-of-the-art protocols. We illustrate our approach by presenting the shortest three-party fair contract signing protocol.

Original languageEnglish
Title of host publicationProceedings of the 22nd IEEE Computer Security Foundations Symposium
Subtitle of host publicationCSF 2009, 8-10 July 2009 / Port Jefferson, New York, USA
Place of PublicationLos Alamitos
PublisherIEEE Computer Society
Pages13-25
Number of pages13
ISBN (Print)9780769537122
DOIs
Publication statusPublished - 2009
Event22nd IEEE Computer Security Foundations Symposium - Port Jefferson, United States
Duration: 8 Jul 200910 Jul 2009

Publication series

NameProceedings of the IEEE
PublisherIEEE
ISSN (Electronic)1063-6900

Conference

Conference22nd IEEE Computer Security Foundations Symposium
Abbreviated titleCSF 2009
Country/TerritoryUnited States
CityPort Jefferson
Period8/07/0910/07/09

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Minimal Message Complexity of Asynchronous Multi-party Contract Signing'. Together they form a unique fingerprint.

Cite this