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 -