In recent years there has been growing popularity of leveraging cloud computing for storing and querying attributed graphs, which have been widely used to model complex structured data in various applications. Such trend of outsourced graph analytics, however, is accompanied with critical privacy concerns regarding the information-rich and proprietary attributed graph data. In light of this, we design, implement, and evaluate OblivGM, a new system aimed at oblivious graph analytics services outsourced to the cloud. OblivGM focuses on the support for attributed subgraph matching, one popular and fundamental graph query functionality aiming to retrieve from a large attributed graph subgraphs isomorphic to a small query graph. Built from a delicate synergy of insights from attributed graph modelling and advanced lightweight cryptography, OblivGM protects the confidentiality of data content associated with attributed graphs and queries, conceals the connections among vertices in attributed graphs, and hides search access patterns. Meanwhile, OblivGM flexibly supports oblivious evaluation of varying subgraph queries, which may contain equality and/or range predicates. Extensive experiments over a real-world attributed graph dataset demonstrate that while providing strong security guarantees, OblivGM achieves practically affordable performance (with query latency on the order of a few seconds).
翻译:近年来,利用云计算来储存和查询各种用途的图表越来越受欢迎,这种云计算已被广泛用于在各种应用中模拟结构化的复杂数据。但是,外包图表分析的这种趋势伴随着对信息丰富和专有的图表数据的重大隐私关切。鉴于此,我们设计、实施和评价ObliivGM,这是一个旨在将图解服务外包给云的新系统,目的是掩盖图解分析服务;OblivGM侧重于支持被分配子图匹配的支持,一个广受欢迎的基本图形查询功能,目的是从大型被分配的图子图子图解中检索到的是一个小型查询图解形态。由于从被分配的图象模型和高级轻量级密码学的洞察到的微妙的协同效应,OblivGM保护了与被分配的图表和查询有关的数据内容的保密性,掩盖了被分配图图图解中的脊椎之间的联系,并隐藏了搜索访问模式。同时,OblivGM灵活支持对各种子查询的模糊评价,其中可能包含平等和(或)范围的上游上游上游查询。在现实世界中进行广泛的实验,在可承受的几号图表运行上提供强有力的安全保障的运行。