Outsourcing Database Join Query Verification Scheme Based on Authentication Tree

doi:10.3969/j.issn.1671-1122.2020.02.012

Abstract

Abstract:

While outsourcing database is widely used, its security is greatly challenged. Users cannot guarantee the correctness and integrity of the query results when querying data. Aiming at the problem that the existing outsourcing databases can not support connection query verification, this paper proposes a connection query verification model based on authentication tree, and gives the formal definition of the model and the definition of the correctness and security of the model. This paper uses bilinear map accumulator, authentication tree and other technologies to build a connection query verification scheme of outsourcing database based on authentication tree, and uses the VBDHE and q-BSDH difficulty assumption of cryptography to give the security analysis. This paper proves that the adversary can’t make the verification pass by falsifying the wrong results, thus proving the correctness of the scheme. Experimental results and performance analysis show that the proposed scheme has higher efficiency than other schemes in key generation, query verification, communication overhead, storage overhead, etc.

Key words: outsourcing database, verifiable set operation, authentication tree, join query

CLC Number:

TP309

HOU Lin, FENG Da, XUAN Pengkai, ZHOU Fucai. Outsourcing Database Join Query Verification Scheme Based on Authentication Tree[J]. Netinfo Security, 2020, 20(2): 91-97.

Figures/Tables 6

References 15

[1]	XIAN Hequn, FENG Dengguo.An Integrity Checking Scheme in Outsourced Database Model[J]. Journal of Computer Research and Development, 2010, 47(6): 1107-1115.
	咸鹤群,冯登国.外包数据库模型中的完整性检测方案[J]. 计算机研究与发展, 2010, 47(6):1107-1115.
[2]	GUPTA R.Above the Clouds: A View of Cloud Computing[J]. Eecs Department University of California Berkeley, 2012, 53(4): 50-58.
[3]	RIVEST R L, SHAMIR A, ADLEMAN L.A Method for Obtaining Digital Signatures and Public-key Cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.
[4]	LI Feifei, HADJIELEFTHERIOU M, KOLLIOS G, et al.Dynamic Authenticated Index Structures for Outsourced Databases[C]//ACM. International Conference on Management of Data and Symposium on Principles Database and Systems, June 27-29, 2006, Chicago, IL, USA. New York: ACM, 2006: 121-132.
[5]	YANG Yin, PAPADOPOULOS S, PAPADIAS D, et al.Authenticated Indexing for Outsourced Spatial Databases[J]. The VLDB Journal, 2009, 18(3): 631-648.
[6]	YIU M L, LO E, YUNG D.Authentication of Moving kNN Queries[C]// IEEE. IEEE 27th International Conference on Data Engineering, April 11-16, 2011, Hannover, Germany. NJ: IEEE, 2011: 565-576.
[7]	LI Feifei, HADJIELEFTHERIOU M, KOLLIOS G, et al.Authenticated Index Structures for Aggregation Queries[J]. ACM Transactions on Information & System Security, 2010, 13(4): 1-35.
[8]	HU Haibo, XU Jianliang, CHEN Qian, et al.Authenticating Location-based Services without Compromising Location Privacy[C]//ACM. International Conference on Management of Data, May 20-25, 2012, Scottsdale Arizona, USA. New York: ACM, 2012: 301-312.
[9]	CHEN Qian, HU Haibo, XU Jianliang.Authenticating Top-k Queries in Location-based Services with Confidentiality[J]. Proceedings of the Vldb Endowment, 2014, 7(1): 49-60.
[10]	PAPADOPOULOS S, WANG Lixing, YANG Yin, et al.Authenticated Multistep Nearest Neighbor Search[J]. IEEE Transactions on Knowledge & Data Engineering, 2011, 23(5): 641-654.
[11]	HUANG Qingyuan, WANG Yongjun, SU Jinshu.A Bilinear Pairing-based Key Agreement Protocol in MANET[J]. Computer Science, 2008, 35(2): 78-80.
	黄清元,王勇军,苏金树.一种基于双线性配对的移动自组网密钥协商协议[J]. 计算机科学, 2008, 35(2):78-80.
[12]	CHEN Anlin, PAN Jin, GUO Chao.Research on Authenticated Key Agreement Protocol in Cross-domain Two-party for Mobile Ad Hoc Network[J]. Application Research of Computers, 2011, 28(7): 2734-2737.
	陈安林,潘进,郭超.移动自组网中跨域两方认证密钥协商协议研究[J]. 计算机应用研究, 2011, 28(7):2734-2737.
[13]	AU M H, TSANG P P, SUSILO W, et al.Dynamic Universal Accumulators for DDH Groups and Their Application to Attribute-based Anonymous Credential Systems[M]// Springer. Topics in Cryptology - CT-RSA 2009. Heidelberg: Springer-Verlag, 2009: 295-308.
[14]	NGUYEN L.Accumulators from Bilinear Pairings and Applications[M]// Springer. Topics in Cryptology - CT-RSA 2005. Heidelberg: Springer Berlin, 2005: 275-292.
[15]	BITANSKY N, CANETTI R, CHIESA A, et al. Recursive Composition and Bootstrapping for SNARKs and Proof-carrying Data[EB/OL]. , 2019-9-20.