Research On Theory Of Practical Secure Two-Party Computation

As the rapid development of Internet of Things, mobile computing and cloud com-puting, people’s lifestyle is undergoing a dramatic change. These emerging data pro-cessing techniques provide great convenience for the whole society. Meanwhile, the leakage of private information and secret data happens frequently, which imposes severe restrictions on the application and popularization of these data processing technologies. Consequently, it has become an urgent task to construct data processing method in pri-vacy preserving manner. Information security is becoming more and more important. As the core technology in the field of information security, cryptography plays a cen-tral role for every aspect of security insurance and provides theoretical foundations and technical supports for data privacy, integrity and authentication.As an important fundamental research topic in the field of cryptography, secure multi-party computation discusses the problem of cooperative computing on private data of several participants in a secure way in the distributed computing scenario. Infor-mally, in the scenario of secure multi-party computation, two or more parties holding private inputs wish to compute some joint functionality on these inputs. The security requirement is that each participant obtains its objective output and nothing else. The research of secure multi-party computation promotes the development of cryptography. Specifically, constructing protocols for secure multi-party computation requires many cryptographic primitives, which facilitates the development of these basic tools. Be-sides, secure multi-party computation is a general theoretical research of cryptographic protocols. It provides theoretical basis for cryptographic protocols, and thus accelerates the progress of modern cryptography.Early studies on secure multi-party computation focus on security model, feasibil-ity and complexity classification, etc. As the great improvement of computing power and communication capability, on the basis of continual studies on theoretical secure multi-party computation, researches on practical secure multi-party computation have also attracted wide attention from the international cryptographic research community. Practical secure multi-party computation mainly focuses on the efficiency of generic protocols for secure multi-party computation, and studies methods and techniques to improve the efficiency of generic protocols, from the aspect of computation overhead, communication overhead and interaction rounds, etc. Generic protocol means a gen-eral protocol that can securely compute any functionality. The basic idea of construct-ing generic protocols is to represent the objective functionality as arithmetic circuit or Boolean circuit, and operate on each circuit gate with cryptographic tools, such as secret sharing, homomorphic encryption, oblivious transfer or garbled circuit, etc. At last, the whole circuit can be computed in a secure manner.As a special case of secure multi-party computation, secure two-party computation formalizes many cryptographic tasks, such as zero-knowledge proof, oblivious transfer, coin tossing and commitment schemes, etc. It has special theoretical research signifi-cance to study secure two-party computation. Besides, as only two parties participate in secure two-party computation, there is no honest majority in the security model. Therefore, research on secure two-party computation has its specific difficulty and par-ticularity.In this paper, we take practical secure two-party computation as main research topic and focus on the fundamental theory in this research area. In the field of se-cure two-party computation, one of the most efficient methods of constructing generic protocols in malicious model is to apply cut-and-choose technique for garbled circuit. With this technique, one can construct efficient generic protocols with provable security under ideal/real simulation paradigm, which implies strongest security level in reality. However, there are still many issues which are not addressed well in cut-and-choose-based secure two-party computation, such as input consistency of participants, selective failure attack in oblivious transfer, two-output function, etc. This paper studies two of the above issues and does some deep research in practical secure two-party computation from two aspects. Firstly, we concentrate on the research of oblivious transfer, one of the underlying basic tools of secure computation. The functionality of oblivious trans-fer is extended and two new cryptographic primitives are proposed. The new proposed primitives can be used to decrease the round complexity and thus improve the efficiency of outer generic secure computation protocols. Secondly, we study two-output function and propose an optimal paradigm to complete two-output secure computation. Based on this new paradigm, one can designs faster two-output secure computation protocols with optimal probability.Specifically, the contributions of this paper are summarised as follows:● Research on Basic Tools of Secure Two-Party Computation-This paper studies the basic tool, oblivious transfer, in secure two-party computation, and proposes two new cryptographic primitives in cut-and-choose scenario:cut-and-choose inverted oblivious transfer and cut-and-choose bilateral oblivious transfer. These new primitives are fundamental cryptographic tools, which are important in fundamental theory in cryptog-raphy. Proposed primitives not only provide new ways to transfer data in an secure manner and enable participants to complete different transfer tasks on the network, but also provide theoretical foundations and technical sup-ports for improving the efficiency of high-level security protocols. Specif-ically, cut-and-choose bilateral oblivious transfer is a very powerful basic tool. When applied in secure computation protocols based on garbled cir-cuit and cut-and-choose paradigm, it can not only transfer all garbled keys corresponding to the generator in all garbled circuits, but also transfer all necessary data of the other participant together. There is no need to com-plete the transfer task with extra interaction rounds. As a result, the frame-work of the outer secure computation protocols are significantly simplified and the interaction rounds between parties are greatly decreased.-Except for formalizing the functionalities of the new proposed cryptograph-ic primitives, cut-and-choose inverted oblivious transfer and cut-and-choose bilateral oblivious transfer, as well as cut-and-choose oblivious transfer pro-posed by other researchers, this paper also instantiates them based on ho-momorphic encryption and formally proves the security of them in mali-cious model under standard security proof paradigm, ideal/real simulation paradigm, which indicates that these constructions theoretically achieve the strongest security level in reality.● Research on Two-Output Secure Computation-This paper studies two-output functions in secure two-party computation, and expects to find effective method that can solve two-output secure com-putation problem with optimal error probability in cut-and-choose paradig-m. Cut-and-choose technique can be used to construct generic protocols in malicious model with high efficiency, at the expense of a certain error probability. This probability is the key factor that affects protocol efficien-cy. It is an important research topic to minimize the error probability. The technique for computing single-output functions with optimal error prob-ability is already presented by researchers. However, it is unclear how to compute two-output functions in an optimal manner. This paper proposes the optimal paradigm for two-output secure computation for the first time, which provides an effective way to design two-output secure computation protocols with optimal error probability. Based on the new paradigm, a fast two-output secure computation generic protocol is constructed, and a rigor-ous security proof is formally provided in malicious model under ideal/real simulation paradigm.-A key problem in two-output computation is the authentication issue of the generator’s output. The efficiency of this problem matters the computation efficiency and communication efficiency of the whole protocol. This paper presents the most efficient scheme in standard model (without random ora-cle assumption) in solving the authenticity issue, utilizing the specific con-struction of garbled keys associated with circuit output wires. The proposed scheme only requires computation operations linear in the output length of the generator, and requires only symmetric cryptographic operations.