Abstract
In this work we continue the study on the round complexity of secure two-party computation with black-box simulation.
Katz and Ostrovsky in CRYPTO 2004 showed a 5 (optimal) round construction assuming trapdoor permutations for the general case where both players receive the output. They also proved that their result is round optimal. This lower bound has been recently revisited by Garg et al. in Eurocrypt 2016 where a 4 (optimal) round protocol is showed assuming a simultaneous message exchange channel. Unfortunately there is no instantiation of the protocol of Garg et al. under standard polynomial-time hardness assumptions.
In this work we close the above gap by showing a 4 (optimal) round construction for secure two-party computation in the simultaneous message channel model with black-box simulation, assuming trapdoor permutations against polynomial-time adversaries.
Our construction for secure two-party computation relies on a special 4-round protocol for oblivious transfer that nicely composes with other protocols in parallel. We define and construct such special oblivious transfer protocol from trapdoor permutations. This building block is clearly interesting on its own. Our construction also makes use of a recent advance on non-malleability: a delayed-input 4-round non-malleable zero knowledge argument.
Katz and Ostrovsky in CRYPTO 2004 showed a 5 (optimal) round construction assuming trapdoor permutations for the general case where both players receive the output. They also proved that their result is round optimal. This lower bound has been recently revisited by Garg et al. in Eurocrypt 2016 where a 4 (optimal) round protocol is showed assuming a simultaneous message exchange channel. Unfortunately there is no instantiation of the protocol of Garg et al. under standard polynomial-time hardness assumptions.
In this work we close the above gap by showing a 4 (optimal) round construction for secure two-party computation in the simultaneous message channel model with black-box simulation, assuming trapdoor permutations against polynomial-time adversaries.
Our construction for secure two-party computation relies on a special 4-round protocol for oblivious transfer that nicely composes with other protocols in parallel. We define and construct such special oblivious transfer protocol from trapdoor permutations. This building block is clearly interesting on its own. Our construction also makes use of a recent advance on non-malleability: a delayed-input 4-round non-malleable zero knowledge argument.
| Original language | English |
|---|---|
| Title of host publication | Theory of Cryptography |
| Editors | Yael Kalai, Leonid Reyzin |
| Place of Publication | Cham |
| Publisher | Springer |
| Pages | 678-710 |
| Number of pages | 33 |
| ISBN (Electronic) | 978-3-319-70500-2 |
| ISBN (Print) | 978-3-319-70499-9 |
| DOIs | |
| Publication status | Published - 5 Nov 2017 |
| Event | 15th Theory of Cryptography Conference - The Charles Commons Conference Center, Johns Hopkins University, Baltimore, United States Duration: 12 Nov 2015 → 15 Nov 2017 https://www.iacr.org/workshops/tcc2017/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer, Cham |
| Volume | 10677 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 15th Theory of Cryptography Conference |
|---|---|
| Abbreviated title | TCC 2017 |
| Country/Territory | United States |
| City | Baltimore |
| Period | 12/11/15 → 15/11/17 |
| Internet address |