Source-linked AI summary
Cloud-Based Approximate Constrained Shortest Distance Queries Over Encrypted Graphs With Privacy Protection
Meng Shen, Baoli Ma, Liehuang Zhu, Rashid Mijumbi, Xiaojiang Du, Jiankun Hu
TL;DR
Encrypted graphs make constraint filtering difficult, leaving privacy-preserving CSD querying unresolved. Connor combines encrypted graph indexing with tree-based ciphertext comparison and cryptographic primitives to support approximate CSD queries, with security analysis and real-world experiments demonstrating effectiveness and efficiency.
Problem
Encrypted-graph methods support shortest-distance queries but do not provide constraint filtering, leaving privacy-preserving CSD querying unresolved.
Method
Connor uses secure 2-hop cover labeling, PRFs, ORE, SWHE, and a tree-based ciphertext comparison protocol for approximate CSD queries over encrypted graphs.
Results
Connor achieves CQA2-security under secure cryptographic primitives and is evaluated through a prototype and extensive experiments on real-world datasets.
Takeaways & Limitations
Connor provides a practical graph-encryption scheme intended to preserve privacy while retaining cloud-based approximate CSD query capability.
Abstract
from arXiv · showhide
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 datasets demonstrate the effectiveness and efficiency of the proposed graph encryption scheme.
I. INTRODUCTION
Cloud outsourcing creates a privacy–querying challenge because encrypted graphs hinder constraint filtering for CSD queries. Connor addresses this gap with an approximate encrypted-graph scheme using secure indexing, ciphertext comparison, and cryptographic protection.
- Motivation: Cloud outsourcing motivates graph encryption, but encrypted graphs make ordinary graph operations such as addition, multiplication, and comparison difficult.Graph owners seek cloud-based storage while protecting privacy-sensitive graph data.
- Problem: CSD queries find shortest distances subject to a cost threshold, including practical routing scenarios with multiple criteria.The paper focuses on single-constraint CSD queries and notes that multi-constraint queries can often be decomposed into sub-queries.
- Research gap: Existing encrypted-graph methods support shortest-distance queries but cannot perform constraint filtering, so they cannot directly answer CSD queries.This leaves privacy-preserving CSD querying unresolved.
- Approach: Connor enables approximate CSD querying over encrypted graphs using secure 2-hop cover labeling, PRFs, ORE, SWHE, and tree-based ciphertext comparison.The comparison protocol accelerates cloud-side constraint filtering while protecting graph attributes.
- Contributions: The paper reports computational efficiency, controlled-disclosure ciphertext comparison, CQA2-security, and evaluation on real-world datasets.Its stated contribution includes answering α-CSD queries in milliseconds and demonstrating effectiveness and efficiency experimentally.
III. BACKGROUND
The background formalizes approximate CSD queries on directed weighted graphs and introduces the α-CSD guarantee. It also uses α-dominance to remove redundant index entries and motivates extending 2HCLI beyond unconstrained distance queries.
- Graph model: The paper models a directed graph whose edges have nonnegative distance and cost values, with cost serving as the constraint.Path distance and path cost are defined as sums over the corresponding edge attributes.
- Approximate CSD query: An α-CSD query returns a path satisfying c(P) ≤ θ and d(P) ≤ α · dopt, where dopt is the exact constrained optimum.The approximation ratio α controls the allowed distance relative to the optimal feasible answer.
- Approximate CSD query: In the example, the exact constrained answer has distance 6, while α = 1.5 permits a valid answer of distance 8 under the same cost constraint.The example path has cost 3 < θ = 4 and distance 8 < 9 = α · dopt.
- Index reduction: Path P1 α-dominates P2 when P1 has no greater cost and distance no greater than α times P2's distance.This principle filters redundant index entries and reduces graph-index construction complexity.
B. Constructing Labeling Index
The 2HCLI represents shortest-distance information through paired in-label and out-label sets, then extends this structure for constrained queries by retaining distance–cost path entries and filtering dominated entries offline.
- Basic 2HCLI: A 2HCLI stores in-label and out-label entities that encode shortest distances and allow queries to find common intermediate vertices.For an origin s and destination t, the query intersects Δout(s) and Δin(t), then selects the shortest resulting distance.
- Constrained labeling: CSD labeling associates each candidate path with a distance–cost pair, requiring the query to minimize distance while enforcing the cost threshold.For each common vertex, the online filter retains candidates satisfying c(a,v) + c(v,c) ≤ θ and chooses the minimum distance sum.
- Basic 2HCLI: 5 is the basic shortest distance from a to c because the route through e has total distance 5, versus 6 through b.
- Constrained labeling: Offline filtering reduces labeling complexity by removing entries that are α-dominated while preserving correct answers independently of any particular query constraint.In the example, the path with tuple (3,2) α-dominates the path with tuple (2,6), so the latter is removed.
- System model: The privacy-preserving system consists of a user who builds and outsources the encrypted index and a cloud server that processes query tokens and returns results.
B. Security Model
The security model defines privacy through a CQA2-style real-versus-ideal experiment, requiring that an adaptive cloud-server adversary cannot distinguish the real encrypted scheme from a simulator using prescribed leakage.
- Security definition: The model treats the adversary as semi-honest and defines security using setup and query leakage functions LSetup and LQuery.
- Real experiment: In the real experiment, the challenger encrypts an adversary-chosen graph and supports a polynomial number of adaptive queries.
- Ideal experiment: In the ideal experiment, a simulator constructs the encrypted index from LSetup and simulates query execution from LQuery.
C. Preliminaries
Connor builds encrypted CSD querying from a graph-encryption construction using 2HCLI, PRF-based identifiers, SWHE-encrypted distances, and order-revealing encryption for costs.
- Connor construction: Connor is introduced as a graph encryption scheme for privacy-preserving α-CSD querying.
- Cryptographic components: The construction uses PRFs and somewhat homomorphic encryption, with ORE supporting comparison of encrypted costs.The basic construction generates secret keys, encrypts the graph index, and processes query tokens over the encrypted index.
- Distance protection: Distances are encoded as 2N−d before SWHE encryption, enabling homomorphic computation of minimum distance sums.The construction sets N=2B+1, where B is the maximum distance over the sketches.
- Cost protection: Costs are multiplied by a private amplification factor φ and encrypted with ORE so the cloud can perform constraint filtering without learning real costs.
- Leakage boundary: The straightforward encrypted index leaks sketch lengths, ORE cost order, and common-vertex counts, motivating the improved construction.
B. Privacy-preserving α-CSD Querying
The privacy-preserving α-CSD scheme improves the encrypted index and query procedures by splitting sketches, masking entries, filtering costs through a query tree, and homomorphically aggregating retained distances.
- GraphEnc2: GraphEnc2 improves GraphEnc1 through revised encrypted-index construction and CSD query procedures.
- Setup: Setup builds a 2HCLI and encrypts its associated sketches before outsourcing the resulting index.
- Query processing: The query token contains PRF-derived labels and a cost-constraint tree based on φ·θ, enabling the cloud to locate relevant encrypted entries.
- Leakage protection: GraphEnc2 stores each encrypted sketch entry separately, preventing the static index from revealing sketch sizes, common-vertex counts, or cost ordering.
- Distance computation: After cost filtering, the cloud computes an encrypted product of candidate distance values and returns it for user-side decryption.
VI. TREE-BASED CIPHERTEXTS COMPARISON APPROACH
The paper introduces a tree-based ciphertext comparison approach for cost constraint filtering in its encrypted-graph scheme.
- The approach supports cost constraint filtering in Connor's graph encryption scheme.
A. Scenarios
The protocol lets a cloud server compare encrypted integer sums with a hidden threshold while limiting plaintext disclosure. It uses tree-based comparisons and path codes to determine the relationship with increasing certainty, while masking values against interval inference.
- Scenarios: The server tests encrypted integer pairs whose sum does not exceed a hidden threshold without learning the plaintext values.Only greater-than, equality, or less-than relationships may be disclosed; local downloading would defeat cloud offloading.
- Scenarios: Homomorphic encryption alone cannot determine the relationship between encrypted x + y and θ because its probabilistic ciphertexts prevent direct comparison.
- Main Idea: The protocol encodes integers with order-revealing encryption and addresses the lack of simultaneous order-comparison and homomorphic properties.
- Main Idea: Iterative comparisons against θ/2, θ/4, and 3θ/4 determine the relationship between x + y and θ with increasing probability.Mixed half-threshold cases are refined by recursively subdividing the threshold interval.
- Main Idea: The cost constraint tree represents threshold-related values as nodes, while root-to-leaf paths produce comparison codes for encrypted integers.For example, 5θ/16 traverses E(θ/2), E(θ/4), and E(3θ/8) to produce path code 010.
- Details of Protocol: Path-code sums classify x + y as greater than or no greater than θ when they overflow or fall at most 2^β−2, otherwise returning uncertainty.The procedure separately traverses the tree for E(x) and E(y), then compares the resulting codes.
- Details of Protocol: Each additional tree step halves uncertainty, and with depth 6 the probability of certainty reaches about 0.9844.The path-code length is β.
- Details of Protocol: Randomly applying a secret large integer φ to x, y, and θ enlarges the plaintext and ciphertext spaces to reduce inference of real values from order information.The user keeps φ and θ secret, while β is user-determined and was set to 6 in the implementation.
VII. COMPLEXITY AND SECURITY ANALYSES
Connor’s complexity analysis covers setup, query-token generation, and cloud-side CSD querying, while its security analysis characterizes leakage and proves security under adaptive chosen-query attacks.
- Complexity: Connor’s setup algorithm has time and space complexity O(nµ), where µ is the total sketch size.The dominant setup cost is encrypting the plain 2HCLI.
- Complexity: Query-token generation has time and space complexity O(2^dθ), driven by constructing the cost-constraint tree.Here, dθ is the tree depth associated with constraint θ.
- Complexity: Cloud-side CSD querying has time complexity O(ηdθ) and space complexity O(η + 2^dθ).η denotes the maximum sketch size per vertex.
- Security: Connor’s leakage functions include query-pattern, sketch-pattern, and cost-pattern leakage over encrypted 2HCLI structures.The leakage definitions describe repeated queries, queried sketches and overlaps, cost ordering, and interval information.
- Security: The scheme uses amplification for costs and SWHE encryption for distances to protect their real values from the server.XOR operations also make sketch entities indistinguishable, preventing setup leakage of pairwise cost order and cost-constraint order.
- Security: Under secure cryptographic primitives, Connor is secure against adaptive chosen-query attacks with respect to its defined leakage functions.The proof establishes indistinguishability between real and ideal games, with distinguishing advantage bounded by a negligible function.
VIII. PERFORMANCE EVALUATION
The performance evaluation assesses the proposed graph encryption scheme through experiments on real-world datasets.
- The evaluation uses experiments to assess the proposed graph encryption scheme.
- The experiments are conducted on real-world datasets.
- The section evaluates the scheme empirically rather than through analysis alone.
A. Setup
The setup uses directed graph datasets, generated edge attributes, randomly sampled queries, and a fixed approximation ratio for experimental comparison.
- Experimental setup: The implementation uses C++, 128-bit security, OpenSSL primitives, and a desktop with a 2.6 GHz Intel Xeon processor and 8 GB RAM.
- Datasets: The experiments use publicly available directed graph datasets, with random distance and cost values from 1 to 100 for unweighted graphs.Subsets of soc-Epinions1 and Email-EuAll are selected to make index construction feasible.
- Methods to compare: Connor is compared with a state-of-the-art plaintext CSD method, using 2HCLI built directly over the original graph.This comparison improves query efficiency but increases index-construction complexity for the plaintext implementation.
- Query workload: Each dataset receives 200 randomly generated queries with randomly selected origins and destinations.The constraint construction uses lower and upper path-cost bounds to vary query feasibility.
- Query workload: The approximation ratio is fixed at α = 1.5 for all queries to balance query accuracy and system efficiency.
B. Evaluation of Secure 2HCLI and Query Token
The evaluation measures encrypted-index construction and query-token generation, finding substantially larger encrypted indexes but moderate token sizes for general constraint-tree depths.
- Index construction: Index construction consists of building the plain 2HCLI and encrypting that index; the plain output serves as the unencrypted baseline.
- Index construction: Graph topology causes substantial variation in index size and construction time, with denser graphs tending to incur higher construction costs.
- Index construction: Encrypted indexes are roughly 6× larger than corresponding plain indexes, while their construction time is only slightly higher.Improving construction efficiency therefore focuses on accelerating plain 2HCLI construction.
- Query-token generation: A query token has size 16×(2^dθ+3) bytes and is usually below 1 KB because dθ is relatively small.
- Query-token generation: Query-token generation time increases significantly with dθ but remains moderate when dθ ≤ 6.
C. Evaluation of Query Efficiency and Accuracy
Connor’s query efficiency and accuracy vary with the cost-tree depth and graph index size. Larger depths improve constraint filtering and can reduce query time, while encrypted queries remain slower than plain queries.
- Query Efficiency: Increasing dθ from 1 to 6 decreases query time for each evaluated dataset.A larger tree filters more distance pairs before the dominant SWHE-based distance computation.
- Query Efficiency: Encrypted 2HCLI queries take longer than plain 2HCLI queries because ciphertext cost filtering and distance computation are time-consuming.Differences among datasets also follow the size of their graph indexes.
- Query Accuracy: Precision increases with dθ, exceeding 94% for every dataset when dθ = 6.Deeper cost trees detect constraint violations with higher probability.
- Query Accuracy: The deviation rate ξ compares Connor’s returned result with the corresponding plain-graph result, with values closer to 1 indicating greater accuracy.The evaluation uses CDFs of ξ to assess final query-result accuracy.