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

Vulnerability Analysis of Geohash Code Against k-nearest Neighbor Attack

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

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.