Minimal message complexity of asynchronous multi-party contract signing
METADATA ONLY
Loading...
Author / Producer
Date
2009
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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 alpha^2 + 1, with alpha 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.
Permanent link
Publication status
published
External links
Editor
Book title
2009 22nd IEEE Computer Security Foundations Symposium
Journal / series
Volume
Pages / Article No.
13 - 25
Publisher
IEEE
Event
22nd IEEE Computer Security Foundations Symposium (CSF 2009)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Contract signing protocols; Multi-party protocols; Complexity; Shortest permutation sequences
Organisational unit
03634 - Basin, David / Basin, David
Notes
Funding
Related publications and datasets
Is new version of: