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.


Année
2016
Mots-clefs:
Laboratoires:




 Notice créée le 2016-07-11, modifiée le 2019-03-17

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)