Source-linked AI summary
Shrinkwrap: Differentially-Private Query Processing in Private Data Federations
Johes Bater, Xi He, William Ehrich, Ashwin Machanavajjhala, Jennie Rogers
TL;DR
Private data federations use secure computation to protect query processing, but exhaustive padding of intermediate results makes complex SQL costly. Shrinkwrap applies computational differential privacy to reduce that padding while preserving privacy guarantees. It significantly improves federation performance, with tunable parameters supporting trade-offs among privacy, accuracy, and performance.
Problem
Secure query processing pads intermediate results to their maximum possible sizes to hide data-dependent sizes, creating substantial overhead as query operators cascade.
Source: §3 · pp. 3–4Method
Shrinkwrap applies computational differential privacy during SQL execution to reduce padded intermediate cardinalities and allocates privacy budgets across query operators.
Source: §1 · p. 2, §4.1 · p. 4Results
Shrinkwrap significantly improves private-data-federation performance while reducing intermediate result sizes.
Source: §9 · p. 12Takeaways & Limitations
Tunable privacy parameters let the system trade among privacy, accuracy, and query performance.
Source: §1 · p. 2For multiple queries, privacy loss is analyzed using sequential composition; tighter composition bounds and workload-level privacy-budget allocation are left for future work.
Source: §4.4 · p. 6
Abstract
from arXiv · showhide
A private data federation is a set of autonomous databases that share a unified query interface offering in-situ evaluation of SQL queries over the union of the sensitive data of its members. Owing to privacy concerns, these systems do not have a trusted data collector that can see all their data and their member databases cannot learn about individual records of other engines. Federations currently achieve this goal by evaluating queries obliviously using secure multiparty computation. This hides the intermediate result cardinality of each query operator by exhaustively padding it. With cascades of such operators, this padding accumulates to a blow-up in the output size of each operator and a proportional loss in query performance. Hence, existing private data federations do not scale well to complex SQL queries over large datasets. We introduce Shrinkwrap, a private data federation that offers data owners a differentially private view of the data held by others to improve their performance over oblivious query processing. Shrinkwrap uses computational differential privacy to minimize the padding of intermediate query results, achieving up to 35X performance improvement over oblivious query processing. When the query needs differentially private output, Shrinkwrap provides a trade-off between result accuracy and query evaluation performance.
1. INTRODUCTION
Shrinkwrap combines differential privacy with secure computation to reduce padding in private federated queries, aiming to improve performance while preserving provable privacy guarantees. It addresses the severe overhead of existing secure query processing and adds mechanisms for balancing privacy, accuracy, and performance.
1. INTRODUCTION
- Privacy breaches have made organizations hesitant to share data, leaving information siloed and its potential analytical value unrealized.Source: §1 · p. 1
- A private data federation lets owners of horizontally partitioned tables run SQL over their union without a trusted curator, while secure computation protects intermediate results from revealing unauthorized information.The stated privacy goal includes preventing one owner from reconstructing another owner's database from intermediate result sizes.Source: §1 · p. 1
- Secure private-federation systems run 4–6 orders of magnitude slower than non-private systems, with worst-case padding making complex SQL queries with multiple joins untenable.Padding hides intermediate sizes and makes execution run at worst-case sizes.Source: §1 · p. 1
- Alternative approaches leave gaps: TEEs require specialized hardware and have reported vulnerabilities, while homomorphic-encryption systems can leak data statistics and memory-access patterns.The passage cites the relevant prior work as, [28],, and.Source: §1 · pp. 1–2
- Shrinkwrap replaces exhaustive intermediate-result padding with oblivious dummy-tuple elimination guided by tunable privacy parameters, producing differentially private cardinality estimates close to the true sizes.The paper also describes this as computational differential privacy that selectively reveals statistical information within provable privacy bounds.Source: §1 · p. 2
- The contributions include a computational differential privacy mechanism for relational operators, an optimizer for allocating privacy budgets across query execution, and a protocol-agnostic cost model for cascading secure computation overhead.The system exposes tunable parameters for the privacy, accuracy, and performance trade-off.Source: §1 · p. 2
2. PRIVATE DATA FEDERATION
A private data federation lets autonomous databases answer SQL queries over their combined data without revealing unauthorized information. Its privacy goals distinguish data-owner protection from trusted and untrusted client access, using secure computation and differential privacy under stated assumptions.
2. PRIVATE DATA FEDERATION
- A federation combines autonomous databases under a shared schema and SQL interface, with a coordinator planning queries and owners returning secret-shared results.The data owners hold horizontal partitions of the tables.Source: §2 · p. 2
2.1 Privacy Goals and Assumptions
- Data owners must not reconstruct others’ data from intermediate results; trusted clients may receive true answers, while untrusted clients receive differentially private views.The coordinator has the same privacy requirements as the client.Source: §2.1 · p. 2
- The guarantees assume computationally bounded, semi-honest parties and specify different collusion boundaries for true-answer and untrusted-client policies.For true answers, the client/coordinator is assumed not to collude with data owners; untrusted clients may collude with all but one owner.Source: §2.1 · pp. 2–3
2.2 Security Primitives
- Secure computation lets multiple parties compute functions on distributed data while protecting inputs under the paper’s semi-honest security definition.Its formal definition compares protocol views and outputs with a simulator’s behavior.Source: §2.2 · p. 3
- Sequential composition bounds the combined privacy loss of independent differentially private releases by summing their ϵ and δ parameters.The paper uses sequential composition as a general, easy-to-compute bound rather than tighter advanced composition.Source: §2.2 · p. 3
3. PROBLEM STATEMENT
Secure computation protects query inputs but makes private federation queries slow because execution traces and intermediate result sizes can reveal data. Exhaustive padding hides those sizes, yet cascaded operators amplify the computation; the paper frames reducing this overhead with differential privacy as its central problem.
3. PROBLEM STATEMENT
- Secure-computation federations run 4–6 orders of magnitude slower than non-private systems, while hardware- and encryption-based alternatives lack formal privacy guarantees.The alternatives cited include secure hardware and property-preserving encryption.Source: §3 · p. 3
- Because execution time and intermediate array sizes can reveal data, federations pad outputs to maximum sizes and make execution independent of inputs.Secure computation also requires worst-case running time, oblivious execution traces, and cryptographic-key operations that scale with program complexity.Source: §3 · p. 3
- A filter with 10^-3 selectivity incurs 1000× overhead, while the example’s successive joins produce a 10^9× computation overhead under exhaustive padding.The figure’s operator tree ends with a distinct operator, and padding growth compounds across the cascade.Source: Figure 2 · p. 4, §3 · p. 4
- The stated goals are to use differentially private leakage, build lower-overhead private mechanisms for individual operators, and optimally allocate privacy budgets across query operators.The proposed budget allocation is for a sequence of operators executed during a query.Source: §3 · p. 4
4. SHRINKWRAP
Shrinkwrap reduces intermediate-result padding by privately resizing secure arrays during SQL execution, allocating privacy budget across operators while preserving the specified privacy guarantees. Its resizing mechanism uses noisy cardinalities, and the analysis covers both query outputs and privacy loss across multiple queries.
4.1 End-to-end Algorithm
- The coordinator allocates a performance privacy budget across operators; larger per-operator budgets produce tighter intermediate-size estimates, and any split satisfying Equation 3 satisfies privacy.For noisy query outputs, the budget remaining after intermediate-cardinality protection is spent on the output mechanism.Source: §4.1 · p. 4
- Shrinkwrap securely computes each operator’s result, then resizes its exhaustively padded array before that result feeds later operators.The final result is returned directly under the true-answer policy, or processed with the remaining privacy budget under the noisy-answer policy.Source: §4.1 · p. 4, §4.2 · p. 5
4.2 DP Resizing Mechanism
- Resize uses truncated-Laplace noise to produce an overestimate of an operator’s cardinality, then sorts dummy tuples to the end and copies the first noisy-cardinality tuples.The mechanism adds nonnegative integer noise; its tail condition Pr[η < ∆c] ≤ δ supports the privacy guarantee.Source: §4.2 · p. 5
- Intermediate-cardinality sensitivity is computed bottom-up from operator stability: unary filters have stability 1, while joins use maximum input multiplicity and can compound sensitivity.In the example, two joins with multiplicity m yield sensitivity m², which remains unchanged through DISTINCT.Source: §4.2 · p. 6
4.3 Overall Privacy Analysis
- Theorem 3 states that owners receive a (ϵ, δ)-computationally differentially private view; clients learn nothing else with true answers or receive a (ϵ, δ)-private view with noisy answers.The privacy analysis composes the per-operator cardinality releases and, for noisy outputs, the additional output privacy loss.Source: §4.3 · p. 6
4.4 Multiple SQL Queries
- Across multiple queries, Shrinkwrap analyzes privacy loss using sequential composition; advanced composition and workload-wide budget optimization are left as future adaptations.The paper describes those approaches as orthogonal to its work.Source: §4.4 · p. 6
5. PERFORMANCE OPTIMIZATION
The section frames privacy-budget allocation as minimizing total query runtime subject to a query-wide privacy budget. It contrasts eager and uniform baselines with a cost-model-based convex optimization strategy.
5. PERFORMANCE OPTIMIZATION
- The allocation problem assigns privacy parameters to query operators to minimize overall runtime while keeping the summed privacy budget within its query-wide limits.The stated constraints also require nonnegative per-operator parameters.Source: §5 · p. 6
5.1 Baseline Privacy Budget Allocation
- Eager spends the full budget on the first operator, while uniform divides it equally; both can miss gains at operators with larger output effects.Eager can benefit later operators through smaller intermediate results, whereas uniform gives every operator some budget.Source: §5.1 · p. 7
5.2 Optimal Privacy Budget Allocation
- Shrinkwrap uses convex optimization with this cost model to determine the budget split that minimizes the objective, then evaluates it against the baseline strategies.The model estimates private output cardinalities using naive reduction factors and expected truncated-Laplace noise.Source: §5.2 · p. 7
- The cost model combines secure computation at each operator with sorting and copying costs for intermediate arrays resized by Shrinkwrap.Exhaustively padded array size depends on input sizes, while the copied size depends on the noisy output estimate.Source: §5.2 · p. 7
6. PROTOCOL IMPLEMENTATION
Shrinkwrap adapts secure query processing to minimize padded intermediate results using a cost model and privacy-budget optimization. Its protocol-agnostic design supports RAM- and circuit-based execution, while its current multi-party construction is inefficient.
6.1 RAM Model
- The RAM model estimates operator costs from secure-array reads and writes, and Shrinkwrap reduces intermediate ORAM sizes by obliviously removing excess dummy tuples.The implementation uses ObliVM with SMCQL, while other ORAM implementations are compatible if their I/O costs can be modeled.Source: §6.1 · p. 8
6.2 Circuit Model
- The circuit model estimates costs from input and output sizes, gate count, circuit depth, and encoding or decoding costs.With EMP, Shrinkwrap removes dummy tuples directly from the circuit rather than modifying ORAM.Source: §6.2 · p. 8
6. PROTOCOL IMPLEMENTATION
- Shrinkwrap uses a cost model to estimate padding costs and optimize privacy-budget allocation across both RAM- and circuit-based protocols.The design minimizes intermediate padding while remaining compatible with protocols whose costs can be modeled.Source: §6.2 · p. 8
6.3 M-Party Support
- The system supports any number of data owners by decomposing work into two-party computations, but the described construction requires m^2 secure computations and is inefficient.The experiments use two-party protocols; improving performance for multiple parties is left for future work.Source: §6.3 · p. 8
7. RESULTS
Experiments on medical and synthetic workloads evaluate Shrinkwrap across query performance, privacy and accuracy trade-offs, budget strategies, operator costs, and scaling. The strongest end-to-end gains occur for join-heavy queries, while performance improvements trade off against output accuracy when final answers are differentially private.
7.1 Experimental Setup
- The evaluation uses three clinical-protocol queries on 500,000 patient records and synthetic data scaled to 750 GB.The medical dataset covers one year from two Chicago-area hospitals; experiments average three runs and generally report true-output runtimes.Source: §7.1 · p. 9, Table 3 · p. 9
7.2 End-to-end Performance
- 33x under the RAM model and 35x under the circuit model: Shrinkwrap improves 3-Join performance over fully padded execution, with the largest gains on join-heavy queries.Dosage Study improves by close to 5x under RAM; Aspirin Count improves by an order of magnitude under RAM and 2x under circuit execution.Source: Figure 5 · p. 9, §7.2 · p. 10
7.3 Privacy, Performance, and Accuracy
- A 0.36% additive output-noise allowance yields a 100x performance improvement for 3-Join, while spending more privacy budget on execution increases final-answer noise.This trade-off is measured with a fixed total privacy budget of ϵ = 1.5 and differentially private final answers.Source: §7.3 · p. 10, Figure 6 · p. 10
7.4 Evaluating Budget Splitting Strategies
- All three budget-splitting strategies improve performance by 3x to 33x, and the optimal strategy performs best for Aspirin Count and 3-Join.Eager beats uniform for Aspirin Count; uniform beats eager for 3-Join, while optimal combines privacy across operators with greater allocation to earlier ones.Source: §7.4 · pp. 10–11, Figure 7 · p. 10
7.5 Operator Breakdown
- In Aspirin Count, Shrinkwrap first benefits Join D after Join M; all three strategies reduce DISTINCT runtime by about an order of magnitude.Uniform may not shrink the first join's cardinality enough to beat full padding, whereas eager reduces it by an order of magnitude; the optimal strategy gives the best overall performance.Source: §7.5 · p. 11, Figure 8 · p. 11
7.6 Join Scale Up
- As join count increases, fully padded intermediate cardinalities grow from n to n^2 to n^3, while Shrinkwrap reduces join outputs and remains orders of magnitude faster overall.The experiments measure the immediate parent operator's runtime and show that execution time still grows significantly with join count.Source: §7.6 · p. 11, Figure 9 · p. 12
7.7 Data Size Scale Up
- With synthetic data scaled to 750 GB, Shrinkwrap continues to improve execution, and its performance improvement grows with data size.The experiment uses EMP and the Aspirin Count reference query.Source: §7.7 · p. 12, Figure 10 · p. 12
8. RELATED WORK
Related work spans several approaches to private query processing, including differential privacy, secure hardware, encryption, and cloud computation. Shrinkwrap extends privacy-performance trade-offs to a broader set of SQL queries in private data federations.
Differential privacy
- PINQ introduced differential privacy for databases with budget tracking and sensitivity analysis; Shrinkwrap applies its privacy calculus to private data federations.DJoin supports selected SQL operators with noisy results, whereas Shrinkwrap uses noisy cardinalities to improve performance and supports a larger operator set.Source: §8 · p. 12
Privacy-performance trade-offs
- Prior work applies computational differential privacy to joins and trades privacy for performance in boolean queries; Shrinkwrap extends that trade-off to broader SQL queries.It also incorporates the precision, provability, and performance approach described for private record linkage.Source: §8 · p. 12
Other private query systems
- Opaque and Hermetic use secure enclaves with constant-cost I/O, so their cost models do not capture Shrinkwrap's variable-cost I/O.Other approaches discussed include homomorphic encryption, TEEs, differential privacy, and cloud computation.Source: §8 · p. 12
9. CONCLUSIONS AND FUTURE WORK
The paper concludes that Shrinkwrap improves private data federation performance through computational differential privacy, intermediate-size reduction, and cost-aware privacy-budget optimization. Future work targets more efficient secure arrays, cross-query budget optimization, and additional protocols and cryptographic primitives.
Conclusions
- Shrinkwrap combines computational differential privacy, reduced intermediate sizes, and a cost model with budget optimization to improve private federation performance.The system is protocol-agnostic and was evaluated using real-world medical data.Source: §9 · p. 12
Future Work
- Future work includes faster secure-array algorithms, privacy-budget optimization across multiple queries, and support for additional secure-computation protocols and cryptographic primitives.Source: §9 · p. 12