Universally-Composable Two-Party Computation in Two Rounds
Round complexity is a central measure of efficiency, and characterizing the round complexity of various cryptographic tasks is of both theoretical and practical importance. The authors show here a Universally Composable (UC) protocol (in the common reference string model) for two-party computation of any functionality, where both parties receive output, using only two rounds. (This assumes honest parties are allowed to transmit messages simultaneously in any given round; they obtain a three-round protocol when parties are required to alternate messages.) Their results match the obvious lower bounds for the round complexity of secure two-party computation under any reasonable definition of security, regardless of what setup is used.