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

王健旭; 李睿; 李银

doi:10.11959/j.cnki.cn2096-109x.2024061

您当前的位置：

首页 >

文章列表页 >

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

学术论文

- 保护搜索内容的字符串模式匹配算法研究
- Efficient algorithms for string pattern matching to protect search content
- 网络与信息安全学报 2024年10卷第4期页码：159-174
- 作者机构：
  
  东莞理工学院，广东东莞 523808
- 作者简介：
  
  [ "王健旭（1997- ），男，黑龙江绥化人，东莞理工学院硕士生，主要研究方向为计算机网络与信息安全。" ]
  [ "李睿（1975- ），男，湖南汨罗人，博士，东莞理工学院教授，主要研究方向为数据隐私保护。" ]
  [ "李银（1982- ），男，河南信阳人，博士，东莞理工学院副教授，主要研究方向为安全数据库、计算机代数。" ]
- 基金信息：
  
  国家重点研发计划(2021YFB3101303);国家自然科学基金(61972089;62372107)
- DOI：10.11959/j.cnki.cn2096-109x.2024061
  中图分类号： TP393
- 收稿：2024-03-19，
  
  修回：2024-07-09，
  
  纸质出版：2024-08-25
- 稿件说明：
移动端阅览
王健旭, 李睿, 李银. 保护搜索内容的字符串模式匹配算法研究[J]. 网络与信息安全学报, 2024, 10(4): 159-174.

Format: WANG J X, LI R, LI Y. Efficient algorithms for string pattern matching to protect search content[J]. Chinese Journal of Network and Information Security, 2024, 10(4): 159-174.
王健旭, 李睿, 李银. 保护搜索内容的字符串模式匹配算法研究[J]. 网络与信息安全学报, 2024, 10(4): 159-174. DOI： 10.11959/j.cnki.cn2096-109x.2024061.

Format: WANG J X, LI R, LI Y. Efficient algorithms for string pattern matching to protect search content[J]. Chinese Journal of Network and Information Security, 2024, 10(4): 159-174. DOI： 10.11959/j.cnki.cn2096-109x.2024061.

摘要

高效的在线字符串模式匹配算法对云数据库检索至关重要，然而搜索内容的泄露会威胁用户隐私。现有的字符串模式匹配算法没有考虑用户搜索内容的保护，可搜索加密方案虽然可以保护用户的搜索内容，但存在索引构建代价大、检索效率低等问题。因此，提出了两种保护用户搜索内容的模式匹配算法：基于分布式点函数的模式匹配（pattern matching based on distributed point function，PMDPF）算法和基于分布式点函数的跳跃式模式匹配（jumping pattern matching based on distributed point function，JPMDPF）算法。PMDPF算法利用指纹函数以及分布式点函数构造模式串真值表，并分发给两台独立的服务器，把搜索中字符对比操作转换为查表操作，从而保护搜索内容。为了提升搜索效率，提出了JPMDPF算法。通过字符跳转，JPMDPF算法以泄露更多信息为代价，其搜索效率比PMDPF算法平均提高了约

倍，其中

为搜索内容长度，同时显著降低了因指纹函数碰撞而导致的误判的概率。实验结果表明，PMDPF算法的搜索效率比基于指纹函数的经典算法提高约5%，并优于现有的可搜索加密方案，PMDPF算法的搜索耗时在搜索内容长度为4时是JPMDPF算法的4.2倍。

Abstract

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.

关键词

Keywords

references

AL-SSULAMI A M , AZMI A M , MATHKOUR H , et al . LsHASHq: a string matching algorithm exploiting longer q-gram shifting [J ] . Information Processing & Management , 2022 , 59 ( 5 ): 103057 .

LECROQ T . Fast exact string matching algorithms [J ] . Information Processing Letters , 2007 , 102 ( 6 ): 229 - 235 .

SUNDAY D M . A very fast substring search algorithm [J ] . Communications of the ACM , 1990 , 33 ( 8 ): 132 - 142 .

FARO S , LECROQ T . Efficient variants of the backward-oracle-matching algorithm [J ] . International Journal of Foundations of Computer Science , 2009 , 20 ( 6 ): 967 - 984 .

PELTOLA H , TARHIO J . Alternative algorithms for bit-parallel string matching [C ] // International Symposium on String Processing and Information Retrieval . Berlin, Heidelberg : Springer , 2003 : 80 - 93 .

CHEN Y B , HE J S , WEI W , et al . A multi-model approach for user portrait [J ] . Future Internet , 2021 , 13 ( 6 ): 147 .

MEHROTRA S , SHARMA S , ULLMAN J , et al . Partitioned data security on outsourced sensitive and non-sensitive data [C ] // Proceedings of the 2019 IEEE 35th International Conference on Data Engineering (ICDE) . Piscataway : IEEE Press , 2019 : 650 - 661 .

徐琳 , 魏晓超 , 蔡国鹏 , 等 . 一个高效的安全两方近似模式匹配协议 [J ] . 计算机研究与发展 , 2022 , 59 ( 8 ): 1819 - 1830 .

XU L , WEI X C , CAI G P , et al . An efficient secure two-party approximate pattern matching protocol [J ] . Journal of Computer Research and Development , 2022 , 59 ( 8 ): 1819 - 1830 .

LI R , LIU A X . Adaptively secure and fast processing of conjunctive queries over encrypted data [J ] . IEEE Transactions on Knowledge and Data Engineering , 2022 , 34 ( 4 ): 1588 - 1602 .

CHOR B , KUSHILEVITZ E , GOLDREICH O , et al . Private information retrieval [J ] . Journal of the ACM , 1998 , 45 ( 6 ): 965 - 981 .

DVIR Z , GOPI S . 2-server PIR with subpolynomial communication [J ] . Journal of the ACM , 2016 , 63 ( 4 ): 1 - 15 .

CORRIGAN-GIBBS H , KOGAN D . Private information retrieval with sublinear online time [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Cham : Springer , 2020 : 44 - 75 .

YU M K , YANG K C , WEI L B , et al . Practical private information retrieval supporting keyword search in the cloud [C ] // Proceedings of the 2014 Sixth International Conference on Wireless Communications and Signal Processing (WCSP) . Piscataway : IEEE Press , 2014 : 1 - 6 .

WONG W K , CHEUNG D W L , KAO B , et al . Secure kNN computation on encrypted databases [C ] // Proceedings of the 2009 ACM SIGMOD International Conference on Management of data . New York : ACM , 2009 : 139 - 152 .

SUN J F , BAO Y Y , NIE X Y , et al . Attribute-hiding predicate encryption with equality test in cloud computing [J ] . IEEE Access , 2018 , 6 : 31621 - 31629 .

FARO S , LECROQ T . The exact online string matching problem: a review of the most recent results [J ] . ACM Computing Surveys , 2013 , 45 ( 2 ): 13 .

DESMOULINS N , FOUQUE P A , ONETE C , et al . Pattern matching on encrypted streams [C ] // International Conference on the Theory and Application of Cryptology and Information Security . Cham : Springer , 2018 : 121 - 148 .

BOUSCATIÉ É , CASTAGNOS G , SANDERS O . Public key encryption with flexible pattern matching [C ] // International Conference on the Theory and Application of Cryptology and Information Security . Cham : Springer , 2021 : 342 - 370 .

GILBOA N , ISHAI Y . Distributed point functions and their applications [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Berlin, Heidelberg : Springer , 2014 : 640 - 658 .

BOYLE E , COUTEAU G , GILBOA N , et al . Efficient pseudorandom correlation generators: silent OT extension and more [C ] // Annual International Cryptology Conference . Cham : Springer , 2019 : 489 - 518 .

BRESLAUER D , GALIL Z . Real-time streaming string-matching [J ] . ACM Transactions on Algorithms , 2014 , 10 ( 4 ): 1 - 12 .

KARP R M , RABIN M O . Efficient randomized pattern-matching algorithms [J ] . IBM Journal of Research and Development , 1987 , 31 ( 2 ): 249 - 260 .

GOLDREICH O , MICALI S , WIGDERSON A . How to play ANY mental game [C ] // Proceedings of the Nineteenth Annual ACM Conference on Theory of computing-STOC '87 . New York : ACM , 1987 : 219 - 219 .

ENGLISH O . Oxford english dictionary [J ] . Encyclopedia of Swearing , 1976 : 334 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据