鲁棒的前后向隐私联合对称可搜索加密方案
作者:
中图分类号:

TP309

基金项目:

国家自然科学基金 (62332018, 62072078, 62271128); 四川省自然科学基金 (2022NSFSC0550)


Robust Scheme for Conjunctive Symmetric Searchable Encryption with Forward and Backward Privacy
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [54]
  • | | | |
  • 文章评论
    摘要:

    动态对称可搜索加密允许用户安全地搜索和动态更新存储在半可信云服务器中的加密文档, 近年来备受关注. 然而, 现有多数对称可搜索加密方案仅支持单关键词搜索, 无法在实现联合搜索的同时满足前向和后向隐私. 此外, 多数方案不具有鲁棒性, 即无法处理客户端重复添加或删除某个关键词/文件标识符对或删除不存在的关键词/文件标识符对等不合理更新请求. 针对上述挑战, 提出一个鲁棒的前后向隐私联合动态对称可搜索加密方案RFBC. 在该方案中, 服务器为每个关键词建立两个布隆过滤器, 分别用于存储所要添加和删除的关键词/文件标识符对的相关哈希值. 当客户端发送更新请求时, 服务器利用两个布隆过滤器进行判断, 过滤不合理请求, 以满足方案的鲁棒性. 此外, 利用多关键词中最低频关键词的状态信息, 结合布隆过滤器与更新计数器, 筛选掉不包含其余关键词的文件标识实现联合查询. 通过定义方案的泄露函数, 经过一系列的安全性游戏证明RFBC支持前向隐私与Type-III后向隐私. 实验分析表明相较于相关方案, RFBC较大幅度提高了计算和通信效率. 具体来说, RFBC更新操作的计算开销分别为ODXT和BDXT的28%和61.7%, 搜索操作的计算开销分别为ODXT和BDXT的21.9%和27.3%, 而搜索操作的通信开销分别为ODXT和BDXT的19.7%和31.6%. 而且, 当不合理更新的比例逐渐增加时, 搜索效率的提升明显高于BDXT与ODXT.

    Abstract:

    Dynamic searchable symmetric encryption has attracted much attention because it allows users to securely search and dynamically update encrypted documents stored in a semi-trusted cloud server. However, most searchable symmetric encryption schemes only support single-keyword search, failing to achieve conjunctive search while protecting forward and backward privacy. In addition, most schemes are not robust, which means that they cannot handle irrational update requests from a client, such as adding or deleting a certain keyword/file identifier pair, or deleting non-existent keywords/file identifier pairs. To address these challenges, this study proposes a robust scheme for conjunctive dynamic symmetric searchable encryption that preserves both forward and backward privacy, called RFBC. In this scheme, the server constructs two Bloom filters for each keyword, which are used to store the relevant hash values of the keyword/file identifier pair to be added and deleted, respectively. When the client sends update requests, the server uses the two Bloom filters to determine and filter irrational update requests, so as to guarantee the robustness of the scheme. In addition, by combining the status information of the lowest frequency keywords among multiple keywords, the Bloom filters, and the update counter, RFBC realizes conjunctive search by filtering out file identifiers that do not contain the rest keywords. Finally, by defining the leakage function, RFBC is proved to be forward private and Type-III backward private through a series of security analyses. Experimental results show that compared with related schemes, RFBC greatly improves computation and communication efficiency. Specifically, the computational overhead of update operations in RFBC is about 28% and 61.7% of that in ODXT and BDXT, respectively. The computational overhead of search operations in RFBC is about 21.9% and 27.3% of that in ODXT and BDXT, respectively. The communication overhead of search operations in RFBC is about 19.7% and 31.6% of that in ODXT and BDXT, respectively. Moreover, as the proportion of irrational updates gradually increases, RFBC exhibits significantly higher improvement in search efficiency compared to both BDXT and ODXT.

    参考文献
    [1] Song DX, Wagner D, Perrig A. Practical techniques for searches on encrypted data. In: Proc. of the 2000 IEEE Symp. on Security and Privacy. Berkeley: IEEE, 2000. 44–55. [doi: 10.1109/SECPRI.2000.848445]
    [2] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption. In: Proc. of the 2012 ACM Conf. on Computer and Communications Security. Raleigh: ACM, 2012. 965–976. [doi: 10.1145/2382196.2382298]
    [3] Zhang YP, Katz J, Papamanthou C. All your queries are belong to us: The power of file-injection attacks on searchable encryption. In: Proc. of the 25th USENIX Conf. on Security Symp. Austin: USENIX Association, 2016. 707–720.
    [4] Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage. In: Proc. of the 21st Annual Network and Distributed System Security Symp. San Diego: NDSS, 2014. 23–26.
    [5] 黄一才, 李森森, 郁滨. 云环境下对称可搜索加密研究综述. 电子与信息学报, 2023, 45(3): 1134–1146.
    Huang YC, Li SS, Yu B. A survey of symmetric searchable encryption in cloud environment. Journal of Electronics & Information Technology, 2023, 45(3): 1134–1146 (in Chinese with English abstract).
    [6] 王贇玲, 陈晓峰. 对称可搜索加密技术研究进展. 电子与信息学报, 2020, 42(10): 2374–2385.
    Wang YL, Chen XF. Research on searchable symmetric encryption. Journal of Electronics & Information Technology, 2020, 42(10): 2374–2385 (in Chinese with English abstract).
    [7] 刘文心, 高莹. 对称可搜索加密的安全性研究进展. 信息安全学报, 2021, 6(2): 73–84.
    Liu WX, Gao Y. A survey on security development of searchable symmetric encryption. Journal of Cyber Security, 2021, 6(2): 73–84 (in Chinese with English abstract).
    [8] Asharov G, Segev G, Shahaf I. Tight tradeoffs in searchable symmetric encryption. Journal of Cryptology, 2021, 34(2): 9.
    [9] Goh EJ. Secure indexes. 2003. https://crypto.stanford.edu/~eujin/papers/secureindex/secureindex.pdf
    [10] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions. In: Proc. of the 13th ACM Conf. on Computer and Communications Security. Alexandria: ACM, 2006. 79–88.
    [11] Cash D, Jarecki S, Jutla C, Krawczyk H, Ro?u MC, Steiner M. Highly-scalable searchable symmetric encryption with support for Boolean queries. In: Proc. of the 33rd Annual Cryptology Conf. Santa Barbara: Springer, 2013. 353–373. [doi: 10.1007/978-3-642-40041-4_20]
    [12] Lai SQ, Patranabis S, Sakzad A, Liu JK, Mukhopadhyay D, Steinfeld R, Sun SF, Liu DX, Zuo C. Result pattern hiding searchable encryption for conjunctive queries. In: Proc. of the 2018 ACM SIGSAC Conf. on Computer and Communications Security. Toronto: ACM, 2018. 745–762. [doi: 10.1145/3243734.3243753]
    [13] Kamara S, Papamanthou C. Parallel and dynamic searchable symmetric encryption. In: Proc. of the 17th Int’l Conf. on Financial Cryptography and Data Security. Okinawa: Springer, 2013. 258–274. [doi: 10.1007/978-3-642-39884-1_22]
    [14] Bost R. ∑oφo?: Forward secure searchable encryption. In: Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security. Vienna: ACM, 2016. 1143–1154. [doi: 10.1145/2976749.2978303]
    [15] Kim KS, Kim M, Lee D, Park JH, Kim WH. Forward secure dynamic searchable symmetric encryption with efficient updates. In: Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security. Dallas: ACM, 2017. 1449–1463.
    [16] Etemad M, Küp?ü A, Papamanthou C, Evans D. Efficient dynamic searchable encryption with forward privacy. Proc. on Privacy Enhancing Technologies, 2018, 2018(1): 5–20.
    [17] Song XF, Dong CY, Yuan DD, Xu QL, Zhao MH. Forward private searchable symmetric encryption with optimized I/O efficiency. IEEE Trans. on Dependable and Secure Computing, 2020, 17(5): 912–927.
    [18] Zhang ZJ, Wang JF, Wang YL, Su YP, Chen XF. Towards efficient verifiable forward secure searchable symmetric encryption. In: Proc. of the 24th European Symp. on Research in Computer Security. Luxembourg: Springer, 2019. 304–321. [doi: 10.1007/978-3-030-29962-0_15]
    [19] Yang JJ, Liu F, Luo XY, Hong JN, Li J, Xue KP. Forward private multi-client searchable encryption with efficient access control in cloud storage. In: Proc. of the 2022 IEEE Global Communications Conf. Rio de Janeiro: IEEE, 2022. 3791–3796.
    [20] Patranabis S, Mukhopadhyay D. Forward and backward private conjunctive searchable symmetric encryption. 2021. https://www.ndss-symposium.org/wp-content/uploads/ndss2021_2C-3_23116_paper.pdf
    [21] Yuan DD, Cui SJ, Russello G. We can make mistakes: Fault-tolerant forward private verifiable dynamic searchable symmetric encryption. In: Proc. of the 7th IEEE European Symp. on Security and Privacy (EuroS&P). Genoa: IEEE, 2022. 587–605.
    [22] Mei L, Xu CG, Xu L, Yuan XL, Liu JK. Practical multi-source multi-client searchable encryption with forward privacy: Refined security notion and new constructions. IEEE Trans. on Dependable and Secure Computing, 2024, 21(1): 63–77.
    [23] Kamara S, Moataz T. Boolean searchable symmetric encryption with worst-case sub-linear complexity. In: Proc. of the 36th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Paris: Springer, 2017. 94–124. [doi: 10.1007/978-3-319-56617-7_4]
    [24] Wang YL, Wang JF, Sun SF, Miao MX, Chen XF. Toward forward secure SSE supporting conjunctive keyword search. IEEE Access, 2019, 7: 142762–142772.
    [25] Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives. In: Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security. Dallas: ACM, 2017. 1465–1482.
    [26] Sun SF, Yuan XL, Liu JK, Steinfeld R, Sakzad A, Vo V, Nepal S. Practical backward-secure searchable encryption from symmetric puncturable encryption. In: Proc. of the 2018 ACM SIGSAC Conf. on Computer and Communications Security. Toronto: ACM, 2018. 763–780. [doi: 10.1145/3243734.3243782]
    [27] Chamani JG, Papadopoulos D, Papamanthou C, Jalili R. New constructions for forward and backward private symmetric searchable encryption. In: Proc. of the 2018 ACM SIGSAC Conf. on Computer and Communications Security. Toronto: ACM, 2018. 1038–1055. [doi: 10.1145/3243734.3243833]
    [28] Hoang T, Yavuz AA, Guajardo J. A secure searchable encryption framework for privacy-critical cloud storage services. IEEE Trans. on Services Computing, 2021, 14(6): 1675–1689.
    [29] He K, Chen J, Zhou QX, Du RY, Xiang Y. Secure dynamic searchable symmetric encryption with constant client storage cost. IEEE Trans. on Information Forensics and Security, 2021, 16: 1538–1549.
    [30] Demertzis I, Chamani JG, Papadopoulos D, Papamanthou C. Dynamic searchable encryption with small client storage. In: Proc. of the 27th Annual Network and Distributed System Security Symp. San Diego: NDSS, 2020.
    [31] Sun SF, Steinfeld R, Lai SQ, Yuan XL, Sakzad A, Liu JK, Nepal S, Gu DW. Practical non-interactive searchable encryption with forward and backward privacy. In: Proc. of the 28th Annual Network and Distributed System Security Symp. NDSS. 2021.
    [32] Vo V, Lai SQ, Yuan XL, Nepal S, Liu JK. Towards efficient and strong backward private searchable encryption with secure enclaves. In: Proc. of the 19th Int’l Conf. on Applied Cryptography and Network Security. Kamakura: Springer, 2021. 50–75. [doi: 10.1007/978-3-030-78372-3_3]
    [33] Vo V, Lai SQ, Yuan XL, Sun SF, Nepal S, Liu JK. Accelerating forward and backward private searchable encryption using trusted execution. In: Proc. of the 18th Int’l Conf. on Applied Cryptography and Network Security. Rome: Springer, 2020. 83–103.
    [34] Amjad G, Kamara S, Moataz T. Forward and backward private searchable encryption with SGX. In: Proc. of the 12th European Workshop on Systems Security. Dresden: ACM, 2019. 4. [doi: 10.1145/3301417.3312496]
    [35] Huang YY, Lv SY, Liu ZL, Song XF, Li J, Yuan YL, Dong CY. Cetus: An efficient symmetric searchable encryption against file-injection attack with SGX. Science China Information Sciences, 2021, 64(8): 182314.
    [36] Zuo C, Sun SF, Liu JK, Shao J, Pieprzyk J. Dynamic searchable symmetric encryption with forward and stronger backward privacy. In: Proc. of the 24th European Symp. on Research in Computer Security. Luxembourg: Springer, 2019. 283–303. [doi: 10.1007/978-3-030-29962-0_14]
    [37] Wu ZQ, Cai ZB, Tang XY, Xu YM, Deng T. A forward and backward private oblivious RAM for storage outsourcing on edge-cloud computing. Journal of Parallel and Distributed Computing, 2022, 166: 1–14.
    [38] Stefanov E, Van Dijk M, Shi E, Chan THH, Fletcher C, Ren L, Yu XY, Devadas S. Path ORAM: An extremely simple oblivious RAM protocol. Journal of the ACM (JACM), 2018, 65(4): 18.
    [39] Li J, Huang YY, Wei Y, Lv SY, Liu ZL, Dong CY, Luo WJ. Searchable symmetric encryption with forward search privacy. IEEE Trans. on Dependable and Secure Computing, 2021, 18(1): 460–474.
    [40] Xu P, Susilo W, Wang W, Chen TY, Wu QH, Liang KT, Jin H. ROSE: Robust searchable encryption with forward and backward security. IEEE Trans. on Information Forensics and Security, 2022, 17: 1115–1130.
    [41] Zuo C, Lai SQ, Yuan XL, Liu JK, Shao J, Wang HX. Searchable encryption for conjunctive queries with extended forward and backward privacy. IACR Cryptology ePrint Archive, 2021, 2021: 1585.
    [42] Chen TY, Xu P, Wang W, Zheng YB, Susilo W, Jin H. Bestie: Very practical searchable encryption with forward and backward security. In: Proc. of the 26th European Symp. on Research in Computer Security. Darmstadt: Springer, 2021. 3–23. [doi: 10.1007/978-3-030-88428-4_1]
    [43] Zuo C, Sun SF, Liu JK, Shao J, Pieprzyk J, Xu L. Forward and backward private DSSE for range queries. IEEE Trans. on Dependable and Secure Computing, 2022, 19(1): 328–338.
    [44] Wang XY, Ma JF, Liu XM, Miao YB, Liu Y, Deng RH. Forward/backward and content private DSSE for spatial keyword queries. IEEE Trans. on Dependable and Secure Computing, 2023, 20(4): 3358–3370.
    [45] Xu L, Duan HY, Zhou AX, Yuan XL, Wang C. Interpreting and mitigating leakage-abuse attacks in searchable symmetric encryption. IEEE Trans. on Information Forensics and Security, 2021, 16: 5310–5325.
    [46] Chamani JG, Papadopoulos D, Karbasforushan M, Demertzis I. Dynamic searchable encryption with optimal search in the presence of deletions. In: Proc. of the 31st USENIX Security Symp. USENIX Association, 2022. 2425–2442.
    [47] Jiang Q, Chang EC, Qi Y, Qi SY, Wu PF, Wang JF. Rphx: Result pattern hiding conjunctive query over private compressed index using Intel SGX. IEEE Trans. on Information Forensics and Security, 2022, 17: 1053–1068.
    [48] Xu C, Wang RJ, Zhu LH, Zhang C, Lu RX, Sharif K. Efficient strong privacy-preserving conjunctive keyword search over encrypted cloud data. IEEE Trans. on Big Data, 2023, 9(3): 805–817.
    [49] Bloom BH. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13(7): 422–426.
    [50] 冯登国. 可证明安全性理论与方法研究. 软件学报, 2005, 16(10): 1743–1756. http://www.jos.org.cn/1000-9825/16/1743.htm
    Feng DG. Research on theory and approach of provable security. Ruan Jian Xue Bao/Journal of Software, 2005, 16(10): 1743–1756 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/16/1743.htm
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

张文琪,李雄,尹智明,梁伟,黄可,张小松.鲁棒的前后向隐私联合对称可搜索加密方案.软件学报,2025,36(8):3858-3882

复制
分享
文章指标
  • 点击次数:155
  • 下载次数: 732
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2023-08-28
  • 最后修改日期:2024-02-20
  • 在线发布日期: 2024-12-04
文章二维码
您是第20234752位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号