高效的在线字符串模式匹配算法对云数据库检索至关重要,然而搜索内容的泄露会威胁用户隐私。现有的字符串模式匹配算法没有考虑用户搜索内容的保护,可搜索加密方案虽然可以保护用户的搜索内容,但存在索引构建代价大、检索效率低等问题...高效的在线字符串模式匹配算法对云数据库检索至关重要,然而搜索内容的泄露会威胁用户隐私。现有的字符串模式匹配算法没有考虑用户搜索内容的保护,可搜索加密方案虽然可以保护用户的搜索内容,但存在索引构建代价大、检索效率低等问题。因此,提出了两种保护用户搜索内容的模式匹配算法:基于分布式点函数的模式匹配(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倍。展开更多
文摘高效的在线字符串模式匹配算法对云数据库检索至关重要,然而搜索内容的泄露会威胁用户隐私。现有的字符串模式匹配算法没有考虑用户搜索内容的保护,可搜索加密方案虽然可以保护用户的搜索内容,但存在索引构建代价大、检索效率低等问题。因此,提出了两种保护用户搜索内容的模式匹配算法:基于分布式点函数的模式匹配(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倍。