Minimal Message Complexity of Asynchronous Multi-party Contract Signing

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

doi:10.1109/CSF.2009.15

Minimal Message Complexity of Asynchronous Multi-party Contract Signing

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

Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

22 Citations (Scopus)

294 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 α ² + 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 language	English
Title of host publication	Proceedings of the 22nd IEEE Computer Security Foundations Symposium
Subtitle of host publication	CSF 2009, 8-10 July 2009 / Port Jefferson, New York, USA
Place of Publication	Los Alamitos
Publisher	IEEE Computer Society
Pages	13-25
Number of pages	13
ISBN (Print)	9780769537122
DOIs	https://doi.org/10.1109/CSF.2009.15
Publication status	Published - 2009
Event	22nd IEEE Computer Security Foundations Symposium - Port Jefferson, United States Duration: 8 Jul 2009 → 10 Jul 2009

Publication series

Name	Proceedings of the IEEE
Publisher	IEEE
ISSN (Electronic)	1063-6900

Conference

Conference	22nd IEEE Computer Security Foundations Symposium
Abbreviated title	CSF 2009
Country/Territory	United States
City	Port Jefferson
Period	8/07/09 → 10/07/09

ASJC Scopus subject areas

General Engineering

Access to Document

10.1109/CSF.2009.15

Author Accepted Manuscript
© 2009 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 144 KB

Cite this

@inproceedings{2524647601d044c0ab4ecdbac190520f,

title = "Minimal Message Complexity of Asynchronous Multi-party Contract Signing",

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.",

author = "Sjouke Mauw and Sa{\v s}a Radomirovi{\'c} and Dashti, {Mohammad Torabi}",

note = "M. Torabi Dashti has been partially supported by the FP7-ICT-2007-1 Project no. 216471, “AVANTSSAR: Automated Validation of Trust and Security of Service-oriented Architectures{"}; 22nd IEEE Computer Security Foundations Symposium, CSF 2009 ; Conference date: 08-07-2009 Through 10-07-2009",

year = "2009",

doi = "10.1109/CSF.2009.15",

language = "English",

isbn = "9780769537122",

series = "Proceedings of the IEEE",

publisher = "IEEE Computer Society",

pages = "13--25",

booktitle = "Proceedings of the 22nd IEEE Computer Security Foundations Symposium",

}

Mauw, S, Radomirović, S & Dashti, MT 2009, Minimal Message Complexity of Asynchronous Multi-party Contract Signing. in Proceedings of the 22nd IEEE Computer Security Foundations Symposium: CSF 2009, 8-10 July 2009 / Port Jefferson, New York, USA. Proceedings of the IEEE, IEEE Computer Society, Los Alamitos, pp. 13-25, 22nd IEEE Computer Security Foundations Symposium, Port Jefferson, New York, United States, 8/07/09. https://doi.org/10.1109/CSF.2009.15

Minimal Message Complexity of Asynchronous Multi-party Contract Signing. / Mauw, Sjouke; Radomirović, Saša; Dashti, Mohammad Torabi.
Proceedings of the 22nd IEEE Computer Security Foundations Symposium: CSF 2009, 8-10 July 2009 / Port Jefferson, New York, USA. Los Alamitos: IEEE Computer Society, 2009. p. 13-25 (Proceedings of the IEEE).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Minimal Message Complexity of Asynchronous Multi-party Contract Signing

AU - Mauw, Sjouke

AU - Radomirović, Saša

AU - Dashti, Mohammad Torabi

N1 - M. Torabi Dashti has been partially supported by the FP7-ICT-2007-1 Project no. 216471, “AVANTSSAR: Automated Validation of Trust and Security of Service-oriented Architectures"

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70350527206&partnerID=8YFLogxK

U2 - 10.1109/CSF.2009.15

DO - 10.1109/CSF.2009.15

M3 - Conference contribution

AN - SCOPUS:70350527206

SN - 9780769537122

T3 - Proceedings of the IEEE

SP - 13

EP - 25

BT - Proceedings of the 22nd IEEE Computer Security Foundations Symposium

PB - IEEE Computer Society

CY - Los Alamitos

T2 - 22nd IEEE Computer Security Foundations Symposium

Y2 - 8 July 2009 through 10 July 2009

ER -

Minimal Message Complexity of Asynchronous Multi-party Contract Signing

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this