The problem of secure multi-party computation(SMPC) is one of the most fundamental problems in information security. First, we introduce the basic concept of SMPC and four SMPC basic agreement: key distribution,oblivious transfer, bit commitment and zero knowledge proof. Secondly, we separately illustrate commitment schemes commitment transfer protocol, commitment sharing protocol and commitment multiplication protocol. Finally, we present unconditionally secure multi-party computation with a passive adversary, an active adversary, general adversary structures.
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.
This thesis considers multi-prover commitment schemes whose security is based on restrictions on the communication between the provers. The results are applicable to so-called relativistic commitment schemes: schemes whose security is guaranteed by the fact that information does not travel faster than the speed of light. A commitment scheme is a cryptographic protocol solving the following problem: One party, the prover, has selected a value which he wants to keep secret at first. The prover wants to have the option to reveal it to the other party, the verifier, at a later time, but the verifier wants a guarantee that no value other than the originally selected one can be revealed. Standard commitment schemes can only be proven secure with computational hardness assumptions. This can be circumvented by splitting the prover into multiple entities and restricting their communication, e.g., no communication at all, or communication only with a delay (as in relativistic commitment schemes). This dissertation introduces new methods for analyzing and designing such multi-prover schemes. As an application, we show that the Lunghi et al. commitment scheme from 2015 has much stronger security that their original analysis indicated.