Enabling Privacy-Preserving Range Queries in Blockchain-Based Collaborative Databases with Bilinear Pairings

doi:10.3969/j.issn.1671-1122.2023.03.003

Abstract

Abstract:

Database sharing is a data aggregation scheme that provides convenience for users to search all databases. Blockchain-based collaborative databases are widely adopted because they are more flexible, transparent, and can eliminate trust servers in the traditional centralized data-sharing model. However, due to wide attacking surfaces in a blockchain network, this decentralized data-sharing paradigm is subject to malicious data breaches. Untrusted blockchain nodes can directly obtain sensitive information from the blockchain. Therefore, failure to address these inherent security issues properly will hinder the wide adoption of secure decentralized applications. This paper devise a novel bit-block encryption scheme to support encrypted range queries via block-based pattern matching.The proposed scheme couldan simultaneously enables a dramatic query speed up and preserves semantic security guarantee. This paper complete the prototype implementation on Enthereum. Experiment results on real-world datasets demonstrate the feasibility and practicability of the proposed scheme.

Key words: encrypted data range query, searchable encryption, decentralized application, smart contract, blockchain

CLC Number:

TP309

LI Chunxiao, WANG Yaofei, XU Enliang, ZHAO Yu. Enabling Privacy-Preserving Range Queries in Blockchain-Based Collaborative Databases with Bilinear Pairings[J]. Netinfo Security, 2023, 23(3): 22-34.

Figures/Tables 8

References 55

[1]	ZHANG Jingyu, ZHONG Siqi, WANG Tian, et al. Blockchain-Based Systems and Applications: A Survey[J]. Journal of Internet Technology, 2020, 21(1): 1-14.
[2]	PENG Yanqing, DU Min, LI Feifei, et al. FalconDB: Blockchain-based Collaborative Database[C]// ACM. Proceedings of the 2020 ACM SIGMOD. New York: ACM, 2020: 352-637.
[3]	ORJUELA K G, GAONA-GARCIA P L, MARIN C E M. Towards an Agriculture Solution for Product Supply Chain Using Blockchain: Case Study Agro-Chain with BigchainDB[J]. Acta Agriculturae Scandinavica, Section B, Soil and Plant Science, 2020, 71(1): 1-16.
[4]	TIGANI J, NAIDU S. Google BigQuery Analytics[M]. Singapore: Wiley, 2014: 25-30.
[5]	WANG Sheng, DINH T T A, LIN Qian, et al. Forkbase: An Efficient Storage Engine for Blockchain and Forkable Applications[EB/OL]. (2018-02-14)[2022-12-06]. https://doi.org/10.48550/arXiv.1802.04949.
[6]	MOHAN C. Blockchains and Databases[EB/OL]. (2017-10-12)[2022-12-06]. https://www.xueshufan.com/publication/2764485190.
[7]	SHARMA E A S K. A Framework Of Big Data as Service Platform For Access Control & Privacy Protection Using Blockchain Network[J]. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 2021, 12(11): 476-485.
[8]	ZHANG Chen, MIAO Yinbin, XIE Qingyuan, et al. Privacy-Preserving Deduplication of Sensor Compressed Data in Distributed Fog Computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2022, 33(12): 4176-4191. doi: 10.1109/TPDS.2022.3179992 URL
[9]	GUO Yu, WANG Cong, YUAN Xingliang, et al. Enabling Privacy-Preserving Header Matching for Outsourced Middleboxes[C]// IEEE. IEEE/ACM International Symposium on Quality of Service (IWQoS’18). New York: IEEE, 2018: 1-10.
[10]	NAKAMOTO S. Bitcoin: A Peer-to-Peer Electronic Cash System[EB/OL]. (2009-03-14)[2022-12-06]. https://bitcoin.org/bitcoin.pdf.
[11]	WANG Mingyue, GUO Yu, ZHANG Chen, et al. MedShare: A Privacy-Preserving Medical Data Sharing System by Using Blockchain[J]. IEEE Transactions on Services Computing, 2021, 9: 438-451.
[12]	GUO Yu, XIE Hongcheng, MIAO Yinbin, et al. Fedcrowd: A Federated and Privacy-Preserving Crowdsourcing Platform on Blockchain[J]. IEEE Transactions on Services Computing, 2020, 15(4): 2060-2073. doi: 10.1109/TSC.2020.3031061 URL
[13]	GUO Yu, ZHANG Chen, WANG Cong, et al. Towards Public Verifiable and Forward-Privacy Encrypted Search by Using Blockchain[J]. IEEE Transactions on Dependable and Secure Computing, 2022, 5: 1-16. doi: 10.1109/TDSC.2008.9 URL
[14]	LUO Yuchuan, JIA Xiaohua, FU Shaojing, et al. pRide: Privacy-Preserving Ride Matching Over Road Networks for Online Ride-Hailing Service[J]. IEEE Transactions on Information Forensics and Security, 2019, 14(7): 1791-1802. doi: 10.1109/TIFS.2018.2885282 URL
[15]	LUO Yuchuan, XU Ming, HUANG Kai, et al. Efficient Auditing for Shared Data in the Cloud with Secure User Revocation and Computations Outsourcing[J]. Computers & Security, 2018, 73: 492-506. doi: 10.1016/j.cose.2017.12.004 URL
[16]	LUO Yuchuan, FU Shaojing, WANG Dongsheng, et al. Efficient and Generalized Geometric Range Search on Encrypted Spatial Data in the Cloud[C]// IEEE. 2017 IEEE/ACM 25th International Symposium on Quality of Service (IWQoS). New York: IEEE, 2017: 1-10.
[17]	SHU Jiang, JIA Xiaohua, YANG Kan, et al. Privacy-Preserving Task Recommendation Services for Crowdsourcing[J]. IEEE Transactions on Services Computing, 2018, 14(1): 235-247.
[18]	GUO Jianxiong, DING Xingjian, JIA Weijia, et al. Combinatorial Resources Auction in Decentralized Ege-Thing Systems Using Blockchain and Differential Privacy[J]. Information Sciences, 2021, 607: 211-229. doi: 10.1016/j.ins.2022.05.128 URL
[19]	ZHANG Chen, GUO Yu, DU Hongwei, et al. Pfcrowd: Privacy- Preserving and federated Crowdsourcing Framework by Using Blockchain[C]// IEEE. 2020 IEEE/ACM 28th International Symposium on Quality of Service (IWQoS). IEEE, 2020: 1-10.
[20]	SONG D X, WAGNER D, PERRIG A. Practical Techniques for Searches on Encrypted Data[C]// IEEE. Prooceedings of IEEE Symposium on Security and Privacy. New York: IEEE, 2000: 1-12.
[21]	SHU Jiangang, YANG Kan, JIA Xiaohua, et al. Proxy-Free Privacy-Preserving Task Matching with Efficient Revocation in Crowdsourcing[J]. IEEE Transactions on Dependable and Secure Computing, 2018, 18(1): 117-130. doi: 10.1109/TDSC.8858 URL
[22]	JIANG Jinghua, ZHENG Yifeng, SHI Zhenkui, et al. A Practical System for Privacy-Aware Targeted Mobile Advertising Services[J]. IEEE Transactions on Services Computing, 2020, 13(3): 410-424. doi: 10.1109/TSC.4629386 URL
[23]	REN Yingying, LIU Wei, LIU Anfeng, et al. A Privacy-Protected Intelligent Crowdsourcing Application of IoT Based on the Reinforcement Learning[J]. Future Generation Computer Systems, 2022, 127: 56-69. doi: 10.1016/j.future.2021.09.003 URL
[24]	GUO Yu, WANG Mingyue, WANG Cong, et al. Privacy-Preserving Packet Header Checking Over in-the-Cloud Middleboxes[J]. IEEE Internet of Things Journal, 2020, 7(6): 5359-5370. doi: 10.1109/JIoT.6488907 URL
[25]	LI Chunxiao, GUO Yu, WANG Xia. Towards Privacy-Preserving Dynamic Deep Packet Inspection over Outsourced Middleboxes[EB/OL]. (date-in-citation content-type="updated">2022-03-01)[2022-12-06]. https://doi.org/10.1016/j.hcc.2021.100033.
[26]	SHI Zhenkui, FU Xuemei, LI Xianxian, et al. ESVSSE: Enabling Efficient, Secure, Verifiable Searchable Symmetric Encryption[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(7): 3241-3254.
[27]	POPA R A, LI F H, ZELDOVICH N. An Ideal-Security Protocol for Order-Preserving Encoding[C]// IEEE. 2013 IEEE Symposium on Security and Privacy. New York: IEEE, 2013: 463-477.
[28]	BONEH D, LEWI K, RAYKOVA M, et al. Semantically Secure Order-Revealing Encryption: Multi-Input Functional Encryption Without Obfuscation[C]// Springer. Advances in Cryptology-EUROCRYPT. Berlin:Springer, 2015: 563-594.
[29]	BOLDYREVA A, CHENETTE N, O’NEILL A. Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions[C]// Springer. Advances in Cryptology-CRYPTO. Berlin:Springer, 2011: 578-595.
[30]	MAVROFORAKIS C, CHENETTE N, O’NEILL A, et al. Modular Order-Preserving Encryption, Revisited[C]// ACM. Proceedings of the 2015 ACM SIGMOD. New York: ACM, 2015: 763-777.
[31]	KERSCHBAUM F. Frequency-Hiding Order-Preserving Encryption: Germany, EP16001942.8[P]. 2019-11-06.
[32]	LEWI K, WU D J. Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds[C]ACM. Proceedings of ACM SIGSAC. New York: ACM, 2016: 1167-1178.
[33]	CHENETTE N, LEWI K, WEIS S A, et al. Practical Order-Revealing Encryption with Limited Leakage[C]// Springer. Proceedings of Fast Software Encryption. Berlin:Springer, 2016: 474-493.
[34]	GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[C]// ACM. Proceedings of STOC. New York: ACM, 2009: 169-178.
[35]	TAN B H M, LEE H T, WANG Huaxiong, et al. Efficient Private Comparison Queries Over Encrypted Databases Using Fully Homomorphic Encryption with Finite Fields[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 18(6): 5861-5874.
[36]	GUO Yu, YUAN Xingliang, WANG Xinyu, et al. Enabling Encrypted Rich Queries in Distributed Key-Value Stores[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(6): 1283-1297. doi: 10.1109/TPDS.71 URL
[37]	GRUBBS P, SEKNIQI K, BINDSCHAEDLER V, et al. Leakage-Abuse Attacks Against Order-Revealing Encryption[C]// IEEE. 2017 IEEE Symposium on Security and Privacy. New York: IEEE, 2017: 655-672.
[38]	NAVEED M, KAMARA S, WRIGHT C V. Inference Attacks on Property-Preserving Encrypted Databases[C]// ACM. Proceedings of ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 644-655.
[39]	CASH D, GRUBBS P, PERRY J, et al. Leakage-Abuse Attacks Against Searchable Encryption[C]// ACM. Proceedings of ACM CCS. New York: ACM, 2015: 668-679.
[40]	FULLER B, VARIA M, YERUKHIMOVICH A, et al. SoK: Cryptographically Protected Database Search[C]// IEEE. Proceedings of IEEE Symposium on Security and Privacy. New York: IEEE, 2017: 172-191.
[41]	YUAN Xingliang, GUO Yu, WANG Xinyu, et al. EncKV: An Encrypted Key-Value Store with Rich Queries[C]// ACM. Proceedings of ACM on Asia Conference on Computer and Communications Security. New York: ACM, 2017: 423-435.
[42]	FABER S, JARECKI S, KRAWCZYK H, et al. Rich Queries on Encrypted Data: Beyond Exact Matches[C]// Springer. Proceedings of ESORICS. Berlin:Springer, 2015: 1-31.
[43]	AGRAWAL R, KIERNAN J, SRIKANT R, et al. Order Preserving Encryption for Numeric Data[C]// ACM. Proceedings of ACM SIGMOD. New York: ACM, 2004: 563-574.
[44]	BOGATOV D, KOLLIOS G, REYZIN L. A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols[C]// ACM. Proceedings of the VLDB Endowment. New York: ACM, 2019: 933-947.
[45]	XU Cheng, ZHANG Ce, XU Jianliang. vChain: Enabling Verifiable Boolean Range Queries over Blockchain Databases[C]// ACM. Proceedings of SIGMOD. New York: ACM, 2019: 141-158.
[46]	ZHANG Ce, XU Cheng, XU Jianliang, et al. GEM2-Tree: A Gas-Efficient Structure for Authenticated Range Queries in Blockchain[C]// IEEE. Proceedings of IEEE 35th ICDE. New York: IEEE, 2019: 842-853.
[47]	GUO Yu, XIE Hongcheng, WANG Cong, et al. Enabling Privacy-Preserving Geographic Range Query in Fog-Enhanced IoT Services[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 19(5): 3401-3416. doi: 10.1109/TDSC.2021.3095933 URL
[48]	GUO Yu, YUAN Xingliang, WANG Xinyu, et al. Enabling Encrypted Rich Queries in Distributed Key-Value Stores[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(6): 1283-1297. doi: 10.1109/TPDS.71 URL
[49]	YUAN Xingliang, GUO Yu, WANG Xinyu, et al. Enckv: An Encrypted Key-Value Store with Rich Queries[C]// ACM. Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. New York: ACM, 2017: 423-435.
[50]	LUO Xiaofang. Design and Implementation of Decentralized Swarm Intelligence E-Commerce Model Based on Regional Chain and Edge Computing[J]. Complexity, 2021, 5: 1-11.
[51]	HU Shengshan, CAI Chengjun, WANG Qian, et al. Searching an Encrypted Cloud Meets Blockchain: A Decentralized, Reliable and Fair Realization[C]// IEEE. Proceedings of IEEE INFOCOM. New York: IEEE, 2018: 792-800.
[52]	GUO Yu, ZHANG Chen, JIA Xiaohua. Verifiable and Forward-Secure Encrypted Search Using Blockchain Techniques[C]// IEEE. Proceedings of IEEE International Conference on Communications (ICC). New York:IEEE, 2020: 1-7.
[53]	KOSBA A, MILLER A, SHI E, et al. Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts[C]// IEEE. Proceedings of IEEE Symposium on Security and Privacy (SP). New York:IEEE, 2016: 839-858.
[54]	CASH D, JAEGER J, JARECKI S, et al. Dynamic Searchable Encryption in Very Large Databases: Data Structures and Implementation[EB/OL]. (2014-01-18)[2022-12-06]. https://www.researchgate.net/publication/269196927.
[55]	CURTMOLA R, GARAY J A, KAMARA S, et al. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions[J]. Journal of Computer Security, 2011, 19(5): 895-934. doi: 10.3233/JCS-2011-0426 URL

密文数量/条	2 bit方案/s			4 bit方案/s			同态加密方案/s
密文数量/条	陷门	EncIndex算法	RngMatch算法	陷门	EncIndex算法	RngMatc算法	Encryption	Comparison
100	0.70	1.09	1.71	0.56	1.56	1.30	4.01	4.76
200	1.41	2.18	3.60	1.21	3.08	2.62	8.11	8.31
400	2.89	4.36	7.25	2.25	6.15	5.33	16.31	16.62
800	5.73	8.70	14.31	4.46	12.36	10.60	32.71	33.12
1600	11.12	17.46	29.21	8.96	24.56	21.65	65.16	66.30

索引数量/条	1 bit方案/MB	2 bit方案/MB	4 bit方案/MB	8 bit方案/MB
100	0.15	0.16	0.47	51.95
200	0.30	0.32	0.93	103.90
400	0.60	0.64	1.86	207.82
800	1.20	1.29	3.72	415.64
1600	2.40	2.58	7.45	831.28