Cloud-Based Approximate Constrained Shortest Distance Queries Over Encrypted Graphs With Privacy Protection
| Autor: | Liehuang Zhu, Baoli Ma, Rashid Mijumbi, Xiaojiang Du, Meng Shen, Jiankun Hu |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Cryptography and Security Shortest distance Theoretical computer science Computer Networks and Communications Computer science business.industry Homomorphic encryption 020206 networking & telecommunications Cloud computing 02 engineering and technology Encryption Graph Ciphertext 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Safety Risk Reliability and Quality business Cryptography and Security (cs.CR) Computer Science::Databases Computer Science::Cryptography and Security |
| Zdroj: | IEEE Transactions on Information Forensics and Security. 13:940-953 |
| ISSN: | 1556-6021 1556-6013 |
| DOI: | 10.1109/tifs.2017.2774451 |
| Popis: | Constrained shortest distance (CSD) querying is one of the fundamental graph query primitives, which finds the shortest distance from an origin to a destination in a graph with a constraint that the total cost does not exceed a given threshold. CSD querying has a wide range of applications, such as routing in telecommunications and transportation. With an increasing prevalence of cloud computing paradigm, graph owners desire to outsource their graphs to cloud servers. In order to protect sensitive information, these graphs are usually encrypted before being outsourced to the cloud. This, however, imposes a great challenge to CSD querying over encrypted graphs. Since performing constraint filtering is an intractable task, existing work mainly focuses on unconstrained shortest distance queries. CSD querying over encrypted graphs remains an open research problem. In this paper, we propose Connor , a novel graph encryption scheme that enables approximate CSD querying. Connor is built based on an efficient, tree-based ciphertext comparison protocol, and makes use of symmetric-key primitives and the somewhat homomorphic encryption, making it computationally efficient. Using Connor , a graph owner can first encrypt privacy-sensitive graphs and then outsource them to the cloud server, achieving the necessary privacy without losing the ability of querying. Extensive experiments with real-world data sets demonstrate the effectiveness and efficiency of the proposed graph encryption scheme. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|