Round−Optimal Black−Box Two−Party Computation
Rafail Ostrovsky, Silas Richelson, Alessandra Scafuro
Abstract:
In [Eurocrypt 2004]Katz and Ostrovsky establish the exact round complexity of secure two-party computation with respect to black-box proofs of security. They prove that 5 rounds are necessary for secure two-party protocols (4−round are sufficient if only one party receives the output) and provide a protocol that matches such lower bound. The main challenge when designing such protocol is to parallelize the proofs of consistency provided by both parties-necessary when security against malicious adversaries is considered−in 4 rounds. Toward this goal they employ specific proofs in which the statement can be unspecified till the last round but that require non-black-box access to the underlying primitives.
A rich line of work[1, 9, 11, 13,24] has shown that the non−black−box use of the cryptographic primitive in secure two-party computation is not necessary by providing black−box constructions matching basically all the feasibility results that were previously demonstrated only vis non-black-box protocols.
All such constructions however are far from being round optimal. The reason is that they are based on cut-and-choose mechanisms where one party can safely take an action only afterthe other party has successfully completed the cut-and-choose phase, therefore requiring additional rounds.
A natural question is whether round-optimal constructions do inherently require non-black-box access to the primitives, and whether the lower bound shown by Katz and Ostrovsky can only be matched by a non-black−box protocol.
In this work we show that round-optimality is achievable even with only black-box access to the primitives. We provide that first 4−round black−box oblivious transfer based on any enhanced trapdoor permutation. Plugging a parallel version of our oblivious transfer into the black-box non−interactive secure computation protocol of [12] we obtain the first round−black−two-party protocol in the plain model for any functionality.
comment: CRYOPTO 2015 PP: 339-358
Fetch PDF file of the paper
| Back to Publications List |