PVOPM: Verifiable Privacy-Preserving Pattern Matching with Efficient Outsourcing in the Malicious Setting

Outsourced pattern matching delegates the task of finding all positions pattern P appears in text T to the cloud from resource-constrained devices. Unfortunately, it has brought a series of security and privacy issues. Most of the state-of-the-art either disclosed text/pattern privacy or exploited the computationally-intensive techniques of public key fully homomorphic encryption (FHE), commitment schemes and zero knowledge proof to achieve both text/pattern privacy and verifiability. To address these issues, as a building block, an efficient privacy preserving verifiable outsourced discrete fourier transform protocol OVFT is first devised based on any one-way trapdoor permutation (OWTP). Based on OVFT, we propose an efficient secure verifiable outsourced polynomial multiplication protocol OPVML which is further exploited in designing our final protocol PVOPM for verifiable privacy-preserving outsourced pattern matching. Without exploiting public key FHE, the proposed PVOPM achieves both verifiability and text/pattern privacy against the collusion between the cloud and malicious receiver/sender, by generating authentication proofs of constant size and executing constant times of any one-way trapdoor permutation, independent to both the text size n and the pattern size m. Finally, formal security proof under universal composable (UC) model and extensive evaluations demonstrate the efficiency and practicability of our proposed PVOPM.

Automated summary

This research proposes a series of protocols to achieve privacy protection and verifiability for outsourced pattern matching, effectively resisting collusion attacks between the cloud and malicious receiver/sender without utilizing public key fully homomorphic encryption.