MIDN 1/C Jamie W. Lee - 3rd Company

Oblivious k-Nearest Neighbors for Secure Map Applications

Advisers: Associate Professor Daniel S. Roche, Computer Science Department, Assistant Professor Travis Mayberry, Cyber Science Department
External Collaborators: Associate Professor Adam J. Aviv, George Washington University
Major: Computer Science

Description: 
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 user’s 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 user’s physical location from being leaked.

Watch the Recorded Presentation:

Comments or Questions for the Trident