1. SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates 2017 FinancialCryptography Privacy SearchableEncryption
    Qian Wang, Kui Ren, Minxin Du, Aziz Mohaisen
    [View PDF on fc17.ifca.ai]
    [Show BibTex Citation]

    author = {Qian Wang and
    Kui Ren and
    Minxin Du and
    Qi Li and
    Aziz Mohaisen},
    editor = {Aggelos Kiayias},
    title = {SecGDB: Graph Encryption for Exact Shortest Distance Queries with
    Efficient Updates},
    booktitle = {Financial Cryptography and Data Security - 21st International Conference,
    {FC} 2017, Sliema, Malta, April 3-7, 2017, Revised Selected Papers},
    series = {Lecture Notes in Computer Science},
    volume = {10322},
    pages = {79--97},
    publisher = {Springer},
    year = {2017},
    url = {https://doi.org/10.1007/978-3-319-70972-7\_5},
    doi = {10.1007/978-3-319-70972-7\_5},
    timestamp = {Wed, 25 Sep 2019 18:15:50 +0200},
    biburl = {https://dblp.org/rec/bib/conf/fc/Wang0DLM17},
    bibsource = {dblp computer science bibliography, https://dblp.org}

In the era of big data, graph databases have become in-creasingly important for NoSQL technologies, and many systems (e.g.,online social networks, world-wide web and electrical grids, etc.) can be modeled as graphs for semantic queries. Meanwhile, with the advent of cloud computing, data owners are highly motivated to outsource and s-tore their massive potentially-sensitive graph data on remote untrusted servers in an encrypted form, expecting to retain the ability to query over the encrypted graphs.To allow e↵ective and private queries over encrypted data, the most well-studied class of structured encryption schemes are searchable symmetric encryption (SSE) designs, which encrypt search structures (e.g., inverted indexes based on keyword-file pairs) for retrieving data files of interestfrom remote servers. So far, however, the problem of graph data encryption that supports customized queries has received limited attention inthe literature. In this paper, we tackle the challenge of designing a Se-cure Graph DataBase encryption scheme (SecGDB) to encrypt graph structures and enforce private graph queries over the encrypted graph database. Specifically, our construction strategically makes use of e�cient additively homomorphic encryption and garbled circuits to support the shortest distance queries with optimal time and storage complexities. Toachieve better amortized time complexity over multiple queries, we further propose an auxiliary data structure called query historyand storeit on the remote server to act as a “caching” resource. Compared with the state-of-the-art solutions, our design returns exact shortest distancequery results instead of approximate ones and allows e�cient graph up-date queries over large-scale encrypted graphs. We prove that our construction is adaptively semantically-secure in the random oracle model and finally implement and evaluate it on various representative real-world datasets, showing that our approach is practically efficient in terms of both storage and computation.