Loading...
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.
Loading...
Name
optimal_fair_computation.pdf
Access type
openaccess
Size
642.74 KB
Format
Adobe PDF
Checksum (MD5)
d1a9d4c23840c8804e9977d5b191d475