Optimal Fair Computation

A computation scheme among n parties is fair if no party obtains the computation result unless all other n-1 parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party. We prove, for the first time, a tight lower bound on the message complexity of optimistic fair computation for n parties among which n-1 can be malicious in an asynchronous network. We do so by relating the optimal message complexity of optimistic fair computation to the length of the shortest permutation sequence in combinatorics.


Year:
2016
Keywords:
Laboratories:




 Record created 2016-07-11, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)