Geohash编码抗k近邻攻击的脆弱性分析

doi:10.3969/j.issn.1671-1122.2021.02.002

信息网络安全 ›› 2021, Vol. 21 ›› Issue (2): 10-15.doi: 10.3969/j.issn.1671-1122.2021.02.002

Geohash编码抗k近邻攻击的脆弱性分析

涂国庆¹^,², 杨延浩¹^,²(), 刘树波³

1.武汉大学国家网络安全学院,武汉 430072
2.空天信息安全与可信计算教育部重点实验室,武汉 430072
3.武汉大学计算机学院,武汉 430070

收稿日期:2020-10-21 出版日期:2021-02-10 发布日期:2021-02-23
通讯作者: 杨延浩 E-mail:yangyanhao@whu.edu.cn
作者简介:涂国庆（1974—）,男,湖北,副教授,博士,主要研究方向为物联网安全|杨延浩（1997—）,男,山东,硕士研究生,主要研究方向为数据库安全|刘树波（1970—）,男,黑龙江,教授,博士,主要研究方向为物联网安全
基金资助:
国家自然科学基金(41671443);武汉市应用基础前沿项目(2020020601012266)

Vulnerability Analysis of Geohash Code Against k-nearest Neighbor Attack

TU Guoqing¹^,², YANG Yanhao¹^,²(), LIU Shubo³

1. School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China
2. Key Laboratory of Aerospace Information Security and Trusted Computing, Ministry of Education, Wuhan 430072, China
3. School of Computer Science,Wuhan University, Wuhan 430070, China

Received:2020-10-21 Online:2021-02-10 Published:2021-02-23
Contact: YANG Yanhao E-mail:yangyanhao@whu.edu.cn

摘要/Abstract

摘要：

Geohash编码作为一种降维技术目前已应用于空间数据库和空间数据引擎中,但其安全性还有待进一步研究。文章关注Geohash编码存在的安全漏洞,从理论上分析了此种降维技术产生推理通道的原因,并提出一种基于k近邻查询的加密Geohash字段重构算法,通过观察大量k近邻查询响应中的明文信息进行统计推断并重构出加密Geohash的原始值。对加密兴趣点数据库进行重构实验,实验表明,观察到的查询响应数量越多,重构值的精确度越高。在Geohash编码精度为30 bit的情况下,当观察到100000到3000000次查询响应时,重构值与原始值平均误差为0.074%到0.015%。该实验揭示了Geohash编码在抵抗k近邻查询推理攻击方面的脆弱性及形成机理,将促进相关地理信息系统行业的安全应用与研究。

关键词: 空间数据库, Geohash编码, k近邻查询, 可搜索加密, 数据库推理攻击

Abstract:

As a dimensionality reduction technology, Geohash coding has been applied to many spatial databases and spatial data engines, but there is no research on its security. This paper focuses on the security vulnerabilities in Geohash encoding, theoretically analyzes the reason why this dimensionality reduction technology produces inference channels, and proposes an encrypted Geohash field reconstruction algorithm based on k nearest neighbor query, by observing a large number of k nearest neighbor query responses for plaintext information, perform statistical inference and reconstruct the original value of encrypted Geohash. Reconstruction experiments on the encrypted interest point database show that the more the number of query responses observed, the higher the accuracy of the reconstruction value. In the case of Geohash coding accuracy of 30bit, when 100000 to 3000000 query responses are observed, the average error between the reconstructed value and the original value is 0.074% to 0.015%. This work reveals the vulnerability and formation mechanism of Geohash coding in resisting k nearest neighbor query inference attacks, and will promote the security application and research of related geographic information system industries.

Key words: spatial database, Geohash coding, k-nearest neighbor query, searchable encryption, database reasoning attack

中图分类号:

TP309

涂国庆, 杨延浩, 刘树波. Geohash编码抗k近邻攻击的脆弱性分析[J]. 信息网络安全, 2021, 21(2): 10-15.

TU Guoqing, YANG Yanhao, LIU Shubo. Vulnerability Analysis of Geohash Code Against k-nearest Neighbor Attack[J]. Netinfo Security, 2021, 21(2): 10-15.

图/表 6

图1

图2

图3

图4

表1

表2

参考文献 15

[1]	JIN An, CHENG Chengqi, SONG Shuhua, et al. Regional Query of Area Data Based on Geohash[J]. Geography and Geo-information Science, 2013,29(5): 31-35.
	金安, 程承旗, 宋树华, 等. 基于 Geohash 的面数据区域查询[J]. 地理与地理信息科学, 2013,29(5): 31-35.
[2]	HUANG Keying, LI Guoqing, WANG Jian. Rapid Retrieval Strategy for Massive Remote Sensing Metadata Based on GeoHash Coding[J]. Remote Sensing Letters, 2018,9(11): 1070-1078.
[3]	ZHOU Chang, LU Huimei, XIANG Yong, et al. GeohashTile: Vector Geographic Data Display Method Based on Geohash[J]. ISPRS International Journal of Geo-Information, 2020,9(7): 418-443.
[4]	XIANG Longgang, WANG Dehao, GONG Jianya. Organization and Efficient Range Query of Large Trajectory Data Based on Geohash[J]. Geomatics and Information Science of Wuhan University, 2017,42(1): 21-27.
	向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的 Geohash 编码组织及高效范围查询[J]. 武汉大学学报(信息科学版), 2017,42(1): 21-27.
[5]	HE Shouwu, CHU Longxian, LI Xiaoying. Spatial Query Processing for Location Based Application on Hbase[C]//IEEE. 2nd International Conference on Big Data Analysis (ICBDA), March 10-12, 2017, Bejing, China. New York: IEEE, 2017: 110-114.
[6]	TAKASU A. An Efficient Distributed Index for Geospatial Databases[C]//Springer. Database and Expert Systems Applications, September 1-4, 2015, Valencia, Spain. Nature Switzerland AG: Springer, 2015: 28-42.
[7]	BAN Ya, WANG Rui, LIU Hongjing, et al. An Efficient Distributed Index for Geospatial Databases[C]//Atlantis Press. International Conference on Computer Modeling, Simulation and Algorithm (CMSA), April, 22-23, 2018, Beijing,China. Paris: Atlantis Press, 2018: 385-388.
[8]	WU Ke. Research on GPU-based Spatial Data Index and Query Technology[D]. Xi’an: Xidian University, 2018.
	吴珂. 基于GPU的空间数据索引与查询技术研究[D]. 西安:西安电子科技大学, 2018.
[9]	BOST R. Forward Secure Searchable Encryption[C]//ACM. Proceedings of the 23th ACM Conference on Computer and Communications Security (ACM CCS), October 24-28, 2016, Vienna Austria. New York: ACM, 2016: 1143-1154.
[10]	CASH D, JAEGER J, JARECKI S, et al. Dynamic Searchable Encryption in Very-large Databases: Data Structures and Implementation[C]//ISOC. Network & Distributed System Security Symposium (NDSS), February 23-26, 2014, San Diego, CA, USA. Reston VA: ISOC, 2014: 23-26.
[11]	CURTMOLA R, GARAY J, KAMARA S, et al. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions[J]. Journal of Computer Security, 2011,19(5): 895-934.
[12]	KELLARIS G, KOLLIOS G, NISSIM K, et al. Generic Attacks on Secure Outsourced Databases[C]//ACM. Proceedings of the 23th ACM Conference on Computer and Communications Security (ACM CCS), October 24-28, 2016, Vienna Austria. New York: ACM, 2016: 1329-1340.
[13]	LACHARITÉ M S, MINAUD B, PATERSON K G. Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage[C]//IEEE. 2018 IEEE Symposium on Security and Privacy (SP), May 20-24, 2018, San Francisco, CA, USA. New York: IEEE, 2018: 297-314.
[14]	KORNAROPOULOS E M, PAPAMANTHOU C, TAMASSIA R. Data Recovery on Encrypted Databases with k-nearest Neighbor Query Leakage[C]//IEEE. 2019 IEEE Symposium on Security and Privacy (SP), May 19-23, 2019, San Francisco, CA, USA. New York: IEEE, 2019: 1033-1050.
[15]	GRUBBS P, LACHARITÉ M S, MINAUD B, et al. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks[C]//IEEE. 2019 IEEE Symposium on Security and Privacy (SP), May 19-23, 2019, San Francisco, CA, USA. New York: IEEE, 2019: 1067-1083.

模拟次数/万次	原始值	10	100	300
汉南区	wt3h7v	wt3h8r	wt3h7w	wt3h7w
蔡甸区	wt3jez	wt3jf4	wt3jf9	wt3jf3
汉阳区	wt3jyg	wt3jyu	wt3jyr	wt3jyj
硚口区	wt3jyy	wt3jz1	wt3jz1	wt3jyx
江夏区	wt3kc6	wt3kc7	wt3kcj	wt3kc6
洪山区	wt3m9b	wt3m9s	wt3m9n	wt3m9f
武昌区	wt3mc1	wt3mch	wt3mc9	wt3mc2
东西湖区	wt3njn	wt3nje	wt3nk2	wt3njq
江汉区	wt3q06	wt3q0p	wt3q0h	wt3q05
江岸区	wt3q0f	wt3q0y	wt3q0r	wt3q0d
青山区	wt3q6c	wt3q6n	wt3q6j	wt3q6b
黄陂区	wt3rdt	wt3rdn	wt3rdt	wt3rdp
新洲区	wt3xkq	wt3xkm	wt3xk6	wt3xkk

Geohash编码抗k近邻攻击的脆弱性分析

Vulnerability Analysis of Geohash Code Against k-nearest Neighbor Attack

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 15

相关文章 8

编辑推荐

Metrics

本文评价

[1]	张应辉, 朱甜, 郑东. 基于区块链的多关键字细粒度可搜索加密方案[J]. 信息网络安全, 2021, 21(2): 34-44.
[2]	周权, 杨宁滨, 许舒美. 基于FBDH算法的容错可验证公钥可搜索加密方案[J]. 信息网络安全, 2020, 20(3): 29-35.
[3]	张玉磊, 刘祥震, 郎晓丽, 王彩芬. 云环境下基于无证书的多服务器可搜索加密方案[J]. 信息网络安全, 2019, 19(3): 72-80.
[4]	陈兰香, 邱林冰. 基于Merkle哈希树的可验证密文检索方案[J]. 信息网络安全, 2017, 17(4): 1-8.
[5]	张楠, 陈兰香. 一种高效的支持排序的关键词可搜索加密系统研究[J]. 信息网络安全, 2017, 17(2): 43-50.
[6]	陆海宁. 可隐藏搜索模式的对称可搜索加密方案[J]. 信息网络安全, 2017, 17(1): 38-42.
[7]	. 基于密文的中文关键词模糊搜索方案[J]. , 2014, 14(7): 69-.
[8]	王保民;何智灵;罗文俊. 基于云存储的多用户可搜索加密方案[J]. , 2013, 13(12): 0-0.