保护搜索内容的字符串模式匹配算法研究

Efficient algorithms for string pattern matching to protect search content

高效的在线字符串模式匹配算法对云数据库检索至关重要,然而搜索内容的泄露会威胁用户隐私。现有的字符串模式匹配算法没有考虑用户搜索内容的保护,可搜索加密方案虽然可以保护用户的搜索内容,但存在索引构建代价大、检索效率低等问题。因此,提出了两种保护用户搜索内容的模式匹配算法:基于分布式点函数的模式匹配(pattern matching based on distributed point function,PMDPF)算法和基于分布式点函数的跳跃式模式匹配(jumping pattern matching based on distributed point function,JPMDPF)算法。PMDPF算法利用指纹函数以及分布式点函数构造模式串真值表,并分发给两台独立的服务器,把搜索中字符对比操作转换为查表操作,从而保护搜索内容。为了提升搜索效率,提出了JPMDPF算法。通过字符跳转,JPMDPF算法以泄露更多信息为代价,其搜索效率比PMDPF算法平均提高了约m倍,其中m为搜索内容长度,同时显著降低了因指纹函数碰撞而导致的误判的概率。实验结果表明,PMDPF算法的搜索效率比基于指纹函数的经典算法提高约5%,并优于现有的可搜索加密方案,PMDPF算法的搜索耗时在搜索内容长度为4时是JPMDPF算法的4.2倍。

Efficient algorithms for online string pattern matching have been deemed crucial for cloud database retrieval.However,the potential leaking of search content has been recognized as a threat to users'privacy.Existing string pattern matching algorithms have not been designed to consider the protection of users'search content.Although searchable encryption schemes can protect users'search content,they have been associated with high index construction costs and inefficient retrieval.Two pattern matching algorithms were proposed to protect users'search content:PMDPF(pattern matching based on distributed point function)and JPMDPF(jumping pattern matching based on distributed point function).In the PMDPF algorithm,a pattern string was provided to protect the search content,and a distributed point function combined with a fingerprint function was utilized to construct true value tables,which were then sent to two independent servers.Character comparison operations were transformed into table lookup operations to conceal the characters that needed to be checked.To enhance search efficiency,a jump pattern matching algorithm(JPMDPF)was proposed,based on the distributed point function.In this approach,character skipping was employed to induce the JPMDPF algorithm,which achieved a significant improvement in search efficiency over the PMDPF algorithm,albeit with the trade-off of revealing more information.On average,the search efficiency of JPMDPF was increased by approximately m-fold,where m represented the length of the pattern string.Concurrently,there was a significant reduction in the probability of misjudgments due to collisions within the fingerprinting function.The experimental results demonstrate that the search efficiency of the PMDPF algorithm is approximately 5%higher than that of the classical algorithm based on the fingerprint function.It outperforms existing searchable encryption schemes.The search time of the PMDPF algorithm is found to be 4.2 times that of JPMDPF when the length of the search content is 4.