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