Secure approximate pattern matching protocol via Boolean threshold private set intersection

Approximate pattern matching (APM) measures whether the Hamming distance between two strings is less than a threshold value. APM has been widely utilized, such as gene matching and facial recognition. Yet, the genetic data are privacy-sensitive, resulting that the owners are unwilling to share the raw data. This inspires us to explore how to securely perform APM. After revisiting threshold private set intersection (TPSI), we first propose and formalize a functionality named Boolean threshold private set intersection (BTPSI). The new proposed BTPSI primitive returns a Boolean value (0 or 1) to the user, rather than the actual elements in TPSI. We then construct a secure protocol for the BTPSI functionality with semihonest security. Besides, we first combine oblivious transfer and BTPSI to achieve the efficient construction of secure approximate pattern matching (SAPM) protocol in a semihonest model. Furthermore, we implement our SAPM protocol to demonstrate its real practicality. The performance result shows that when the text length is 2 20 ${2}<^>{20}$ and the pattern length is 2 10 ${2}<^>{10}$, the total runtime is less than 3 s.

Automated summary

This paper proposes a secure protocol for approximate pattern matching to address the privacy concerns in sharing genetic data. The authors first introduce the Boolean threshold private set intersection (BTPSI) functionality and develop a secure protocol for it. They then combine oblivious transfer with BTPSI in a semi-honest model to achieve an efficient construction of secure approximate pattern matching (SAPM) protocol. The performance experiment shows that the protocol has a low runtime when the length of the text and pattern are within certain ranges.