面向连接关键词可搜索加密的查询恢复攻击

杜瑞颖; 沈蓓; 何琨; 赵陈斌; 王贝宁; 陈晶

doi:10.11959/j.issn.1000-436x.2024141

您当前的位置：

首页 >

文章列表页 >

面向连接关键词可搜索加密的查询恢复攻击

学术论文 | 更新时间：2024-09-10

- 面向连接关键词可搜索加密的查询恢复攻击
- Query recovery attacks against conjunctive keyword searchable encryption
- 通信学报 2024年45卷第8期页码：125-135
- 作者机构：
  
  武汉大学国家网络安全学院，湖北武汉 430040
- 作者简介：
  
  [ "杜瑞颖（1964- ），女，河南新乡人，博士，武汉大学教授、博士生导师，主要研究方向为网络安全、隐私保护等。" ]
  [ "沈蓓（2001- ），女，湖北赤壁人，武汉大学硕士生，主要研究方向为网络安全、应用密码学等。" ]
  [ "何琨（1986- ），男，湖北武汉人，博士，武汉大学副教授、博士生导师，主要研究方向为应用密码学、网络安全、云计算安全、人工智能安全、区块链安全等。" ]
  [ "赵陈斌（1996- ），男，安徽六安人，武汉大学博士生，主要研究方向为网络安全、应用密码学等。" ]
  [ "王贝宁（1998- ），女，湖北武汉人，武汉大学博士生，主要研究方向为可搜索加密、应用密码学等。" ]
  [ "陈晶（1981- ），男，湖北武汉人，博士，武汉大学教授、博士生导师，主要研究方向为网络安全、应用密码学、分布式系统安全等。" ]
- 基金信息：
  
  国家重点研发计划基金资助项目;The National Key Research and Development Program of China(2021YFB2700200);中央高校基本科研业务费专项资金资助项目;The Fundamental Research Funds for the Central Universities(2042022kf1195);国家自然科学基金资助项目;The National Natural Science Foundation of China(62172303);湖北省重点研发计划基金资助项目(2021BAA190;2022BAA039);山东省重点研发计划基金资助项目;The Key Research and Development Program of Shandong Province(2022CXPT055)
- DOI：10.11959/j.issn.1000-436x.2024141
  中图分类号： TP309
- 收稿日期：2024-03-26，
  
  修回日期：2024-06-28，
  
  纸质出版日期：2024-08-25
- 稿件说明：
移动端阅览
杜瑞颖,沈蓓,何琨等.面向连接关键词可搜索加密的查询恢复攻击[J].通信学报,2024,45(08):125-135.

DU Ruiying,SHEN Bei,HE Kun,et al.Query recovery attacks against conjunctive keyword searchable encryption[J].Journal on Communications,2024,45(08):125-135.
杜瑞颖,沈蓓,何琨等.面向连接关键词可搜索加密的查询恢复攻击[J].通信学报,2024,45(08):125-135. DOI： 10.11959/j.issn.1000-436x.2024141.

DU Ruiying,SHEN Bei,HE Kun,et al.Query recovery attacks against conjunctive keyword searchable encryption[J].Journal on Communications,2024,45(08):125-135. DOI： 10.11959/j.issn.1000-436x.2024141.

摘要

为了恢复连接关键词可搜索加密方案中的用户查询，提出了2种针对连接查询可搜索加密方案的攻击方法，分别是交叉泄露攻击和频率匹配攻击。首先，从泄露中提取候选关键词集合；然后，分别利用关键词对结果模式泄露和查询频率信息进行过滤。结果表明，在交叉泄露攻击中，当攻击者仅掌握10%的数据集时，若关键词在空间为100，查询恢复的准确率可高达90%，将关键词空间扩大至1 000，攻击者依然能够恢复50%以上的查询；在频率匹配攻击中，即使攻击者仅已知不准确的频率分布信息，也至少可以准确恢复70%的查询。

Abstract

In order to recover user’s queries in conjunctive keyword searchable encryption schemes

two attacks against the conjunctive keyword searchable encryption schemes were proposed

such as cross leakage attack and frequency matching attack. Firstly

a set of candidate keywords were extracted from the leakage. Then the keywords were filtered according to the keyword pair result pattern leakage and query frequency information respectively. Results show that in the cross leakage attack

with knowledge of only 10% of the dataset

the accuracy of query recovery can reach up to 90% if the keyword space is 100. And more than 50% of the queries are still able to recovered by the attacker if the keyword space is expanded to 1 000. In frequency matching attack

even with only inaccurate frequency distribution information known to the attacker

at least 70% of queries can be accurately recovered.

关键词

Keywords

references

SONG D X , WAGNER D , PERRIG A . Practical techniques for searches on encrypted data [C ] // Proceedings of the IEEE Symposium on Security and Privacy . Piscataway : IEEE Press , 2000 : 44 - 55 .

CURTMOLA R , GARAY J , KAMARA S , et al . Searchable symmetric encryption: improved definitions and efficient constructions [J ] . Journal of Computer Security , 2011 , 19 ( 5 ): 895 - 934 .

CASH D , JARECKI S , JUTLA C , et al . Highly-scalable searchable symmetric encryption with support for Boolean queries [C ] // Annual Cryptology Conference . Berlin : Springer , 2013 : 353 - 373 .

LAI S Q , PATRANABIS S , SAKZAD A , et al . Result pattern hiding searchable encryption for conjunctive queries [C ] // Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2018 : 745 - 762 .

DEMERTZIS I , PAPADOPOULOS D , PAPAMANTHOU C , et al . SEAL: attack mitigation for encrypted databases via adjustable leakage [C ] // 29th USENIX Security Symposium (USENIX Security 20) . Berkeley : USENIX Association , 2020 : 2433 - 2450 .

GARG S , MOHASSEL P , PAPAMANTHOU C . TWORAM: efficient oblivious RAM in two rounds with applications to searchable encryption [C ] // Annual International Cryptology Conference . Berlin : Springer , 2016 : 563 - 592 .

ZHANG Y , KATZ J , PAPAMANTHOU C . All your queries are belong to us: the power of file-injection attacks on searchable encryption [C ] // 25th USENIX Security Symposium (USENIX Security 16) . Berkeley : USENIX Association , 2016 : 707 - 720 .

ISLAM M S , KUZU M , KANTARCIOGLU M . Access pattern disclosure on searchable encryption: ramification, attack and mitigation [C ] // Proceedings of the 19th Annual Network and Distributed System Security Symposium . Reston : Internet Society , 2012 : 12 .

NING J , HUANG X , POH G S , et al . LEAP: leakage-abuse attack on efficiently deployable, efficiently searchable encryption with partially known dataset [C ] // Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2021 : 2307 - 2320 .

OYA S , KERSCHBAUM F . Hiding the access pattern is not enough: Exploiting search pattern leakage in searchable encryption [C ] // 30th USENIX Security Symposium (USENIX Security 21) . Berkeley : USENIX Association , 2021 : 127 - 142 .

OYA S , KERSCHBAUM F . IHOP: improved statistical query recovery against searchable symmetric encryption through quadratic optimization [J ] . arXiv Preprint , arXiv: 2110.04180 , 2021 .

CASH D , GRUBBS P , PERRY J , et al . Leakage-abuse attacks against searchable encryption [C ] // Proceedings of the Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2015 : 668 - 679 .

BLACKSTONE L , KAMARA S , MOATAZ T . Revisiting leakage abuse attacks [C ] // Proceedings of the 2020 Network and Distributed System Security Symposium . Reston : Internet Society , 2020 : 1 - 18 .

LIU C , ZHU L H , WANG M Z , et al . Search pattern leakage in searchable encryption: attacks and new construction [J ] . Information Sciences , 2014 , 265 : 176 - 188 .

KIRKPATRICK S , Jr GELATT C D , VECCHI M P . Optimization by simulated annealing [J ] . Science , 1983 , 220 ( 4598 ): 671 - 680 .

PATRANABIS S , MUKHOPADHYAY D . Forward and backward private conjunctive searchable symmetric encryption [C ] // Proceedings of the 2021 Network and Distributed System Security Symposium . Reston : Internet Society , 2021 : 1 - 52 .

BOST R , MINAUD B , OHRIMENKO O . Forward and backward private searchable encryption from constrained cryptographic primitives [C ] // Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2017 : 1465 - 1482 .

CHAMANI J G , PAPADOPOULOS D , KARBASFORUSHAN M , et al . Dynamic searchable encryption with optimal search in the presence of deletions [J ] . IACR Cryptol EPrint Arch , 2022 , 2022 : 648 .

CHEN T Y , XU P , PICEK S , et al . The power of bamboo: on the post-compromise security for searchable symmetric encryption [C ] // Proceedings of the 2023 Network and Distributed System Security Symposium . Reston : Internet Society , 2023 : 1 - 18 .

YUAN D D , ZUO C , CUI S J , et al . Result-pattern-hiding conjunctive searchable symmetric encryption with forward and backward privacy [J ] . Proceedings on Privacy Enhancing Technologies , 2023 ( 2 ): 40 - 58 .

WANG B , YU S C , LOU W J , et al . Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud [C ] // Proceedings of the IEEE Conference on Computer Communications . Piscataway : IEEE Press , 2014 : 2112 - 2120 . .

SUN S F , ZUO C , LIU J K , et al . Non-interactive multi-client searchable encryption: realization and implementation [J ] . IEEE Transactions on Dependable and Secure Computing , 2022 , 19 ( 1 ): 452 - 467 .

WANG J , CHOW S S M . Omnes pro uno: practical multi-writer encrypted database [C ] // 31st USENIX Security Symposium (USENIX Security 22) . Berkeley : USENIX Association , 2022 : 2371 - 2388 .

RIZOMILIOTIS P , MOLLA E , GRITZALIS S . REX: a searchable symmetric encryption scheme supporting range queries [C ] // Proceedings of the 2017 on Cloud Computing Security Workshop . New York : ACM Press , 2017 : 29 - 37 .

ZHENG Y D , LU R X , ZHANG S N , et al . PMRQ: achieving efficient and privacy-preserving multidimensional range query in eHealthcare [J ] . IEEE Internet of Things Journal , 2022 , 9 ( 18 ): 17468 - 17479 .

WANG Y L , WANG J F , SUN S F , et al . Towards multi-user searchable encryption supporting Boolean query and fast decryption [C ] // International Conference on Provable Security . Berlin : Springer , 2017 : 24 - 38 .

GRUBBS P , LACHARITÉ M S , MINAUD B , et al . Learning to reconstruct: statistical learning theory and encrypted database attacks [C ] // Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP) . Piscataway : IEEE Press , 2019 : 1067 - 1083 .

GUI Z , JOHNSON O , WARINSCHI B . Encrypted databases: new volume attacks against range queries [C ] // Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2019 : 361 - 378 .

FREDMAN M L , TARJAN R E . Fibonacci heaps and their uses in improved network optimization algorithms [J ] . Journal of the ACM (JACM) , 1987 , 34 ( 3 ): 596 - 615 .

XU L , ZHENG L Q , XU C Z , et al . Leakage-abuse attacks against forward and backward private searchable symmetric encryption [C ] // Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2023 : 3003 - 3017 .

GUI Z C , PATERSON K G , PATRANABIS S . Rethinking searchable symmetric encryption [C ] // Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP) . Piscataway : IEEE Press , 2023 : 1401 - 1418 .

浏览量

下载量

CSCD

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

提交

工具集

关联资源

基于分层结构的匹配量隐藏加密多重映射方案

支持安全共享的云存储系统研究

基于动态布谷鸟过滤器的多关键词可搜索加密方案

面向云存储且支持重加密的多关键词属性基可搜索加密方案

面向云存储的属性基双边访问控制方案