IACR News item: 13 July 2013
Eric Brier, David Naccache, Li-yao Xia
ePrint Report
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.
Additional news items may be found on the IACR news page.