From fairness to full security in multiparty computation (Q5916285)

The paper presents a transformation for multiparty protocols with fairness and a constant number of honest parties into corresponding protocols with full security. A protocol is called fair if an adversary can prematurely abort the computation, however, only before learning any new information; a protocol is called fully secure if no adversary can prevent the honest parties from obtaining their outputs. The proposed transformation is more efficient than previous transformations. The main idea is quite simple which is to delegate the computation to random committees that invoke the fair computation. The authors show that the results are in a sense optimal, by proving that for some functionalities, a super-constant number of sequential invocations of the fair computation is necessary for computing the functionality fully secure. The idea of electing a small committee to perform a computation is an old and established approach. It was initially proposed in [\textit{G. Bracha}, J. Assoc. Comput. Mach. 34, 910--920 (1987; Zbl 0631.68023)] for a randomized Byzantine generals protocol. Since then it has been deeply analyzed and considered in numerous settings. Therefore, the transformation seems straight-forward. However, technical difficulties have to be addressed. As an intermediate security model, the authors introduce fairness with restricted identifiable abort, where only corrupted committee members are allowed to abort the computation. The authors show that a fair protocol can be transformed into a corresponding one with fairness with restricted identifiable abort. The underlying idea is to let the committee prove that every step in the execution is correct such that when the protocol terminates the parties either obtain the output or identify a corrupted party. To achieve a fully secure computation a small committee is chosen using an information-theoretically secure committee-election protocol. The computation is then delegated to this small committee, which securely computes the functionality with fairness and restricted identifiable abort. Since, the computation of the small committee might abort, the computation may have to be repeat several times, while eliminating the aborting parties. In order to reduce the round complexity the authors use the technique to split up the committee into several subcommittees. These details are interesting and explained well. Two applications are explicitly stated. The first one is a new coin-flipping protocol, whose round complexity has a super-logarithmic dependency on the number of parties. A second application is a new fully secure protocol for computing the Boolean OR function, with a super-constant round complexity. Both protocols improve previous results.