We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In particular, Katz and Ostrovsky CRYPTO '04 proved that 5 rounds are necessary and sufficient for securely realizing every two-party functionality where both parties receive the output. However, the exact round complexity of general multi-party computation, as well as two-party computation with a simultaneous message exchange channel, is not very well understood.
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′=max4,k+1k'=max4,k+1; then,Two-party setting with simultaneous message transmission: there exists a
k′k'-round protocol for securely realizing every two-party functionality;Multi-party setting: there exists a
k′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 functionalityfive 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.
Private set intersection (PSI) has important application value, however, current quantum PSI protocols are either unsuitable for multi-party scenarios or inefficient. Recently, Imran (arXiv: 2303.17196v3 , 2023) proposed two quantum secure multi-party greatest common divisor (GCD) protocols that can be used for PSI, but with the downside of information leakage and resource consumption. In this paper, we propose a novel quantum secure multi-party GCD protocol that has higher security and lower complexity. To hide privacy, each party randomly selects a coefficient within a range determined by his input integer, and with the assistance of a semi-honest third party TP, all parties secretly calculate the linear combination of their inputs under these coefficients. Once enough linear combinations are collected, TP calculates the GCD of these combinations, which is equal to the GCD of all input integers. To verify the honesty of participants, a quantum zero-knowledge proof sub-protocol is designed. Analysis shows that our GCD protocol is correct and has security against malicious attacks. Moreover, its complexity is polynomial level and lower than Imran’s. Furthermore, we demonstrate the scalability of our GCD protocol in private set operations, such as private set intersection, private set intersection cardinality, private multi-set intersection, etc.