IACR News item: 25 February 2016
Sandro Coretti, Martin Hirt, Juan Garay, Vassilis Zikas
ePrint Report
Secure multi-party computation (MPC) allows several mutuallydistrustful parties to securely compute a joint function of theirinputs and exists in two main variants: In *synchronous* MPC partiesare connected by a synchronous network with a global clock, andprotocols proceed in *rounds* with strong delivery guarantees, whereas*asynchronous* MPC protocols can be deployed even in networks thatdeliver messages in an arbitrary order and impose arbitrary delays onthem.
The two models---synchronous and asynchronous---have to a large extentdeveloped in parallel with results on both feasibility and asymptoticefficiency improvements in either track. The most notable gap in thisparallel development is with respect to round complexity. Inparticular, although under standard assumptions on a synchronouscommunication network (availability of secure channels and broadcast),synchronous MPC protocols with (exact) constant rounds have beenconstructed, to the best of our knowledge, thus far no constant-roundasynchronous MPC protocols are known, with the best protocolsrequiring a number of rounds that is linear in the multiplicativedepth of the arithmetic circuit computing the desired function.
In this work we close this gap by providing the first constant-roundasynchronous MPC protocol. Our protocol is optimally resilient (i.e.,it tolerates up to $t<n/3$ corrupted parties), adaptively secure, andmakes black-box use of a pseudo-random function. It works under thestandard network assumptions for protocols in the asynchronous MPCsetting, namely, a complete network of point-to-point (secure)asynchronous channels with eventual delivery and asynchronousByzantine agreement (aka consensus). We provide formal definitions ofthese primitives and a proof of security in the UniversalComposability framework.
The two models---synchronous and asynchronous---have to a large extentdeveloped in parallel with results on both feasibility and asymptoticefficiency improvements in either track. The most notable gap in thisparallel development is with respect to round complexity. Inparticular, although under standard assumptions on a synchronouscommunication network (availability of secure channels and broadcast),synchronous MPC protocols with (exact) constant rounds have beenconstructed, to the best of our knowledge, thus far no constant-roundasynchronous MPC protocols are known, with the best protocolsrequiring a number of rounds that is linear in the multiplicativedepth of the arithmetic circuit computing the desired function.
In this work we close this gap by providing the first constant-roundasynchronous MPC protocol. Our protocol is optimally resilient (i.e.,it tolerates up to $t<n/3$ corrupted parties), adaptively secure, andmakes black-box use of a pseudo-random function. It works under thestandard network assumptions for protocols in the asynchronous MPCsetting, namely, a complete network of point-to-point (secure)asynchronous channels with eventual delivery and asynchronousByzantine agreement (aka consensus). We provide formal definitions ofthese primitives and a proof of security in the UniversalComposability framework.
Additional news items may be found on the IACR news page.