高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

优化局部性的前向安全动态对称可搜索加密方案

郭宇韬 柳枫 王峰 薛开平

郭宇韬, 柳枫, 王峰, 薛开平. 优化局部性的前向安全动态对称可搜索加密方案[J]. 电子与信息学报, 2025, 47(8): 2780-2790. doi: 10.11999/JEIT250107
引用本文: 郭宇韬, 柳枫, 王峰, 薛开平. 优化局部性的前向安全动态对称可搜索加密方案[J]. 电子与信息学报, 2025, 47(8): 2780-2790. doi: 10.11999/JEIT250107
GUO Yutao, LIU Feng, WANG Feng, XUE Kaiping. Locality-optimized Forward-secure Dynamic Searchable Symmetric Encryption[J]. Journal of Electronics & Information Technology, 2025, 47(8): 2780-2790. doi: 10.11999/JEIT250107
Citation: GUO Yutao, LIU Feng, WANG Feng, XUE Kaiping. Locality-optimized Forward-secure Dynamic Searchable Symmetric Encryption[J]. Journal of Electronics & Information Technology, 2025, 47(8): 2780-2790. doi: 10.11999/JEIT250107

优化局部性的前向安全动态对称可搜索加密方案

doi: 10.11999/JEIT250107 cstr: 32379.14.JEIT250107
基金项目: 国家自然科学基金(62372425),中国科学院青年创新促进会优秀会员支持项目(Y202093)
详细信息
    作者简介:

    郭宇韬:男,硕士生,研究方向为网络安全和应用密码学

    柳枫:男,博士生,研究方向为网络安全和应用密码学

    王峰:男,实验师,研究方向为身份认证和授权管理、访问控制、区块链系统

    薛开平:男,教授,研究方向为下一代网络体系结构与网络安全

    通讯作者:

    王峰 wf0229@ustc.edu.cn

  • 中图分类号: TN918; TP309

Locality-optimized Forward-secure Dynamic Searchable Symmetric Encryption

Funds: The National Natural Science Foundation of China (62372425), The Youth Innovation Promotion Association of the Chinese Academy of Sciences (CAS)(Y202093)
  • 摘要: 对称可搜索加密是实现在云存储场景下加密搜索的一项重要原语。动态对称可搜索加密是支持动态增加和删除数据的对称可搜索加密,在多数场景相较静态方案更为实用。对称可搜索加密中局部性指的是搜索时服务器需要进行的非连续存储访问的次数,是影响搜索效率的重要指标之一。然而,动态对称可搜索加密中局部性与前向安全性的要求相矛盾。差的局部性导致了搜索时间随结果数量的简单线性增长,进而严重影响高频关键词的搜索效率。现有针对前向安全动态对称可搜索加密进行局部性优化的方案要么存在对两次搜索之间的更新次数的限制,要么更新效率和读效率较低。该文提出了新的局部性优化方案,能够转换任意符合要求的前向安全动态对称可搜索加密方案为优化局部性的前向安全动态对称可搜索加密方案,同时不损害更新效率和读效率在内的其他重要性能指标。方案基于客户端缓冲和分批打包,打包内同关键词更新可连续读取,有效限制了各关键词的局部性上界。同时,该文设计并使用了安全的打包格式,通过安全证明确保了转换后方案在保证前向安全的同时不会引入额外信息泄露。理论和实验分析证明了该方案在极大提升高频关键词搜索效率的同时,不对更新效率以及其他关键词的搜索效率产生显著的负面影响。
  • 图  1  转换后方案的更新流程和搜索流程

    图  2  简单的打包方式存在的信息泄露问题

    图  3  $L = 3$对应打包及其合适区间的划分

    图  4  更新时间对比

    图  5  搜索延迟对比

    1  初始化$ {\text{Tran}}{{\text{s}}_{L,|W|}}[{\varPi }].{\text{Setup}}(\lambda ; \bot ) $

     输入:安全参数$ \lambda $
     输出:客户端输出密钥$ K = {K_{\varPi }} $、状态$ {\text{st}} = (e,{\text{Buffer}},{\text{s}}{{\text{t}}_{\varPi }}) $;
     服务器输出加密数据库$ {\text{EDB = (Packs,ED}}{{\text{B}}_{\varPi }}) $
     (1) $ (({K_{\varPi }},{\text{s}}{{\text{t}}_{\varPi }}{\text{);ED}}{{\text{B}}_{\varPi }}) \leftarrow {\varPi }.{\text{Setup}}(\lambda ; \bot ) \text{;} $
     (2) $ {\text{Buffer}} \leftarrow \varnothing $(关键词到更新列表的映射),$e \leftarrow 0$;
     (3) $ {\text{Packs}} \leftarrow \langle \rangle $(空列表);
     (4) 客户端存储密钥$ K = {K_{\varPi }} $、状态$ {\text{st}} = (e,{\text{Buffer}},{\text{s}}{{\text{t}}_{\varPi }}) $,服
     务器存储加密数据库$ {\text{EDB = (Packs,ED}}{{\text{B}}_{\varPi }}) $。
    下载: 导出CSV

    2  更新$ {\text{Tran}}{{\text{s}}_{L,|W|}}[{\varPi }].{\text{Update}}({K_{\varPi }},(e,{\text{Buffer}},{\text{s}}{{\text{t}}_{\varPi }}) $,${\text{id}},w,{\text{op}} $;$({\text{Packs}},{\text{ED}}{{\text{B}}_{\varPi }})) $

     输入:客户端输入更新的关键词$ w $、文档标识符$ {\text{id}} $、操作符$ {\text{op}} $、密钥$ K = {K_{\varPi }} $、状态$ {\text{st}} = (e,{\text{Buffer}},{\text{s}}{{\text{t}}_{\varPi }}) $;服务器输入加密数据库
     $ {\text{EDB = (Packs,ED}}{{\text{B}}_{\varPi }}) $
     输出:客户端和服务器分别输出可能更新的上述状态和加密数据库客户端执行:
     (1) $ {\text{Buffer}}[w] \leftarrow {\text{Buffer}}[w]||\langle ({\text{id}},{\text{op}})\rangle \text{;} $
     (2) if $\sum\nolimits_{w \in W} {|{\text{Buffer}}[w]|} \lt {2^{L - 1}}$,结束;
     (3) $e \leftarrow e + 1 , P \leftarrow {\text{InitPack}}(L) \text{;} $
     (4) foreach $ w \in \{ w'\mid {\text{Buffer}}[w'] \ne \langle \rangle \} $,设$ {\text{Buffer}}[w] = {\langle ({\text{i}}{{\text{d}}_i},{\text{o}}{{\text{p}}_i})\rangle _i} $:
       (a) ${t_{e,w}}{\mathop {\leftarrow} \limits^{{S\mkern-10.5mu/}} } {\{ 0,1\} ^\lambda } $;
       (b) $ (l,r){\mathop {\leftarrow} \limits^{{S\mkern-10.5mu/}} } {\text{SuitableIntervals}}(|{\text{Buffer}}[w]|) \cap {\text{UnusedIntervals}}(P) $,其中$ {\text{UnusedIntervals}}(P) $表示$ P $中在本次算法执行中未被本行选取过   的区间;
       (c) 设$ (l,r) $在$ {{P}} $中对应的子数组为$ {\text{Arr}} $;
       (d) for $ j \leftarrow 1 $to$ {2^{l - 1}} $:
        (i) if $ j \le |{\text{Buffer}}[w]| $, $ {\text{Arr}}[j] \leftarrow H({t_{e,w}}||j) \oplus ({\text{i}}{{\text{d}}_j}||{\text{o}}{{\text{p}}_j}) $;else $ {\text{Arr}}[j] \leftarrow H({t_{e,w}}||j) \oplus \bot $。
       (e) $({\text{s}}{{\text{t}}_{\varPi }};{\text{ED}}{{\text{B}}_{\varPi }}) \leftarrow {\varPi }.{\text{Update}}({K_{\varPi }},{\text{s}}{{\text{t}}_{\varPi }},e||l||r||{t_{e,w}},w',{\text{add';ED}}{{\text{B}}_{\varPi }}) 。 $
     (5) $ {\text{Buffer}} \leftarrow \varnothing \text{;} $
     (6) 设$ m $为步骤(4)中处理的关键词数;
     (7) for $ i \leftarrow 1 $ to $ |W| - m $:
       (a) $ ({\text{s}}{{\text{t}}_{\varPi }};{\text{ED}}{{\text{B}}_{\varPi }}) \leftarrow {\varPi }.{\text{Update}}({K_{\varPi }},{\text{s}}{{\text{t}}_{\varPi }}, \bot ,'{\text{dummy}}','{\text{add}}';{\text{ED}}{{\text{B}}_{\varPi }}) $。其中$ {{'{\mathrm{dummy}}'}} $表示一个弃用关键词。
     (8) 生成随机比特串填充$ P $中$ {\text{UnusedIntervals}}(P) $对应的部分;
     (9) 将$ P $发送给服务器。服务器执行:
     (10) $ {\text{Packs}} \leftarrow {\text{Packs}}||\langle P\rangle $。
    下载: 导出CSV

    3  搜索$ {\text{Tran}}{{\text{s}}_{L,|W|}}[{\varPi }].{\text{Search}}({K_{\varPi }},(e,{\text{Buffer}},{\text{s}}{{\text{t}}_{\varPi }}),w;({\text{Packs}},{\text{ED}}{{\text{B}}_{\varPi }})) $

     输入:客户端输入搜索的关键词$ w $,密钥$ K = {K_{\varPi }} $、状态$ {\text{st}} = (e,{\text{Buffer}},{\text{s}}{{\text{t}}_{\varPi }}) $;服务器输入加密数据库$ {\text{EDB = (Packs,ED}}{{\text{B}}_{\varPi }}) $
     输出:客户端输出搜索结果即对应关键词$ w $的文档标识符集合$ {\text{DB}}(w) $、可能更新的上述状态;服务器输出可能更新的上述加密数据库客户
     端执行:
     (1) $(({\text{s}}{{\text{t}}_{\varPi }},{\text{ID}}');{\text{ED}}{{\text{B}}_{\varPi }}) \leftarrow {\varPi }.{\text{Search}}({K_{\varPi }},{\text{s}}{{\text{t}}_{\varPi }},w;{\text{ED}}{{\text{B}}_{\varPi }}) $
     (2) 将$ {\text{ID}}' $发送给服务器。服务器执行:
     (3) 设$ {\text{ID}}' ={\{ ({e_i}'||{l_i}'||{r_i}'||t{'_{{e_i},w}})\} _{i = 1,2,\cdots,b}} $,将其按$ {e_i}' $正序排列,得到$ {\langle ({e_i},{l_i},{r_i},{t_{{e_i},w}})\rangle _{i = 1,2,\cdots,b}} $;
     (4) ${\text{ID}} \leftarrow \varnothing \text{;}$
     (5) for $i \leftarrow 1$ to $|b|$,设$ ({l_i},{r_i}) $在$ {\text{Packs}}[{e_i}] $中对应的子数组为$ {\text{Ar}}{{\text{r}}_i} $:
       (a) for $j \leftarrow 1$ to $|{\text{Ar}}{{\text{r}}_i}|$:
        (i) if $ {\text{Ar}}{{\text{r}}_i}[j] \oplus H({t_{{e_i},w}}||j) = \bot $,break;
        (ii) 设$ {\text{id||op}} = {\text{Ar}}{{\text{r}}_i}[j] \oplus H({t_{{e_i},w}}||j) $;
        (iii) if $ {{{\mathrm{op }}= ' {\mathrm{add}}'}} $, $ {\text{ID}} \leftarrow {\text{ID}} \cup \{ {\text{id}}\} $;else $ {\text{ID}} \leftarrow {\text{ID}} \setminus \{ {\text{id}}\} $。
     (6) 将$ {\text{ID}} $返回给客户端。客户端执行:
     (7) for $i = 1$ to $|{\text{Buffer}}[w]|$,设$ {\text{(id,op)}} = {\text{Buffer}}[w][i] $;
       (a) if $ {\text{op =}} ' {\mathrm{add}}' $, $ {\text{ID}} \leftarrow {\text{ID}} \cup \{ {\text{id}}\} $;else $ {\text{ID}} \leftarrow {\text{ID}} \setminus \{ {\text{id}}\} $
     (8) 输出$ {\text{ID}} $为最终搜索结果。
    下载: 导出CSV

    表  1  复杂度对比

    方案 搜索复杂度 局部性 读效率 更新复杂度 客户端存储
    ${\text{FAST}}$[4] $O(|{\text{DB}}(w)|)$ $O(|{\text{DB}}(w)|)$ $O(1)$ $O(1)$ $O(|W|)$
    $ {\text{Tran}}{{\text{s}}_{L,|W|}}{\text{[FAST]}} $ $O(|{\text{DB}}(w)|)$ $O(\min (|{\text{DB}}(w)|,N/|W|))$ $O(1)$ $O(\log_2 |W|)$ $O(|W|)$
    ${\text{S}}{{\text{D}}_a}[1C]$/${\text{L-S}}{{\text{D}}_d}[1C]$[14] $O(|{\text{DB}}(w)|{\log _2}N)$ $O({\log _2}N)$ $O({\log _2}N)$ $ O({\log _2}N) $/$ O(\log _2^2N) $ $O({\log _2}N)$
    ${\text{S}}{{\text{D}}_a}[N{\text{log}}N]$/${\text{L-S}}{{\text{D}}_d}[N{\text{log}} N]$[14] $O(|{\text{DB}}(w)| + {\log _2}N)$ $O({\log _2}N)$ $O({\log _2}N)$ $ O(\log _2^2N) $/$O(\log _2^3N)$ $O({\log _2}N)$
    下载: 导出CSV

    表  2  客户端存储对比

    方案 客户端存储大小
    ${\text{FAST}}$[4] 390.6 kB
    ${\text{Tran}}{{\text{s}}_{L,|W|}}{\text{[FAST]}},L = 14$ 618.9 kB
    ${\text{Tran}}{{\text{s}}_{L,|W|}}{\text{[FAST]}},L = 15$ 690.9 kB
    ${\text{Tran}}{{\text{s}}_{L,|W|}}{\text{[FAST]}},L = 16$ 834.9 kB
    $ {\text{S}}{{\text{D}}_a}[1C] $[14] 128 B
    ${\text{S}}{{\text{D}}_a}[N\log N]$[14] 128 B
    下载: 导出CSV
  • [1] 肖人毅. 云计算中数据隐私保护研究进展[J]. 通信学报, 2014, 35(12): 168–177. doi: 10.3969/j.issn.1000-436x.2014.12.020.

    XIAO Renyi. Survey of privacy preserving data queries in cloud computing[J]. Journal on Communications, 2014, 35(12): 168–177. doi: 10.3969/j.issn.1000-436x.2014.12.020.
    [2] LI Feng, MA Jianfeng, MIAO Yinbin, et al. A survey on searchable symmetric encryption[J]. ACM Computing Surveys, 2024, 56(5): 119. doi: 10.1145/3617991.
    [3] DENNING P J. The locality principle[J]. Communications of the ACM, 2005, 48(7): 19–24. doi: 10.1145/1070838.1070856.
    [4] SONG Xiangfu, DONG Changyu, YUAN Dandan, et al. Forward private searchable symmetric encryption with optimized I/O efficiency[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 17(5): 912–927. doi: 10.1109/TDSC.2018.2822294.
    [5] BOST R, MINAUD B, and OHRIMENKO O. Forward and backward private searchable encryption from constrained cryptographic primitives[C]. The 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, USA, 2017: 1465–1482. doi: 10.1145/3133956.3133980.
    [6] CASH D and TESSARO S. The locality of searchable symmetric encryption[C]. The 33rd International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, Copenhagen, Denmark, 2014: 351–368. doi: 10.1007/978-3-642-55220-5_20.
    [7] ASHAROV G, NAOR M, SEGEV G, et al. Searchable symmetric encryption: Optimal locality in linear space via two-dimensional balanced allocations[C]. The 48th ACM Symposium on Theory of Computing, Cambridge, USA, 2016: 1101–1114. doi: 10.1145/2897518.2897562.
    [8] DEMERTZIS I and PAPAMANTHOU C. Fast searchable encryption with tunable locality[C]. Proceedings of 2017 ACM International Conference on Management of Data, Chicago, USA, 2017: 1053–1067. doi: 10.1145/3035918.3064057.
    [9] ASHAROV G, SEGEV G, and SHAHAF I. Tight tradeoffs in searchable symmetric encryption[C]. Proceedings of the 38th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2018: 407–436. doi: 10.1007/978-3-319-96884-1_14.
    [10] BOST R. ∑oφoς: Forward secure searchable encryption[C]. 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 2016: 1143–1154. doi: 10.1145/2976749.2978303.
    [11] STEFANOV E, PAPAMANTHOU C, and SHI E. Practical dynamic searchable encryption with small leakage[C]. The 21st Annual Network and Distributed System Security Symposium, San Diego, USA, 2014. doi: 10.14722/ndss.2014.23298.
    [12] ZHANG Yupeng, KATZ J, and PAPAMANTHOU C. All your queries are belong to us: The power of File-Injection attacks on searchable encryption[C]. The 25th USENIX Conference on Security Symposium, Austin, USA, 2016: 707–720.
    [13] POWERS D M W. Applications and explanations of Zipf’s law[C]. The Joint Conferences on New Methods in Language Processing and Computational Natural Language Learning, Sydney, Australia, 1998: 151–160.
    [14] MONDAL P, CHAMANI J G, DEMERTZIS I, et al. I/O-efficient dynamic searchable encryption meets forward & backward privacy[C]. The 33rd USENIX Security Symposium, Philadelphia, USA, 2024: 2527–2544.
    [15] SONG D X, WAGNER D, and PERRIG A. Practical techniques for searches on encrypted data[C]. 2000 IEEE Symposium on Security and Privacy, Berkeley, USA, 2000: 44–55. doi: 10.1109/SECPRI.2000.848445.
    [16] CURTMOLA R, GARAY J, KAMARA S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[C]. The 13th ACM Conference on Computer and Communications Security, Alexandria, USA, 2006: 79–88. doi: 10.1145/1180405.1180417.
    [17] LI Feng, MA Jianfeng, MIAO Yinbin, et al. Beyond volume pattern: Storage-efficient Boolean searchable symmetric encryption with suppressed leakage[C]. The 28th European Symposium on Research in Computer Security Computer Security, Hague, Netherlands, 2024: 126–146. doi: 10.1007/978-3-031-50594-2_7.
    [18] HALTIWANGER J and HOANG T. Exploiting update leakage in searchable symmetric encryption[C]. The 17th ACM Conference on Data and Application Security and Privacy, Porto, Portugal, 2024: 115–126. doi: 10.1145/3626232.3653260.
    [19] ZHAO Chenbin, DU Ruiying, HE Kun, et al. Efficient verifiable dynamic searchable symmetric encryption with forward and backward security[J]. IEEE Internet of Things Journal, 2025, 12(3): 2633–2645. doi: 10.1109/JIOT.2024.3470772.
    [20] LI Dexin, ZHAO Xingwen, LI Hui, et al. Volume-hiding multidimensional verifiable dynamic searchable symmetric encryption scheme for cloud computing[J]. IEEE Internet of Things Journal, 2024, 11(23): 37437–37451. doi: 10.1109/JIOT.2024.3408812.
    [21] ZUO Cong, LAI Shangqi, SUN Shifeng, et al. Searchable encryption for conjunctive queries with extended forward and backward privacy[J]. Proceedings on Privacy Enhancing Technologies, 2025, 2025(1): 440–455. doi: 10.56553/popets-2025-0024.
    [22] MIERS I and MOHASSEL P. IO-DSSE: Scaling dynamic searchable encryption to millions of indexes by improving locality[C]. The 24th Annual Network and Distributed System Security Symposium, San Diego, USA, 2017. doi: 10.14722/ndss.2017.23394.
    [23] MINAUD B and REICHLE M. Dynamic local searchable symmetric encryption[C]. The 42nd Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2022: 91–120. doi: 10.1007/978-3-031-15985-5_4.
    [24] XU Peng, SUSILO W, WANG Wei, et al. ROSE: Robust searchable encryption with forward and backward security[J]. IEEE Transactions on Information Forensics and Security, 2022, 17: 1115–1130. doi: 10.1109/TIFS.2022.3155977.
    [25] DOU Haochen, DAN Zhenwu, XU Peng, et al. Dynamic searchable symmetric encryption with strong security and robustness[J]. IEEE Transactions on Information Forensics and Security, 2024, 19: 2370–2384. doi: 10.1109/TIFS.2024.3350330.
  • 加载中
图(5) / 表(5)
计量
  • 文章访问数:  161
  • HTML全文浏览量:  94
  • PDF下载量:  16
  • 被引次数: 0
出版历程
  • 收稿日期:  2025-02-24
  • 修回日期:  2025-05-08
  • 网络出版日期:  2025-05-28
  • 刊出日期:  2025-08-27

目录

    /

    返回文章
    返回