Details

Autor(en) / Beteiligte

• Dong Xie
• Guanru Li
• Bin Yao
• Xuan Wei
• Xiaokui Xiao
• Yunjun Gao
• Minyi Guo

Titel

Practical private shortest path computation based on Oblivious Storage

Ist Teil von

• 2016 IEEE 32nd International Conference on Data Engineering (ICDE), 2016, p.361-372

Ort / Verlag

IEEE

Erscheinungsjahr

2016

Quelle

IEEE Electronic Library Online

Beschreibungen/Notizen

• As location-based services (LBSs) become popular, location-dependent queries have raised serious privacy concerns since they may disclose sensitive information in query processing. Among typical queries supported by LBSs, shortest path queries may reveal information about not only current locations of the clients, but also their potential destinations and travel plans. Unfortunately, existing methods for private shortest path computation suffer from issues of weak privacy property, low performance or poor scalability. In this paper, we aim at a strong privacy guarantee, where the adversary cannot infer almost any information about the queries, with better performance and scalability. To achieve this goal, we introduce a general system model based on the concept of Oblivious Storage (OS), which can deal with queries requiring strong privacy properties. Furthermore, we propose a new oblivious shuffle algorithm to optimize an existing OS scheme. By making trade-offs between query performance, scalability and privacy properties, we design different schemes for private shortest path computation. Eventually, we comprehensively evaluate our schemes upon real road networks in a practical environment and show their efficiency.