Query recovery attacks against conjunctive keyword searchable encryption

DU Ruiying; SHEN Bei; HE Kun; ZHAO Chenbin; WANG Beining; CHEN Jing

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

您当前的位置：

首页 >

文章列表页 >

Query recovery attacks against conjunctive keyword searchable encryption

Papers | 更新时间：2024-09-10

- Query recovery attacks against conjunctive keyword searchable encryption
- Journal on Communications Vol. 45, Issue 8, Pages: 125-135(2024)
- 作者机构：
  
  武汉大学国家网络安全学院，湖北武汉 430040
- 作者简介：
- 基金信息：
  
  The Key Research and Development Program of Hubei Province(2021BAA190;2022BAA039)
- DOI：10.11959/j.issn.1000-436x.2024141
  CLC： TP309
- Received：26 March 2024，
  
  Revised：2024-06-28，
  
  Published：25 August 2024
- 稿件说明：
移动端阅览
杜瑞颖,沈蓓,何琨等.面向连接关键词可搜索加密的查询恢复攻击[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 .

Views

1651

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Volume-hiding encrypted multi-map scheme based on hierarchical structure

Research on cloud storage systems supporting secure sharing

Multi-keyword searchable encryption scheme based on dynamic cuckoo filter

Multi-keyword attribute-based searchable encryption scheme supporting re-encryption for cloud storage

Attribute-based bilateral access control scheme for cloud storage

Related Author

Jing CHEN

Hanxing LI

Kun HE

Meng JIA

Yuqing LI

Ruiying DU

Yan SONG

Zhen HAN

Related Institution

Beijing Key Laboratory of Security and Privacy in Intelligent Transportation,Beijing Jiaotong University

Science and Technology on Information Assurance Laboratory

School of Information Science and Engineering, University of Jinan

Quan Cheng Laboratory

Shandong Provincial Key Laboratory of Network-based Intelligent Computing, University of Jinan

AI问答

⁰