Cryptology ePrint Archive: Report 2013/432

How to Sign Paper Contracts? Conjectures & Evidence Related to Equitable & Efficient Collaborative Task Scheduling

Eric Brier and David Naccache and Li-yao Xia

Abstract: This paper explores ways of performing commutative tasks by $N$ parties. Tasks are defined as {\sl commutative} if the order at which parties perform tasks can be freely changed without affecting the final result. It is easy to see that arbitrary $N$-party commutative tasks cannot be completed in less than $N-1$ basic time units.

We conjecture that arbitrary $N$-party commutative tasks cannot be performed in $N-1$ time units by exchanging less than $4N-6$ messages and provide computational evidence in favor this conjecture. We also explore the most equitable commutative task protocols.

Category / Keywords: foundations / traffic analysis, encrypted containers, protocols

Date: received 8 Jul 2013

Contact author: david naccache at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20130713:052203 (All versions of this report)

Short URL: ia.cr/2013/432

Discussion forum: Show discussion | Start new discussion