Research On Key Techniques Of Practical Secure Two-party Computation And Privacy Protection

After the concept of Secure Multi-Party Computation(MPC)was proposed,as a theoretical study of general cryptographic protocols,rich and profound research results have been obtained,and basically complete conclusions have been made in theoretical models of secure computation and the existence of protocols in various backgrounds.In the digital society,data has become the basic resource for social development.To make data play its due value and promote social development,data fusion and utilization is the only way.However,all aspects of data integration and utilization may cause information security issues such as privacy leakage,which seriously hinders data sharing and utilization.MPC can protect the input of all parties in a computing task from being leaked,ensuring that all honest parties obtain correct results.Therefore,it has become an important tool for data sharing and collaborative utilization under privacy protection.With the gradual maturity of theoretical research and the promotion of urgent social needs,the research hotspot of MPC has shifted from the initial theoretical research to the practical research of general schemes in the past ten years.Researchers propose many efficient and practical solutions to specific problems in specific scenarios.Meanwhile,MPC drives the practical research of basic cryptographic protocols such as Oblivious Transfer(OT),secret sharing,and zero knowledge,which has greatly promoted the landing and application of various private data computing service platforms.Secure two-party computation is a special case of MPC,which is not only a common situation in practical applications where it can meet a large number of requirements but also an important foundation for practical research on secure multi-party computation.A secure computation protocol designed in two-party scenarios can provide an important train of thought and basic components for extending to multi-party scenarios.In practical applications,secure two-party computation can meet the requirements of private data computing.This thesis mainly studies the practical secure two-party computation,and uses this as a basis to study key technologies of privacy protection.The research content includes not only low-level cryptographic primitives but also high-level secure computation protocols.Specifically,the work of this thesis mainly includes the following 3 aspects:1.Research on OT protocols in cloud environment:OT is the core component of the MPC universal architecture.General secure computing protocols are generally constructed based on Yao-garbled circuits or GMW(GMW-like)protocols.Under the semi-honest adversary model,each input bit of the evaluation party in Yao-garbled circuits corresponds to one execution of the OT protocol,and each multiplication gate of the GMW protocol requires at least one execution of the OT protocol,which makes the general secure multiparty necessarily to use a large number of OT protocols.Therefore,the research on the practicality of MPC protocol largely depends on the practicality of OT.Acting as one of the most important primitives in cryptography,OT has developed into an independent research field in MPC.The basic OT protocol is that the receiver selects one of the two messages sent by the sender,i.e.1-out-of-2 OT.Subsequently,more general k-out-of-n OT is derived.Research has shown that OT must be designed based on the public-key mechanism.k-out-of-n OT protocols also require a large amount of public-key operations.The computational complexity of existing k-out-of-n OT protocols is usually O(kn),which is difficult to meet practical requirements.With the rise of new computing models such as cloud computing,it has not only gained widespread popularity in the industry but also received close attention from academia.We study the protocol design of OT in cloud environments using the powerful computing power and dedicated bandwidth provided by cloud servers.The high computation and communication complexity of k-out-of-n OT protocols has become a bottleneck in applications.In this thesis,based on cloud computing scenarios,we design and construct an efficient protocol OTnk assisted by a single server.We provide formal security proof of the protocol under the semi-honest model,achieving the desired security requirements.Existing OT protocols in cloud environments require several servers,while our proposal only requires a single server to perform the computation.The proposed protocol in this thesis requires three rounds of communication in total and reduces the computation and communication complexity of the sending and receiving parties to O(n).2.Research on OT extension protocols:As mentioned above,in a semi-honest model,MPC protocols typically require a large number of OT instances.In a stronger adversary model,the protocols require more OT instances to achieve the required security.Therefore,researchers have proposed and designed the OT extension protocol(OT extension for short)to obtain a large number of OT instances required in the protocol.The core idea of OT extension is to extend plenty of OT instances that are based on a small number of public-key operations together with a large number of symmetric operations.The proposal of OT extension provides an important foundation for the practicality of MPC.This thesis focuses on specific application scenarios and security models,studies the efficiency and security of existing OT extension protocols,and designs more efficient and secure OT extension protocols.(1)Outsourcing extension scheme under the semi-honest model.In the practical application of secure two-party computation protocols,the participants may have the small available computing power and limited interactive bandwidth.This thesis optimizes the computation of participants in the OT extension protocol in the outsourcing scenario.The public-key computation of the receiver is transferred to the offline phase,and all public-key operations of the sender are transferred to the cloudaided server.The three parties can generate a large number of OT instances through interaction.Under the semi-honest model,the public-key computation complexity of the sender in this scheme is optimal.(2)Signed-OT extension schemes under the publicly verifiable covert model.Unlike the semi-honest model and malicious model,the publicly verifiable covert model can achieve a good balance between security and efficiency.Signed-OT is a basic component for constructing publicly verifiable schemes,so it is necessary to provide plenty of signed-OT instances for publicly verifiable and secure protocols by invoking the signed-OT extension protocol so it is necessary to achieve the extension of the signedOT scheme.However,there are security flaws in the existing signed-OT extension protocol.This thesis presents a feasible attack method and proposes a secure publicly verifiable protocol.By testing and analyzing the efficiency of the proposed protocol,the computational and communication efficiency of this scheme has been improved by at least 2 times.3.Research on private set compution protocols:Private set compution is a high-level but basic primitive in the MPC field,which can be applied to various complex computing scenarios such as statistical analysis,private data query and data mining.It can also construct specific protocols directly oriented to applications such as electronic voting.Based on private set operations,this thesis focuses on the efficient and practical construction of protocols in two-party scenarios.(1)Research on efficient private member test schemes.We research a practical private membership test protocol for the case where the par ticipant has only one element in a set.When the input form is bit strings,privacy member test protocols are also known as pattern matching.In existing pattern matching protocols with wildcards,participants need to interact at least twice.This thesis proposes a single-round secure pattern matching protocol with wildcards,which is the first protocol to require only one interaction.With OT extension technology,the amount of public-key computation required by the protocol is only related to security parameter.(2)Intersection-based two-party computation protocols.Considering the situation where two participants both hold large-scale sets,a new cryptographic primitive called shuffle oblivious pseudorandom function based on OT extension is proposed for the first time,where the amount of the public-key computation depends on the security parameter.Based on the new primitive,two-party intersection computation protocols are designed,including the intersection cardinality protocol,private set intersection protocol with threshold,and circuit-based private set intersection protocol.In summary,based on the basic theory of secure multi-party compution and focusing on the practicality problem of secure two-party computation,this thesis designs basic cryptograpic primitives and efficient and practical underlying secure computing protocols,and on this basis provides key technologies for privacy protection applications.The research content improves the practicality of secure computing from both theoretical and practical aspects.