These questions are intimately connected to the round complexity of non-malleable commitments. Indeed, the exact relationship between the round complexities of non-malleable commitments and secure multi-party computation has also not been explored.
In this work, we revisit these questions and obtain several new results. First, we establish the following main results. Suppose that there exists a k-round non-malleable commitment scheme, and let k' = max(4, k + 1); then,
– (Two-party setting with simultaneous message transmission): there exists a k'-round protocol for securely realizing every two-party functionality;
– (Multi-party setting):there exists a k'-round protocol for securely realizing the multi-party coin-flipping functionality.
As a corollary of the above results, by instantiating them with existing non-malleable commitment protocols (from the literature), we establish that four rounds are both necessary and sufficient for both the results above. Furthermore, we establish that, for every multi-party functionality five rounds are sufficient. We actually obtain a variety of results offering trade-offs between rounds and the cryptographic assumptions used, depending upon the particular instantiations of underlying protocols.Category / Keywords: cryptographic protocols / Exact Round Complexity,Multi-Party Computation, Two-Party Computation, Simultaneous Model Exchange Channel, Lower Bound Original Publication (in the same form): IACR-EUROCRYPT-2016 Date: received 7 Mar 2016, last revised 10 Mar 2016 Contact author: antigoni at cs au dk Available format(s): PDF | BibTeX Citation Note: A citation is added Version: 20160310:155644 (All versions of this report) Short URL: ia.cr/2016/252 Discussion forum: Show discussion | Start new discussion