Method for reducing the storage overhead of the IEX scheme

ZHANG Xiangbo; MA Changshe; SU Yuchen

doi:10.11959/j.issn.2096-109x.2025052

您当前的位置：

首页 >

文章列表页 >

Method for reducing the storage overhead of the IEX scheme

Papers | 更新时间：2025-11-08

- Method for reducing the storage overhead of the IEX scheme
- Chinese Journal of Network and Information Security Vol. 11, Issue 5, Pages: 149-161(2025)
- 作者机构：
  
  华南师范大学计算机学院，广东广州 510631
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2025052
  CLC： TP393
- Received：01 February 2025，
  
  Revised：2025-06-19，
  
  Published：25 October 2025
- 稿件说明：
移动端阅览
张象博, 马昌社, 苏雨晨. 面向IEX方案存储开销优化的方法[J]. 网络与信息安全学报, 2025, 11(5): 149-161.

ZHANG X B, MA C S, SU Y C. Method for reducing the storage overhead of the IEX scheme[J]. Chinese Journal of Network and Information Security, 2025, 11(5): 149-161.
张象博, 马昌社, 苏雨晨. 面向IEX方案存储开销优化的方法[J]. 网络与信息安全学报, 2025, 11(5): 149-161. DOI： 10.11959/j.issn.2096-109x.2025052.

ZHANG X B, MA C S, SU Y C. Method for reducing the storage overhead of the IEX scheme[J]. Chinese Journal of Network and Information Security, 2025, 11(5): 149-161. DOI： 10.11959/j.issn.2096-109x.2025052.

摘要

可搜索对称加密允许在加密数据中进行高效搜索，IEX是首个实现次线性搜索复杂度且支持布尔查询的方案，但该方案的服务器存储开销较大。为减少服务器存储开销，提出了一种基于三角矩阵的数据组织方法，该方法可以减少约50%的两两关键字的文档交集数据量。基于上述数据组织方法，进一步提出了IEX改进方案IEX-RS。实验结果表明，与IEX方案相比，IEX-RS方案在保持相同搜索性能的同时，可减少49%的服务器存储开销。

Abstract

Searchable symmetric encryption was recognized as an efficient method for searching within encrypted data. The IEX scheme was the first to achieve sublinear search complexity while supporting Boolean queries; however

it was found to incur high server storage overhead. To reduce the storage cost on the server side

a data organization method based on triangular matrices was proposed. This method was shown to reduce the data volume of pairwise keyword-document intersections by approximately 50%. Based on the aforementioned data organization method

an improved scheme named IEX-RS was further proposed. Experimental results demonstrate that the IEX-RS scheme significantly reduces server storage overhead by 49%

while search performance equivalent to that of the original IEX scheme is maintained.

关键词

Keywords

references

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

CHASE M , KAMARA S . Structured encryption and controlled disclosure [C ] // Proceeding of Advances in Cryptology -ASIACRYPT 2010 . Berlin : Springer , 2010 : 577 - 594 .

CASH D , JARECKI S , JUTLA C , et al . Highly-scalable searchable symmetric encryption with support for Boolean queries [C ] // Proceeding of Advances in Cryptology – CRYPTO 2013 . Berlin : Springer , 2013 : 353 - 373 .

KAMARA S , MOATAZ T . Boolean searchable symmetric encryption with worst-case sub-linear complexity [C ] // Proceeding of Advances in Cryptology – EUROCRYPT 2017 . Berlin : Springer , 2017 : 94 - 124 .

CURTMOLA R , GARAY J , KAMARA S , et al . Searchable symmetric encryption: improved definitions and efficient constructions [C ] // Proceeding of the 13th ACM Conference on Computer and Communications Security . New York : ACM Press , 2006 : 79 - 88 .

CASH D , JAEGER J , JARECKI S , et al . Dynamic searchable encryption in very-large databases: data structures and implementation [C ] // Proceeding of the Network and Distributed System Security Symposium (NDSS ' 14). 2014 : 23 - 26 .

BOST R . ∑oφoς: forward secure searchable encryption [C ] // Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM Press , 2016 : 1143 - 1154 .

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 .

GOLLE P , STADDON J , WATERS B . Secure conjunctive keyword search over encrypted data [C ] // Proceedings of Applied Cryptography and Network Security . Berlin : Springer , 2004 : 31 - 45 .

BALLARD L , KAMARA S , MONROSE F . Achieving efficient conjunctive keyword searches over encrypted data [C ] // Proceedings of Information and Communications Security (ICICS 2005) . Berlin : Springer , 2005 : 414 - 426 .

PAPPAS V , KRELL F , VO B , et al . Blind seer: a scalable private DBMS [C ]] // Proceedings of 2014 IEEE Symposium on Security and Privacy . Piscataway : IEEE Press , 2014 : 359 - 374 .

FISCH B A , VO B , KRELL F , et al . Malicious-client security in blind seer: a scalable private DBMS [C ] // Proceedings of 2015 IEEE Symposium on Security and Privacy . Piscataway : IEEE Press , 2015 : 395 - 410 .

BELLARE M , HOANG V T , ROGAWAY P . Foundations of garbled circuits [C ] // Proceedings of the 2012 ACM Conference on Computer and Communications Security . New York : ACM Press , 2012 : 784 - 796 .

LI R , LIU A X . Adaptively secure conjunctive query processing over encrypted data for cloud computing [C ] // Proceedings of 2017 IEEE 33rd International Conference on Data Engineering (ICDE) . Piscataway : IEEE Press , 2017 : 697 - 708 .

WU Z , LI K . VBTree: forward secure conjunctive queries over encrypted data for cloud computing [J ] . The VLDB Journal , 2019 , 28 ( 1 ): 25 - 46 .

ZUO C , SUN S F , LIU J K , et al . Forward and backward private dynamic searchable symmetric encryption for conjunctive queries [J ] . Cryptology ePrint Archive , 2020 : 1357 .

ISLAM M S , KUZU M , KANTARCIOGLU M . Access pattern disclosure on searchable encryption: ramification, attack and mitigation [C ] // Proceedings of the 2012 Network and Distributed System Security Symposium (NDSS 2012) . Virginia : the Internet Society , 2012 .

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

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

LAI S , 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 (CCS '18) . New York : ACM Press , 2018 : 745 - 762 .

PATRANABIS S , MUKHOPADHYAY D . Forward and backward private conjunctive searchable symmetric encryption [C ] // Proceedings of the 28th Annual Network and Distributed System Security Symposium (NDSS 2021) . Virginia : the Internet Society , 2021 : 342 - 1345 .

MA C , GU Y , LI H . Practical searchable symmetric encryption supporting conjunctive queries without keyword pair result pattern leakage [J ] . IEEE Access , 2020 , 8 : 107510 - 107526 .

ZUO C , LAI S , YUAN X , et al . Searchable encryption for conjunctive queries with extended forward and backward privacy [J ] . Cryptology ePrint Archive , 2021 : 1585 .

SUN S F , STEINFELD R , LAI S , et al . Practical non-interactive searchable encryption with forward and backward privacy [C ] // Proceedings of Network and Distributed System Security Symposium . Virginia : the Internet Society , 2021 .

JUTLA C , PATRANABIS S . Efficient searchable symmetric encryption for join queries [C ] // Proceedings of Advances in Cryptology -ASIACRYPT 2022 . Berlin : Springer , 2022 : 304 - 333 .

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

BAG A , TALAPATRA D , RASTOGI A , et al . Two-in-one-sse: fast, scalable and storage-efficient searchable symmetric encryption for conjunctive and disjunctive boolean queries [C ] // Proceedings of Privacy Enhancing Technologies . 2023 : 115 - 139 .

BAG A , PATRANABIS S , MUKHOPADHYAY D . Tokenised multi-client provisioning for dynamic searchable encryption with forward and backward privacy [C ] // Proceedings of the 19th ACM Asia Conference on Computer and Communications Security . New York : ACM Press , 2024 : 1691 - 1707 .

YUAN D , CUI S , RUSSELLO G . Result pattern hiding Boolean searchable encryption: achieving negligible false positive rates in low storage overhead [J ] . Cryptology ePrint Archive , 2024 .

PATEL S , PERSIANO G , SEO J Y , et al . Efficient Boolean search over encrypted data with reduced leakage [C ] // Proceedings of Advances in Cryptology – ASIACRYPT 2021 . Berlin : Springer , 2021 : 577 - 607 .

郭斯栩 , 何申 , 粟栗 , 等 . 基于多关键字的Top- k 布尔可搜索加密方案 [J ] . 计算机研究与发展 , 2022 , 59 ( 8 ): 1841 - 1852 .

GUO S X , HE S , SU L , et al . Top- k Boolean searchable encryption scheme based on multiple keywords [J ] . Journal of Computer Research and Development , 2022 , 59 ( 8 ): 1841 - 1852 .

FERREIRA B , PORTELA B , OLIVEIRA T , et al . Boolean searchable symmetric encryption with filters on trusted hardware [J ] . IEEE Transactions on Dependable and Secure Computing , 2022 , 19 ( 2 ): 1307 - 1319 .

杨紫依 , 马昌社 , 谢南江 . 支持联合查询和交叉模式隐藏的结构加密 [J ] . 网络与信息安全学报 , 2024 , 10 ( 3 ): 175 - 187 .

YANG Z Y , MA C S , XIE N J . Cross pattern hiding structured encryption for conjunctive queries [J ] . Chinese Journal of Network and Information Security , 2024 , 10 ( 3 ): 175 - 187 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

STE-based encrypted relational database scheme with reduced leakages

Related Author

SU Yuchen

MA Changshe

Related Institution

No data

⁰