Publication
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.
Arjen Lenstra, Robert Granger, Thorsten Kleinjung, Benjamin Pierre Charles Wesolowski
Serge Vaudenay, Fatma Betül Durak