支持亿级数据的高效密文范围查询完整性验证

doi:10.16451/j.cnki.issn1003-6059.202401003

摘要
图/表
参考文献
相关文章 (0)

全文: PDF (1556 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要密文查询的完整性验证机制能在保护人工智能应用数据隐私的同时,为查询结果的可靠性提供保证.然而,现有针对密文范围查询的完整性验证方法存在验证数据结构构建开销较高、数据可扩展性较差的缺陷.为此,文中分析ServeDB(Secure Verifiable and Efficient Framework)计算性能瓶颈产生的原因,并基于分析结论提出基于立方格索引的密文范围查询完整性验证方法(Cube-Cell-Based Authentication Tree, CubeTree).CubeTree采用基于分位数归一化的数据重分布优化方法,平衡数据记录在值域空间中的分布,降低数据记录的编码开销.进一步提出基于平衡K叉树的扁平化结构以及基于立方格索引的验证数据结构,合并具有相同编码的数据记录,采用立方格作为基本验证单元,大幅降低验证数据结构的冗余性,减少构造过程的计算与存储开销.在真实数据集与合成数据集上的实验表明,CubeTree能显著降低验证数据结构的构建开销以及查询完整性证明的生成与校验开销,并可高效处理亿级规模的大型数据集.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	王肇康
	潘佳辉
	周璐

关键词 ：应用安全, 密文范围查询, 查询完整性验证, 验证数据结构, 立方格索引

Abstract：The encrypted query integrity authentication mechanism can provide assurance for the reliability of the query results while protecting the data privacy of artificial intelligence applications. However, the existing encrypted range query integrity authentication methods suffer from high overhead in authentication data structure construction and poor data scalability. To address these issues, the causes of performance bottlenecks in secure verifiable and efficient framework(ServeDB)are analyzed. Based on the analysis conclusions, a cube-cell-based authentication method(CubeTree) is proposed for the encrypted range query integrity authentication problem. A quantile-normalization-based data redistribution optimization is adopted to balance the data distribution in the domain. The encoding overheads of data records are reduced by the data redistribution optimization. Furthermore, a flat balanced K-ary tree structure and a cube-cell-based index authentication data structure are proposed. The redundancy of the authentication data structure is significantly reduced by merging data records with same codes and adopting cube cells as the basic units. Consequently, the computational and storage costs of the CubeTree construction are decreased. Experiments on real-world and synthetic datasets show that CubeTree can significantly reduce the construction costs of the authentication data structure and the generation/verification costs of query integrity proofs, while efficiently handling large-scale datasets with hundreds of millions of data records.

Key words： Application Security Encrypted Range Query Query Integrity Authentication Authentica-tion Data Structure Cube Cell Index

收稿日期: 2023-09-07

ZTFLH:

TP315

基金资助:国家重点研发计划项目(No.2021YFB3101100)、国家自然科学基金项目(No.62202225)资助

通讯作者: 王肇康,博士,讲师,主要研究方向为大数据并行处理、图计算.E-mail: wangzhaokang@nuaa.edu.cn.

作者简介: 潘佳辉,硕士研究生,主要研究方向为查询完整性验证.E-mail: floating@nuaa.edu.cn. 周璐,博士,教授,主要研究方向为密码学、物联网安全.E-mail:lu.zhou@nuaa.edu.cn.

引用本文:

王肇康, 潘佳辉, 周璐. 支持亿级数据的高效密文范围查询完整性验证[J]. 模式识别与人工智能, 2024, 37(1): 27-46. WANG Zhaokang, PAN Jiahui, ZHOU Lu. Efficient Encrypted Range Query Integrity Authentication for Hundreds of Millions of Records. Pattern Recognition and Artificial Intelligence, 2024, 37(1): 27-46.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.202401003 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2024/V37/I1/27

[1] WANG J F, CHEN X F, HUANG X Y, et al. Verifiable Auditing for Outsourced Database in Cloud Computing. IEEE Transactions on Computers, 2015, 64(11): 3293-3303.
[2] ZHANG B, DONG B X, WANG W H.Integrity Authentication for SQL Query Evaluation on Outsourced Databases: A Survey. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(4): 1601-1618.
[3] XIE M, WANG H X, YIN J, et al. Integrity Auditing of Outsourced Data // Proc of the 33rd International Conference on Very Large Data Bases. New York, USA: ACM, 2007: 782-793.
[4] DEVANBU P, GERTZ M, MARTEL C, et al. Authentic Data Publication over the Internet. Journal of Computer Security, 2003, 11(3): 291-314.
[5] PANG H H, TAN K L.Authenticating Query Results in Edge Computing // Proc of the 20th International Conference on Data Engineering. Washington, USA: IEEE, 2004. DOI: 10.1109/ICDE.2004.1320027.
[6] YANG Y, PAPADIAS D, PAPADOPOULOS S, et al. Authenticated Join Processing in Outsourced Databases // Proc of the ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2009: 5-18.
[7] NUCKOLLS G.Verified Query Results from Hybrid Authentication Trees // Proc of the IFIP Annual Conference on Data and Applications Security and Privacy. Berlin, Germany: Springer, 2005: 84-98.
[8] CHENG W W, PANG H, TAN K L.Authenticating Multi-dimensional Query Results in Data Publishing // Proc of the IFIP Annual Conference on Data and Applications Security and Privacy. Berlin, Germany: Springer, 2006: 60-73.
[9] NARASIMHA M, TSUDIK G.Authentication of Outsourced Databases Using Signature Aggregation and Chaining // Proc of the 11th International Conference on Database Systems for Advanced Applications. Berlin, Germany: Springer, 2006: 420-436.
[10] PANG H, ZHANG J L, MOURATIDIS K.Scalable Verification for Outsourced Dynamic Databases. Proceedings of the VLDB Endowment, 2009, 2(1): 802-813.
[11] PAPADOPOULOS D, PAPADOPOULOS S, TRIANDOPOULOS N.Taking Authenticated Range Queries to Arbitrary Dimensions // Proc of the ACM SIGSAC Conference on Computer and Communications Security. New York, USA: ACM, 2014: 819-830.
[12] ZHANG Y P, KATZ J, PAPAMANTHOU C.IntegriDB: Verifi-able SQL for Outsourced Databases // Proc of the 22nd ACM SIGSAC Conference on Computer and Communications Security. New York, USA: ACM, 2015: 1480-1491.
[13] REN K, GUO Y, LI J Q, et al. HybrIDX: New Hybrid Index for Volume-Hiding Range Queries in Data Outsourcing Services // Proc of the IEEE 40th International Conference on Distributed Computing Systems. Washington, USA: IEEE, 2020: 23-33.
[14] ZHAN Y, SHEN D F, DUAN P, et al. MDOPE: Efficient Multi-dimensional Data Order Preserving Encryption Scheme. Information Sciences, 2022, 595: 334-343.
[15] ZHANG S N, RAY S, LU R X.SOREL: Efficient and Secure ORE-Based Range Query over Outsourced Data. IEEE Transactions on Big Data, 2022, 8(6): 1702-1715.
[16] TIAN P X, GUO C, CHOO K K R, et al. EAFS: An Efficient, Accurate, and Forward Secure Searchable Encryption Scheme Su-pporting Range Search. IEEE Systems Journal, 2022, 16(2): 3450-3460.
[17] GUO C, SU S H, CHOO K K R, et al. A Provably Secure and Effi-cient Range Query Scheme for Outsourced Encrypted Uncertain Data from Cloud-Based Internet of Things Systems. IEEE Internet of Things Journal, 2022, 9(3): 1848-1860.
[18] TIAN P X, GUO C, CHOO K K R, et al. A Privacy-Preserving Hybrid Range Search Scheme over Encrypted Electronic Medical Data in IoT Systems. IEEE Internet of Things Journal, 2023, 10(17): 15314-15324.
[19] WU S R, LI Q, LI G L, et al. ServeDB: Secure, Verifiable, and Efficient Range Queries on Outsourced Database // Proc of the IEEE 35th International Conference on Data Engineering. Washing-ton, USA: IEEE, 2019: 626-637.
[20] MENG Q, WENG J, MIAO Y B, et al. Verifiable Spatial Range Query Over Encrypted Cloud Data in VANET. IEEE Transactions on Vehicular Technology, 2021, 70(12): 12342-12357.
[21] CUI N N, YANG X C, CHEN Y L, et al. Secure Boolean Spatial Keyword Query with Lightweight Access Control in Cloud Environments. IEEE Internet of Things Journal, 2022, 9(12): 9503-9514.
[22] MA W J, PENG Y G, LIU X M, et al. VeriRange: A Verifiable Range Query Model on Encrypted Geographic Data for loT Environment. IEEE Internet of Things Journal, 2023. DOI: 10.1109/JIOT.2023.3294589.
[23] ZHANG M H, XIE Z L, YUE C, et al. Spitz: A Verifiable Database System. Proceedings of the VLDB Endowment, 2020, 13(12): 3449-3460.
[24] WANG Q, ZHOU F C, ZHOU B Y, et al. Privacy-Preserving Publicly Verifiable Databases. IEEE Transactions on Dependable and Secure Computing, 2022, 19(3): 1639-1654.
[25] YANG D Q, ZHANG D Q, ZHENG V W, et al. Modeling User Activity Preference by Leveraging User Spatial Temporal Characte-ristics in LBSNs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(1): 129-142.
[26] CHO E, MYERS S A, LESKOVEC J.Friendship and Mobility: User Movement in Location-Based Social Networks // Proc of the 17th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining. New York, USA: ACM, 2011: 1082-1090.
[27] BERNARDINELI D L. eBird Brazilian Birdwatching Observations: An Comprehensive Geo-Spatial Dataset for Bird Observation[EB/OL].[2023-09-20]. https://www.kaggle.com/datasets/danlessa/ebird-brazilian-observations.
[28] YANG D Q, ZHANG D Q, QU B Q.Participatory Cultural Ma-pping Based on Collective Behavior Data in Location-Based Social Networks. ACM Transactions on Intelligent Systems and Technology, 2016, 7(3): 1-23.
[29] SOHRABI B 2.3 Million US Wildfires(1992-2020) 6th Edition: Spatial Wildfire Occurrence Data for the United States, 1992-2020[EB/OL]. [2023-09-20]. https://www.kaggle.com/datasets/behroozsohrabi/us-wildfire-records-6th-edition.