Research On Basic Theory And Crucial Technique Of Efficient Secure Two-party Computation

In recent years,with the continuous development of computer network technology and the rapid rise of the emerging technology such as cloud computing,big data and Internet of Things,network security has become a hot topic for the nation,government and individuals.People prefer paying more attention to protect the data privacy now,for the privacy issues occur frequently in various ways at home and abroad.Thus,the security of data is becoming a global problem to be solved in the process of network.Fortunately,cryptography provides rich and powerful means for data protection,which covers not only confidentiality and privacy,but also other security factors such as in-tegrity,authentication and so on.Therefore,cryptography plays an irreplaceable role in protecting security of data in the network.Secure multi-party computation(SMPC)is an important research branch of mod-ern cryptography,which mainly considers the secure computation problems in distribut-ed computing scenario.Distributed computing involves lots of distinct but connected devices,which are willing to execute a joint computation task.SMPC aims at enabling these parties to carry out the distributed computation in a secure way.Intuitionally,se-curity means how to protect the input privacy of each party and to guarantee the correct-ness of the output.Concretely,input privacy means that each party cannot obtain any information about the input of other parties using the its own input and output.Besides,output correctness requires that each party should obtain its correct output.In terms of computation tasks,SMPC can deal with some simple tasks,such as coin-tossing and broadcast,and also numerous complex real application problems like electronic voting,electronic auctions and anonymous transactions.In fact,SMPC can be seen as research of general cryptographic protocol,therefore any cryptographic protocols can be covered in the theory model of SMPC.It follows that research on SMPC could greatly promote the development of cryptography in both basic theory and application protocols.SMPC has experienced a development of twists and turns since Mr Andrew Chi-Chih Yao proposed the millionaire problem in 1982.The early research mainly focus on the feasibility of secure multi-party computation.In this period,a vast amount of pretty theoretical facts have been proposed,which indicate that any distributed tasks can be securely computed in some condition.Besides,research in other aspects,such as security model,formal proof and general protocols,has been matured gradually in theory.However,these theoretical achievements are far from reality.After a period of silence,SMPC has ushered in a new peak in the past ten years.The reasons are mainly manifested in the following two aspects.First,the development of practical SMPC protocols makes people full of hope when using SMPC to solve real problems.As a result,SMPC has attracted more and more attention.Second,cloud computing provides application background for SMPC when applying SMPC for data processing in privacy-preserving manner.The current research in SMPC mainly contains its basic theory,construction of efficient protocols and the combination with other disciplines.This paper mainly studies the basic theory and curricula technique of efficient and secure two-party computation(STPC).STPC is a special case of secure multi-party computation,which only involves the two-party setting.Compared with SMPC,secure two-party computation has its own advantages,especially in efficiency.Besides,most real-world applications only involve two participants,such that it is easier to model them in two-party setting.For the reason that more and more cryptographic researchers have interest in solving real-world problems using secure two-party computation,our research mainly focus on constructing truly efficient secure two-party protocols so as to speed up the pace of STPC from theory to practice.Certainly,this paper focuses on cryptographic basic theory.Therefore,we are mainly concerned with the security requirements the proposed cryptographic protocols satisfy,and also the theoretical fea-sibility when realizing those cryptographic protocols.In this way,we lay a theoretical foundation for the design and realization of practical cryptographic protocols.Besides,we do not consider how to implement and deploy these protocols in real-world,but pay attention to strict security proof.In other words,our proposed secure protocols must be formally proved in specific security model.The above provable security requirement is also necessary in modern cryptography.Our research mainly contains the following aspects:basic protocols in STPC,general constructions of secure two-party protocols,cloud-assisted STPC and secure two-party protocols for specific applications.Consid-ering basic primitive,we study efficient construction of oblivious transfer(OT)protocol in standard malicious adversary model.For constructions of general functionality,we mainly study efficient secure two-party protocols based on Yao's garbled circuits and cut-and-choose technique,so as to guarantee security gainst malicious adversary.In late-model secure computation,we consider cloud-assisted secure two-party computa-tion.We mainly study its security model and the efficient construction of protocols in cloud computing scenario.In addition,we study efficient constructions of secure protocol for specific pattern matching problem.Concretely,the study content of this paper mainly includes the following four as-pects:1.Oblivious transfer is a basic primitive of secure multi-party computation and mod-ern cryptography,which has been widely used in other cryptographic protocols.The traditional 1-out-of-2 oblivious transfer(OT21)protocol involves sender and receiver,where the sender holds a pair of secret messages and the receiver wishes to choose one of the message pair.Security requires that the choice of the receiver is secret to the sender,and meanwhile the receiver can only obtain one message.In general,k-out-of-n oblivious transfer(OTnk)indicates that the receiver wants to obtain k messages from the sender's n messages(w hen k=1,that is OTn1).The study of oblivious transfer mainly contains efficiency and security.For the rea-son that oblivious transfer is widely used as a sub-protocol in other cryptographic protocols,the strong security requirement is always the focus of the study.This paper firstly presents an efficient construction of OTn1 with security against mali-cious adversary,and then proves its security in the ideal/real simulation paradigm.The protocol is mainly based standard decisional Diffie-Hellman(DDH)assump-tion with constant number of interactive complexity.Besides,the computation and communication complexity is just liner of n.2.The earliest general protocol for secure two-party computation is based on Yao garbled circuits and only is secure in semi-honest adversary model.Considering malicious adversary,there exists a theoretical compiler,called GMW,which can transfer a protocol with semi-honest security to the version with malicious secu-rity.However,the efficiency is intolerable.Differently,cut-and-choose technique avoids using complex zero-knowledge proof and is widely used in the construc-tion of general secure tao-party protocols when considering malicious adversary.The new framework,which combines Yao garbled circuits and cut-and-choose technique,brings up many new problems.Traditional cryptographic tools are not enough to solve these problems,such that we are looking forward to searching for other new and satisfying primitives.This paper focuses on a new crypto-graphic primitive,called cut-and-choose bilateral oblivious transfer(CCBOT),and firstly proposes a secure CCBOT protocol in the malicious adversary mod-el.The protocol achieves transferring all the keys of the garbled circuit at one time,as a result the interactive rounds of the secure two-party protocol are great-ly reduced.The proposed protocol is based on DDH assumption,and besides avoids using cut-and-choose technique and commitment scheme.Furthermore,the round,communication and computation cost are all constant.3.Cloud computing enables users to perform data processing in a new way,which means that users can outsource their personal data and computation tasks to the cloud.Secure multi-party computation in cloud-assisted setting indicates that the parties have access to one or more cloud servers,which have no input and output to the computation.The cloud servers only provide their computational resources to help the parties execute the protocol.In this way,the computation cost of all the parties greatly reduce and such that the corresponding protocol becomes more efficient.This paper mainly studies the security model and efficient construction of cloud-assisted secure two-party computation protocol.We firstly construct a secure OTnk protocol in the cloud-assisted setting,where the cloud servers are assumed semi-honest.The proposed protocol is more efficient in computational complexity compared with other existing protocols.4.Privacy preserving has gradually attracted more and more attention in numerous real-word scenarios,such as machine blearing,social network and blockchain.Most of the related algorithms and protocols in these scenarios can be modeled using secure two-party computation.This paper studies the pattern matching problem in a privacy preserving manner.Secure pattern matching protocol in-volves only two parties,where one party holds the text and the other one hold-s the pattern.The protocol aims at returning the successful matching results,and meanwhile revealing nothing to the other party.Approximate pattern match-ing is a variant of exact pattern matching,which enables two approximate pat-terns can match successfully.It has been widely used in DNA matching,facial recognition and music retrieval.This paper focuses on efficient construction of privacy-preserving pattern matching protocol.We propose a secure exact pattern matching protocol using two basic tools,which are secret sharing and oblivious transfer.Then we present a secure approximate pattern matching protocol based on the first protocol in cloud-assisted setting.The approximate protocol enables the parties to outsource their computational tasks to the semi-honest cloud server,such that we gain better efficiency.