Research On Secure Two-party Computation Protocols For Pattern Matching Problem

With the development of cloud computing,big data and other technologies,the multi-source data in the distributed computing scenario gives full play to its social and economic value.While maximizing the value of multi-source data,it is also inevitable to consider its privacy leakage.In terms of protecting the privacy of data,secure multi-party computation(SMPC)plays an irreplaceable role,which essentially considering privacy protection issues at the protocol-level.Secure two-party computation is a special instance of secure multi-party computation,which aims to enable two parties to jointly perform distributed computing tasks while ensuring that the private data of both parties are not revealed.Secure pattern matching(SPM)protocol involves two participants,the user who enters the pattern string to be queried and the database owner who enters the long text string.Secure pattern matching allows the user to obtain the positions of its pattern string appearing in the text string,while ensuring that no information about the pattern string and the text string other than the matched substrings is revealed.This paper focuses on the secure pattern matching problem,which is portrayed by a secure two-party computation model,the main research include:1.Secure wildcard pattern matching(SWPM)is a variant of standard pattern matching designed to determine the positions of a short pattern in a long text,where wildcards can match any character in a character list,while not revealing the private input of the parties.By extending the functionality of classical wildcard pattern matching,we proposed secure wildcard pattern matching with query(SWPMQ)functionality which allows the user(pattern holder)to obtain the positions and actual data of these positions without revealing pattern and text information.We give the specific construction of the protocol in the presence of semi-honest adversaries and prove the security of the protocol through ideal/real simulation paradigm.By using oblivious transfer extension(OTE)technique,the computational complexity of the protocol can be reduced to O(k),where k represents the number of oblivious transfer(OT)protocols that need to be executed.2.Secure approximate pattern matching(SAPM)is also a variant of pattern matching,which aims to determine the positions of text substrings that approximately match a pattern,i.e.,to determine the positions of all text substrings whose Hamming distance from the pattern is less than a given threshold τ,while not revealing the privacy of the parties’ input.An efficient secure approximate pattern matching protocol is proposed for the approximate pattern matching scenario,and the protocol is proved to be secure in the presence of semi-honest adversaries by ideal/real simulation paradigm.In terms of efficiency,compared to currently available secure approximate pattern matching works,our protocol has an advantage in the aspect of computational complexity by reducing the complexity to O(nτ),where n is the text length,τ is a given threshold value.