Oblivious k-Nearest Neighbors for Secure Map Applications
Abstract
Cloud storage enables users to access and store large amounts of data on servers anytime and anywhere at little to no cost. Map applications are specific examples of cloud storage servers that allow users to query for nearby points of interest. Despite the many benefits offered by map applications, users are susceptible to data leakage through their access patterns, which is a significant security risk for these applications since the users location and other sensitive data can be leaked. In order to mitigate access pattern leakage and implement security in map applications, we have developed a novel remotely-stored network data structure, the ORAM-backed Hilbert B-tree. The novel data structure combines existing features such as the B-tree data structure, k-Nearest Neighbor (k-NN) search algorithms, Hilbert Curves, and Oblivious Random Access Memory (ORAM) algorithms, but ultimately allows users to make oblivious queries in map applications, a function that has not yet been conceived for such applications. This provides a significant improvement in security for map applications without compromising performance, preventing sensitive information such as the users physical location from being leaked.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 06, 2020
- Accession Number
- AD1136693
Entities
People
- Jamie W. Lee
Organizations
- United States Naval Academy