Shrinkwrap: Efficient SQL Query Processing in
Differentially Private Data Federations
Johes Bater

Xi HeWilliam Ehrich

Northwestern University

University of Waterloo

Northwestern University

johes@u.northwestern.edu
xi.he@uwaterloo.ca
wdehrich@gmail.com
Ashwin Machanavajjhala
Jennie Rogers
Duke University

Northwestern University

ashwin@cs.duke.edu

jennie@northwestern.edu

ABSTRACTattention. Data breaches litter the news headlines, creating fear and a hesitance to share data, even among trusted
collaborators. Without data sharing, information becomessiloed and enormous potential analytical value is lost.
Recent work in databases and cryptography attempts tosolve the data sharing problem by introducing the private
data federation [4]. A private data federation consists ofa set of data owners who support a common relational
database schema. Each party holds a horizontal partition(i.e., a subset of rows) of each table in the database. A
private data federation provides a SQL query interface toanalysts (clients) over the union of the records held by thedata owners. Query evaluation is performed securely frommultiple data owners without revealing unauthorized information to any party involved in the query and without theassistance of a trusted data curator.
A private data federation must provably ensure the following guarantee: a data owner should not be able to reconstruct the database (or a part of it) held by other data
owners based on the intermediate result sizes of the query
evaluation. One way to achieve this without a trusted data
curator is to use secure computation protocols, which provide a strong privacy guarantee that intermediate results
leak no information about their inputs.
Current implementations of private data federations thatuse secure computation have a performance problem: stateof-the-art systems have slowdowns of 4–6 orders of magnitude over non-private data federations [4, 56]. This slowdown comes from the secure computation protocols used byprivate data federations to securely evaluate SQL queries
without the need of a trusted third party. A query is executed as a directed acyclic graph of database operators.
Each operator takes one or two inputs, applies a function,and outputs its result to the next operator. In a typical(distributed) database engine, the execution time needed tocompute each intermediate result and the size of that result
leaks information about the underlying data to curious data
owners participating in the secure computation. To prevent
this leakage, private data federations insert dummy tuples
to pad intermediate results to their maximum possible size,
thereby ensuring that execution time is independent of the
input data. With secure evaluation, query execution runsin the worst-case, drastically increasing computation costs
as intermediate result sizes grow. While performance is reasonable for simple queries and small workloads, performanceis untenable for complex SQL queries with multiple joins.

A private data federation is a set of autonomous databasesthat 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 thisgoal 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 thatoffers 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 a 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.
PVLDB Reference Format:
Johes Bater, Xi He, Willi Ehrich, Ashwin Machanavajjhala, Jennie Rogers. Shrinkwrap: Differentially-Private Query Processingin Private Data Federations. PVLDB, 12(3): 307-320, 2018.
DOI: https://doi.org/10.14778/3291264.3291274

1.

INTRODUCTION

The storage and analysis of data has seen dramatic growth
in recent years. Organizations have never valued data more
highly. Unfortunately, this value has attracted unwantedThis work is licensed under the Creative Commons AttributionNonCommercial-NoDerivatives 4.0 International License. To view a copyof this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For
any use beyond those covered by this license, obtain permission by emailing
info@vldb.org. Copyright is held by the owner/author(s). Publication rights
licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 12, No. 3
ISSN 2150-8097.
DOI: https://doi.org/10.14778/3291264.3291274

307

Several approaches attempt to solve this performance problem, but they fail to provably bound the information leaked
to a data owner. One line of research uses Trusted Execution Environments (TEEs) that evaluate relational operators within an on-chip secure hardware enclave [54, 56].
TEEs efficiently protect query execution, but they require
specialized hardware from chip manufacturers. Moreover,current TEE implementations from both Intel and AMD
do not adequately obscure computation, allowing observers
to obtain supposedly secure data through widely publicizedhardware vulnerabilities [9, 17, 28, 31, 49]. Another approach selectively applies homomorphic encryption to evaluate relational operators in query trees, while keeping the underlying tuples encrypted throughout the computation (e.g.,
CryptDB [45]). While this system improves performance, itleaks too much information about the data, such as statistics
and memory access patterns, allowing a curious observer todeduce information about the true values of encrypted tuples [15, 26, 39, 7].
In this work, we bridge the gap between provable securesystems with untenable performance and practical systems
with no provable guarantees on leakage using differential
privacy [14]. Differential privacy is a state-of-the-art technique to ensure privacy, and provides a provable guaranteethat one can not reconstruct records in a database basedon outputs of a differentially private algorithm. Differentially private algorithms, nevertheless, permit approximate
aggregate statistics about the dataset to be revealed.
We present Shrinkwrap, a system that improves private
data federation performance by carefully relaxing the privacy guaranteed for data owners in terms of differential privacy. Instead of exhaustively padding intermediate results
to their worst-case sizes, Shrinkwrap obliviously eliminates
dummy tuples according to tunable privacy parameters, reducing each intermediate cardinality to a new, differentiallyprivate value. The differentially private intermediate result sizes are close to the true sizes, and thus, Shrinkwrap
achieves practical query performance.
To the best of our knowledge, Shrinkwrap is the first system for private data sharing that combines differential privacy with secure computation for query performance optimization. The main technical contributions in this work are:
• A query processing engine that offers controlled information leakage with differential privacy guarantees to speed
up private data federation query processing and provides
tunable privacy parameters to control the trade-off between privacy, accuracy, and performance

Private Data
Owner

End User
SQL
query qoutput of q
over all DBs
secure query plan q

Query
Coordinator secret shares of q’s

output (1/data owner)

Secure Computation

Figure 1: Private data federation architecture
Section 6 describes how we implement specific secure computation protocols on top of Shrinkwrap’s protocol agnostic
design. We experimentally evaluate our system implementation over real-world medical data in Section 7. We conclude
with a survey of related work and future directions.

2.

PRIVATE DATA FEDERATIONIn this section, we formally define a private data federation (PDF), describe privacy goals and assumptions, anddefine two security primitives – secure computation and differential privacy.
A private data federation is a collection of autonomous
databases that share a unified query interface for offering insitu evaluation of SQL queries over the union of the sensitive
data of its members without revealing unauthorized information to any party involved in the query. A private data
federation has three types of parties: 1) two or more data
owners DO1 , . . . , DOm that hold private data D1 , . . . , Dm
respectively, and where all Di share a public schema of k relations (R1 , . . . , Rk ); 2) a query coordinator that plans andorchestrates SQL queries q on the data of the data owners;and 3) a client that writes SQL statements to the query coordinator. The set of private data D̄ = (D1 , . . . , Dm ) ownedby the data owners is a horizontal partition of every tablein the total data set D.
As shown in Figure 1, the client first passes an SQL statement q(·) to the query coordinator, who compiles the query
into an optimized secure query plan to be executed by eachdata owner. Once the data owners finish execution, theyeach pass their secret share of the output to the query coordinator, who assembles and returns the result to the client.

2.1

Privacy Goals and Assumptions

Table 1 summarizes the privacy goals for all parties involved in this process and the necessary assumptions required for achieving these goals.
Privacy Goals: Data owners require a privacy guaranteethat the other parties (data owners, query coordinator andthe client) are not able to reconstruct the private data theyhold based on intermediate results of the query execution.
In particular, we require data owners to have a differentiallyprivate view over the inputs of other data owners (formallydefined in Def. 2). We aim to support two policies for clients.
Clients may be trusted (output policy 1) and allowed tosee true answers to queries but must not learn any otherinformation about the private inputs held by data owners.
Clients may be untrusted (output policy 2), in which casethey only are permitted a differentially private view over the
inputs. The query coordinator is an extension of the clientand has the same privacy requirements.

• A computational differential privacy mechanism that securely executes relational operators, while minimizing intermediate result padding of operator outputs• A novel algorithm that optimally allocates, tracks, andapplies differential privacy across query execution• A protocol-agnostic cost model that approximates thelarge, and non-linear, computation overhead of securecomputation as it cascades up an operator tree
The rest of this paper is organized as follows. In Section 2 we define private data federations, outline our privacy
goals and formally define secure computation and differential privacy. Section 3 describes the problem addressed by
Shrinkwrap. Our end-to-end solution, Shrinkwrap, and its
privacy guarantees, is described in Section 4. We show how
to optimize the performance of Shrinkwrap in Section 5.

308

Table 1: Privacy Goals and Assumptions

Privacy Goal
for DOs
Privacy Goal
for Client
Client & DO
Assumption
DOs Colludes
with Client
Client Colludes
with some DOs

where negl(κ) refers to any function that is o(κ−c ), for all
constants c and OUTPUTΠ (D̄) denotes the output sequenceof all parities during the execution represented in VIEWΠ
I (D̄).

Client Sees
Client Sees
True Answers
Noisy Answers
Differentially private (DP) view overdata held by other DOs
Learns only
DP view overquery answer
data held by DOs

Various cryptographic protocols that enable secure computation have been studied [5, 10, 11, 18, 46, 33, 52, 55] andseveral are applicable to relational operators [4, 8, 50].
Differential Privacy (DP): Differential privacy [14] is anappealing choice to bound the information leakage on the individual records in the input while allowing multiple releasesof statistics about the data. This privacy notion is utilizedby numerous organizations, including the US Census Bureau [34], Google [16], and Uber [27]. Formally, differential
privacy is defined as follows.

Semi-honest & Computationally Bounded
Not allowed

AllowedNot allowed

AllowedAssumptions: To achieve the privacy goals presented above,a private data federation assumes that all parties are computationally bounded and work in the semi-honest setting.
Hence, the query coordinator honestly follows the protocols
and creates a secure plan to evaluate the query. All parties
faithfully execute the cryptographic protocol created by thequery coordinator, but may attempt to infer properties ofprivate inputs held by other parties by observing the query
instruction traces and data access patterns. The query coordinator is also assumed to be memory-less as it destroys
its contents after sending query results back to the client.
When the client sees the true answers (output policy 1), we
assume that the client is trusted to not collude with data
owners; otherwise, if the client shares the true answer witha data owner (or publishes the true answer), the data owner
who colludes with the client can use their own private data
and the true query answer to infer the input of the otherdata owners. Similarly, we assume the data owners do notshare their true input with the client; otherwise, the client
can infer the other data owners’ input and gain more information than just the query answer. When the client is
not trusted, we assume that the client may collude with (asmany as all but one) data owners. Our guarantees hold evenin that extreme case.

2.2

Definition 2 ((, δ)-Differential Privacy). A randomized mechanism f : D → R satisfies (, δ)-differential
privacy if for any pair of neighboring databases D, D0 ∈ Dsuch that D and D0 differ by adding or removing a row andany set O ⊆ R,
Pr[f (D) ∈ O] ≤ e Pr[f (D0 ) ∈ O] + δ.

The differential privacy guarantee degrades gracefully wheninvoked multiple times. In the simplest form, the overall privacy loss of multiple differentially private mechanisms canbe bounded with sequential composition [13].
Theorem 1 (Sequential Composition). If M1 andM2 are (1 , δ1 )-DP and (2 , δ2 )-DP algorithms that use independent randomness, then releasing the outputs M1 (D) andM2 (D) on database D satisfies (1 + 2 , δ1 + δ2 )-DP.
There exist advanced composition theorems that give tighter
bounds on privacy loss under certain conditions [14], but we
use sequential composition as defined above as it is generaland easy to compute.

3.

Secure Computation: To securely compute functions on
distributed data owned by multiple parties, secure computation primitives are required. Let f : Dm → Rm be afunctionality1 over D̄ = (D1 , . . . , Dm ) ∈ Dm , where fi (D̄)
denotes the i-th element of q(D̄). Let Π be an m-party
protocol for computing f and VIEWΠ
i (D̄) be the view of
the i-th party during an execution of Π on D̄. For I ={i1 , . . . , it } ⊆ [m], we let DI = (Di1 , . . . , Dit ), fI (D̄) =Π(qi1 (D̄), . . . , qit (D̄)), and VIEWΠ
I (D̄) = (I, VIEWi1 (D̄), . . . ,Π
VIEWi1 (D̄)). We define secure computation with respect tosemi-honest behavior [19] as follows.
Definition 1 (secure computation). We say an mparty protocol securely computes f : Dm → Rm if there exists a probabilistic polynomial-time algorithm denoted S andnegl(κ) such that for any non-uniform probabilistic polynomial adversary A and for every I ⊆ [m], every polynomialp(·), every sufficiently large κ ∈ N, every D̂ ∈ Dm of size at
most p(κ), it holds thatΠ
Pr[A(VIEWΠ
I (D̄), OUTPUT (D̄)) = 1]|
1

PROBLEM STATEMENTOur goal is to build a system that permits efficient query
evaluation on private data federations while achieving provable guarantees on the information disclosed to clients anddata owners. As discussed in Section 1, prior work is divided
into two classes: (i) systems that use secure computation toanswer queries, which give formal privacy guarantees but
suffer 4–6 orders of magnitude slowdowns compared to nonprivate data federations [4, 56], and (ii) systems that use
secure hardware [54, 56] or property preserving encryption[45], which are practical in terms of performance, but haveno formal guarantee on the privacy afforded to clients anddata owners.
While secure computation based solutions are attractive,
and there is much recent work in improving their efficiency [6,24, 25], secure computation solutions fundamentally limit
performance due to several factors: 1) a worst-case running
time is necessary to avoid leaking information from earlytermination; 2) computation must be oblivious, i.e., the program counters and the memory traces must be independentof the input; 3) cryptographic keys must be sent and computed on by data owners, the cost of which scales with thecomplexity of the program.
In particular, applying secure computation protocols to
execute SQL queries results in extremely slow performance.
A SQL query is a directed acyclic graph of database operators. Each operator in the tree takes an input, applies a

Security Primitives| Pr[A(S(I, DI , fI (D̄)), f (D̄)) = 1]−

(2)

(1)
≤ negl(κ),

Functionality f can be both deterministic or randomized

309

SELECT DISTINCT pid
FROM demographic de, diagnosis di
medication m
WHERE di.diag="hd" AND m.med = "aspirin"
AND di.code = m.code AND de.pid = m.pid

4.
DISTINCT[n ]./pid [n3 ]./code [n2 ]demographic

[n]

4.1
σdiag=hd[n]σmed=aspirin[n]diagnosis[n]medication[n]

SHRINKWRAPIn this section, we present the end-to-end algorithm ofShrinkwrap for answering a SQL query in a private data federation, the key differentially private mechanism for safely
revealing the intermediate cardinality of each operator, andthe overall privacy analysis of Shrinkwrap.

3

End-to-end Algorithm

At its core, Shrinkwrap is a system that applies differential
privacy throughout SQL query execution to reduce intermediate result sizes and improve performance. The private
data federation ingests a query q as a directed acyclic graph(DAG) of database operators Q = {o1 , . . . , ol }, following
the order of a bottom up tree traversal. The query coordinator decides the output policy based on the client type andassigns the privacy parameters (, δ) for the corresponding
privacy goals. To improve performance, a privacy budgetof (1→l , δ1→l ) will be spent on protecting intermediate cardinalities of the l operators. When the client is allowed tolearn the true query output (output policy 1), then 1→l = and δ1→l = δ; when the client is allowed to learn noisy
query answers from a differentially private mechanism, then
1→l <  and δ1→l < δ, where the remaining privacy budget( − 1→l , δ − δ1→l ) will be spent on the query output.
Algorithm 1 outlines the end-to-end execution of a SQL
query in Shrinkwrap. Inputs to the algorithm are the query
Q, the overall privacy parameters (, δ), the privacy budget
for improving the performance (1→l , δ1→l ), and the public information K, including the relational database schema
and the maximum possible input data size at each party.
First, the query coordinator allocates the privacy budget
for improving performance (1→l , δ1→l ) among the operators
in Q such that

Figure 2: Exhaustive padding of intermediate results in an
oblivious query evaluation
function, and outputs its result to the next operator. The
execution time needed to calculate each intermediate result
and the array size required to hold that result leaks information about the underlying data. To address this leakage,
private data federations must insert dummy tuples to padintermediate results to their maximum possible size and ensure that execution time is independent of the input data.
We demonstrate this property in the following example.
Example 1. Figure 2 shows a SQL query and its corresponding operator tree. Tuples flow from the source relations
through a filter operator, before entering two successive join
operators and ending at a distinct operator. To hide the selectivity of each operator, the private data federation pads
each intermediate result to its maximum value. At the filters, the results are padded as if no tuples were filtered out,
remaining at size n. This is a significant source of additional computation. If the selectivity of a filter is 10−3 , ourpadding gives a 1000× performance overhead. As the tuples flow into the first join, which now receives two inputs ofsize n, exhaustive padding produces an output of n2 tuples.
When this result passes through the next join, the result sizethat the distinct operator must process jumps to n3 . If weonce again assume a 10−3 selectivity at the joins, we now
see a 109 × computation overhead. Such a significant slowdown arises from the cumulative effect of protecting cascading operators. By exhaustively padding operator outputs, we
see ever-increasing intermediate result cardinalities and, asa function of that growth, ever-decreasing performance.

l
X
i=1

i = 1→l andlX

δi = δ1→l

(3)

i=1

where (i , δi ) is the privacy budget allocated to operator
oi . If i = δi = 0, then the operator is evaluated obliviously (without revealing the intermediate result size). Wheni , δi > 0, Shrinkwrap is allowed to reveal an overestimate of
the intermediate result size, with larger (i , δi ) values giving
tighter intermediate result estimates. The performance improvement of Shrinkwrap highly depends on how the budget
is split among the operators, but any budget split that satisfies Equation 3 satisfies privacy. We show several allocation
strategies in Section 5 and analyze them in the evaluation.
Next, the query coordinator compiles a secure query plan
to be executed by the data owners. The secure query plan
traverses the operators in Q. For each operator oi , data
owners compute secret shares of the true output using securecomputation over the federated database and the output ofother operators computed from D. We denote this securecomputation for oi by SM C(oi , D). The true outputs (ofsize ci ) are placed into a secure array Oi . The secure arrayis padded (with encrypted dummy values) so that its size
equals the maximum possible output size for operator oi .
Then, Shrinkwrap calls a (i , δi )-differentially private function Resize() to resize this secure array Oi to a smaller array
Si such that a subset of the (encrypted) dummy records are
removed. Resizing is described in Section 4.2. Once all theoperators are securely evaluated, if the output policy allows
release of true answers to the client (policy 1), the last secure

To tackle this fundamental performance challenge, we formalize our research problems as follows.
• Build a system that uses differentially private leakage ofintermediate results to speed up SQL query evaluation
while achieving all the privacy goals stated in Section 2.
• Given an SQL operator o and a privacy budget (, δ),design an (, δ)-differentially private mechanism that executes the operator with a smaller performance overhead
compared to fully oblivious computation.
• Given a sequence of operators Q = {o1 , . . . , ol }, design
an algorithm to optimally split the privacy budget (, δ)among these operators during query execution.
In the following sections, we present our system for efficient SQL query processing, starting with the differentiallyprivate mechanisms and overall privacy analysis used for operator evaluation (Section 4), and then our budget splitting
algorithm that optimizes performance (Section 5).

310Based on these inputs, the Resize() function runs a (i , δi )differentially private truncated Laplace mechanism (Def. 4)
to obtain a new, differentially private cardinality c̃i > ci forthe secure array. Next, this function sorts the exhaustively
padded secure array Oi obliviously such that all dummy
tuples are at the end of the array and then copies the firstc̃i tuples in the sorted array into a new secure array Si of
size c̃i . This new secure array Si of a smaller size than Oi
is used for the following computations.

Algorithm 1: End-to-end Shrinkwrap algorithm
Input: PDF query DAG with operators Q = {o1 , . . . , ol },the federated database D, public information K,
privacy parameters (, δ), privacy budget for
performance (1→l ≤ , δ1→l ≤ δ)
Output: Query output R//Computed on query coordinatorPP
P = {(1 , δ1 ), . . . , (l , δl )| li=1 i = 1→l , li=1 δi = δ1→l }← AssignBudget(1→l , δ1→l , Q, K) // (Sec. 5)//Computed on private data owners
for i ← 1 to l do
(Oi , ci ) ← SMC(oi , D) //with exhaustive padding
Si ← Resize(Oi ,ci ,i ,δi ,∆ci ) // DP resizing (Sec. 4.2)
end
if  = 1→l and δ = δ1→l thenSend query coordinator Sl //output policy 1
else
Query output budget 0 ← ( − 1→l ), δ0 ← (δ − δ1→l )Send query coordinator M (0 ,δ0 ) (Sl ) //output policy 2
end

Noise Generation: Shrinkwrap generates differentially private cardinalities by using a truncated Laplace mechanism.
Given an operator o, with a privacy budget (, δ) and thesensitivity parameter for the cardinality query ∆c, this mechanism computes a noisy cardinality for use in Algorithm 1.

Definition 4 (Truncated Laplace Mechanism).
Given a query c : D → N, the truncated Laplace mechanism
TLap(, δ, ∆c) adds a non-negative integer noise max(η, 0)
to the true query answer c(D), where η ∈ Z follows a distribution, denoted by L(, δ, ∆c) that has a probability density0/∆c,function Pr[η = x] = p · e−(/∆c)|x−η | , where p = ee/∆c −1+1//Computed on query coordinator
R ← Assemble(Sl )return R to client
function Resize(O, c, , δ, ∆c)c̃ ← c+TLap(, δ, ∆c) // perturb cardinality
O ← Sort(O) //obliviously sort dummy tuples to the end
S ← new SecureArray(O[1, . . . , c̃])return S/∆cη 0 = − ∆c·ln((e Theorem 2. The truncated Laplace mechanism satisfies(, δ)-differential privacy.
Proof. For any neighboring databases D1 , D2 , let c1 =c(D1 ) ≥ 0 and c2 = c(D2 ) ≥ 0. W.L.O.G. we consider
c2 ≥ c1 . It is easy to see that Pr[TLap(D1 ) ∈ (−∞, c1 )] = 0
and Pr[TLap(D2 ) ∈ (−∞, c2 )] = 0. By the noise property,2 )=o]| ≤ .
for any o ≥ c2 ≥ c1 , it is true that | ln Pr[TLap(DPr[TLap(D1 )=o]However, when the output o ∈ [c1 , c2 ), Pr[TLap(D2 ) =o] = 0, but the Pr[TLap(D2 ) = o] > 0, making the ratio of probabilities unbounded. Nevertheless, we can boundPr[TLap(D2 ) ∈ [c1 , c2 )] by δ as shown below.

DP Resizing Mechanism

For each operator oi , Shrinkwrap first computes the true
result using secure computation and places it into a exhaustively padded secure array Oi . For example, as shown in
Figure 3, a join operator with two inputs, each of size n,
will have a secure array Oi of size n2 . This is the exhaustive
padding case shown on the left side of the figure, with theprivate data federation inserting the materialized intermediate results into the secure array and padding those resultswith dummy tuples. The Resize() function takes in the exhaustively padded secure array Oi , the true cardinality ofthe output ci , the privacy parameters (i , δi ), and the sensitivity of the cardinality query at operator oi , denoted by∆ci . The cardinality query ci (D) returns the output of theoperator oi in the PDF query q. The sensitivity of a queryis defined as follows.

Dummy
Data

n2 = |R|･|S|

max{D,D 0 s.t. |D−D 0 |∪|D 0 −D|=1}

Dummy
Data

Exhaustive Padding

Definition 3 (Query Sensitivity). The sensitivity ofa function f : D → R∗ is the maximum difference in its output for any pairs of neighboring databases D and D0 ,
∆f =

+ ∆c.

This mechanism allows us to add non-negative integer noise
to the intermediate cardinality query which corresponding
to the number of the dummy records. The noise η drawn
from L(, δ, ∆c) satisfies that Pr[η < ∆c] ≤ δ, which enables
us to show the privacy guarantee of this mechanism.

array Sl will be directly returned to the query coordinator;
otherwise, the data owners jointly and securely compute a
differentially private mechanism on Sl with the remaining
privacy budget (0 =  − 1→l , δ0 = δ − δ1→l ), denoted by
M (0 ,δ0 ) (Sl ), and return the output of M (0 ,δ0 ) (Sl ) to thequery coordinator. For instance, one could use a Laplacemechanism to perturb count queries using a multiparty protocol for generating noise as in [38]. Finally, the query coordinator assembles the final secure array received from thedata owners Sl , decrypting the final result R and returning
it to the client.

4.2

+1)δ)

Real
Data

Real
Data

Without
Shrinkwrap

With
Shrinkwrap

Lap(𝜀,δ, Δc)
DP Noise|R⋈S|
True Cardinality

Figure 3: Effect of Shrinkwrap on Intermediate Result
Sizes When Joining Tables R and S

kf (D) − f (D0 )k1

311

Let O∗ = (−∞, c2 ). We can show that for any output set
O of query c(), we have
Pr[TLap(D1 ) ∈ O]
= Pr[TLap(D1 ) ∈ (O ∩ O∗ )] + Pr[TLap(D1 ) ∈ (O − O∗ )]≤ Pr[TLap(D1 ) ∈ [c1 , c2 )] + e Pr[TLap(D2 ) ∈ (O − O∗ )]= Pr[η1 < ∆c] + e Pr[TLap(D2 ) ∈ O]
= δ + e Pr[TLap(D2 ) ∈ O]

(4)

Hence, this mechanism satisfies (, δ)-DP.
Sensitivity Computation: In order to create our noisy
cardinalities using the truncated Laplace mechanism in Definition 4, we must determine the cardinality query sensitivity
at the output of each operator in the query tree. An intermediate result cardinality, ci , is the output size of the sub-query
tree rooted at operator oi . The sensitivity of ci depends on
the operators in its sub-query tree, and we compute this as
a function of the stability of operators in the sub-query tree.
The stability of an operator bounds the change in the output
with respect to the change in the input of the operator.

4.3

T (B)| ≤ s × |A

Theorem 3. Under the assumptions in Section 2, Algorithm 1 achieves the privacy goals: data owners have a (, δ)computational differentially private view over the input dataof other data owners; when true answers are returned to theclient, the client learns nothing else; when noisy answers are
returned the client, the client has a (, δ)-computational differentially private view over the input data of all the data
owners.

B|

For unary operators, such as SELECT, PROJECT, the stability usually equals one. For JOIN operators, a binary operators, the stability is equal to the maximum multiplicityof the input data. The sensitivity of the intermediate cardinality query ci can be recursively computed bottom up,
starting from a single change in the input of the leaf nodes.

Proof. (sketch) We prove that the view of data owners satisfies computational differential privacy [37, 48] byshowing that the view of any data owner is computationallyindistinguishable from its view in an ideal simulation that
outputs only the differentially private cardinalities of each
operator output.
Let Sim be a simulator that takes as input the horizontal
partitions held by the data owners (D1 , ..., Dm ), and outputs a vector Si⊥ for operator oi such that: (a) |Si⊥ | is drawn
from ci + TLap(), and (b) Si⊥ contains encryptions of 0 (ofthe appropriate arity). It is easy to see that a function computed by Sim satisfies (1→l , δ1→l )-DP: (a) at each operator,
the release of |Si⊥ | satisfies (i , δi )-DP, and (b) By sequential composition (Theorem 1) and Equation 3, releasing all
the cardinalities satisfies (1→l , δ1→l )-DP. When the output
itself is differentially private, there is an additional privacy
loss to data owners (since the client could release the output
to the data owners), but the overall algorithm still satisfies(, δ)-DP by sequential composition.
The real execution outputs secure arrays Si at each operator oi using secure computation. This ensures that the viewof a data owner in the real execution is computationallyindistinguishable from the execution of Sim, which satisfies (, δ)-DP. Thus, we can show that the view of any data
owner satisfies (, δ)-computational DP. The privacy guaranteed to the client and query coordinator can be analogously
argued.

Example 2. Given a query tree shown in Figure 4, thebottom two filter operators each have a stability of one, giving
a sensitivity (∆c) of 1 at that point. Next, the first join has
a stability of m for the maximum input multiplicity, which
increases the overall sensitivity to m. The following join operator also has a stability of m, which changes the sensitivity
to m2 . Finally, the DISTINCT operator has a stability of 1,
so the overall sensitivity remains m2 .
DISTINCT[∆c5 = m2 ]./pid[∆c4 = m2 ]./piddemographics[∆c3 = m]σdiag=hd

σmed=aspirin[∆c1 = 1][∆c2 = 1]

diagnosis

Overall Privacy Analysis

Given a PDF query DAG q with operators {o1 , . . . , ol } anda privacy parameter (, δ), Algorithm 1 achieves the privacy
goals stated in Section 2.

Definition 5 (Stability [36]). A transformation operator is s-stable if for any two input data sets A and B,|T (A)

Resize() function, Shrinkwrap takes an intermediate result
secure array and sorts it so that all dummy tuples are at
the end of the secure array. Next, Shrinkwrap cuts off theend of the original secure array and copies the rest into thenew, differentially-private sized secure array. Since the new
secure array has a size guaranteed to be larger than thetrue cardinality, we know that cutting off the end will only
remove dummy tuples. Thus, we avoid paying the full I/O
cost for each tuple. However, we do pay an O(n log(n))
cost for the initial sorting, as well as an O(n) cost for bulk
copying the tuples. This algorithm is an extension of the
one in [21] and variants of it are in [40, 41, 56].

medication

Figure 4: Sensitivity analysis for running example

4.4

Using these principles, Shrinkwrap calculates the sensitivity
for each operator in a query tree for use in Laplace noise
generation during query execution. More details can be seen
in PINQ [36] for computing the sensitivity of SQL queries.

Multiple SQL Queries

The privacy loss of Shrinkwrap due to answering multiple queries is analyzed using sequential composition (Theorem 1). There are two approaches to minimize privacy loss
across multiple queries: (i) applying advanced composition
theorems that give tighter bounds on privacy loss under certain conditions [14] or (ii) optimizing privacy budget allocation across the operators of a workload of predefined SQLSecure Array Operations: Each time Shrinkwrap adds
or removes tuples, it normally needs to pay an I/O cost
for accessing the secure array. We avoid paying the fullcost by carrying out a bulk unload and load. To start the312queries (e.g. using [35]). These two approaches are orthogonal to our work and adapting these ideas to the context of
secure computation is an interesting avenue for future work.

5.

PERFORMANCE OPTIMIZATION

A key technical challenge is to divide the privacy budget
for performance (1→l , δ1→l ) across the different operators
so the overall runtime of the query execution is minimized.
Problem 1. Given a privacy budget (1→l , δ1→l ), a PDF
query DAG q with operators Q = {o1 , . . . , ol }, and public information K which includes the sensitivities of the intermediate cardinality queries {∆c1 , . . . , ∆cl } and the schema information, compute the share (i , δi ) assigned to oi such that:
Pl(a) the assignment ensures privacy, i.e.,
i=1 i = 1→l ,and (b) the overall run time of the query is minimized.

5.1

Baseline Privacy Budget Allocation

We first consider two baseline strategies for allocating theprivacy budget to individual operators.
Eager: This approach allocates the entire budget (1→l , δ1→l )to the first operator in the query tree. In Figure 2, thisequates to minimizing the output cardinality of the filter on
diagnoses and executing the rest of the tree obliviously. A
benefit of this approach is that since the intermediate resultsof the first operator flow through the rest of the tree, every
operator will see the benefit of minimizing the output cardinality. On the other hand, in some trees, certain operators,
like joins, have an output-sized effect on the total query
performance. Not allocating any privacy budget to those
operators results in a missed optimization opportunity.
Uniform: The second approach splits the privacy budget(1→l , δ1→l ) uniformly across the query tree, resulting inequal privacy parameters for each operator. The benefit
here is that every single operator receives part of the budget, so we do not lose out on performance gains from any
operator. The drawback of the uniform approach, like the
one-time approach, is that some operators produce larger
effects, so by not allocating more of the budget to them, welose out on potential performance gains.

5.2

Optimal Privacy Budget Allocation

We design a third approach which uses an execution costmodel as an objective function and applies convex optimization to determine the optimal budget splitting strategy.
Cost Model: The execution cost of a query in Algorithm 1
mainly consists of (a) the cost for securely computing each
operator and (b) the I/O cost of handling each intermediate
result by Shrinkwrap. We model these costs as functions of
the corresponding input and output data sizes. The cost of
secure computation at operator oi is represented by a function costoi (Ni ), where Ni is the set of the cardinalities of
the input tables. The I/O cost of Shrinkwrap handling eachintermediate result of operator oi is mainly the cost to sortthe exhaustively padded array of size n0 and the cost of copying the array of size n to the new array of size n0 , denoted bycosts (n) and costc (n, n0 ) respectively. In particular, the sizeof the exhaustively padded array also depends on the sizesof the input tables, represented by a function oi (Ni ). Mostof the time, the size of the exhaustively padded array is the
product of the input table sizes. For example, if operator oi
takes one input table of size n1 , then oi (N = {n1 }) = n1 ;if operator oi takes two input tables of size n1 and n2 , thenoi (N = {n1 , n2 }) = n1 · n2 . The number of tuples n0 copied
to the new array depends on the noisy output size ni .
The input tables to an operator can be a mix of base tables and the intermediate output tables. Given a database ofk relations (R1 , . . . , Rk ), there will be an additional l number of intermediate output tables generated in a query treeof l operators. The public knowledge K contains the table sizes for the original tables, but the output cardinalitiesof the operators are unknown. In the private setting, wecannot use the true cardinality for the estimation. Instead,
Shrinkwrap uses the naive reduction factors from [47] toestimate the output cardinality of each operator, denotedby estimate(ci , K). The noise ηi added to the cardinality
depends on the noise distribution of the truncated Laplacemechanism and we use the expectation of the distribution
TLap(i , δi , ∆ci ) to model the noise. Putting this together,
the output cardinality ni at operator oi is estimated byestimate(ci , K) + E(TLap(i , δi , ∆ci )).
With this formulation, the cost of assigning privacy budget P = {(i , δi )|i = 1, . . . , l} to operators Q = {o1 , . . . , ol }in the query tree is modeled as
C(P, K) =lX

costoi (Ni )+costs (oi (Ni ))+costc (oi (Ni ), ni )

i=1

(5)
where ni = estimate(ci , K) + E(TLap(i , δi , ∆qi )).
Optimization: Using this cost model, we find the optimal
solution to the following problem as the budget allocation
strategy for Algorithm 1.
minP C(P ) s.t.

l
X
i=1

i ≤ 1→l ,lXδi ≤ δ1→l ,i=1

i , δi ≥ 0 ∀i = 1, . . . l(6)We show the detailed cost model including the unit costfunction costoi (Ni , ni ), costs (oi (Ni )), and costc (oi (Ni ), ni )for two different secure computation protocols in the next
section. Using a convex optimization solver, we determine
the optimal budget split that minimizes the cost objectivefunction. We evaluate how it performs against the baseline
approaches in Section 7.

6.

PROTOCOL IMPLEMENTATION

Shrinkwrap is a flexible computation layer that supports awide range of private data federations and database engines.
The only requirements are that the private data federation
process queries as operator trees and that the underlying
database engine supports SQL queries. Shrinkwrap implements a wide range of SQL operators for PDF queries, including selection, projection, aggregation, limit, and some
window aggregates. For joins, we handle equi-joins and crossproducts. At this time we do not support outer joins or set
operations. For output policy 2 where client sees noisy answers released from differentially private mechanisms, we
support aggregate queries like COUNT for the final operator.
The fundamental design pattern of secure computation
protocols is the circuit model, where functions are represented as circuits, i.e. a collection of topologically orderedgates. The benefit of this model is that by describing how
to securely compute a single gate, we can compose the computation across all gates to evaluate any circuit, simplifying

313

Table 2: Operator I/O cost

the design of the protocol. The downside is that circuits
are difficult for programmers to reason about. Instead, the
von Neumann-style Random Access Machine (RAM) model
handles the impedance mismatch between programmers andcircuits by creating data structures, such as ORAM, thatutilize circuit-based oblivious algorithms for I/O. With the
RAM model, programmers no longer have to write programs
as circuits. Instead, they can think of their data as residing
in secure arrays that can be plugged into their existing code.
The downside of the RAM model is that since the data structures are more general purpose, performance lags behind direct circuit model implementations of the same function. In
this work, we use Shrinkwrap with both RAM model andcircuit model protocols, providing a general framework thatcan easily add new protocols to the query executor.

6.1

Operator
FilterJoin
Aggregate
Aggregate, Group By
Window Aggregate
Distinct
Sort

costo (N = {n1 , n2 , . . .})n1 ∗ cread (n1 ) + n1 ∗ cwrite (n1 )n1 ∗ cread (n1 ) + n1 ∗ n2 ∗ cread (n2 )+n1 ∗ n2 ∗ cwrite (n1 ∗ n2 )n1 ∗ cread (n1 ) + cwrite (n1 )n1 ∗ cread (n1 ) + n1 ∗ cwrite (n1 )n1 ∗ cread (n1 ) + n1 ∗ cwrite (n1 )n1 ∗ cread (n1 ) + n1 ∗ cwrite (n1 )n1 ∗ log2 (n1 ) ∗ (cread (n1 ) + cwrite (n1 ))next operator. With Shrinkwrap, we resize the intermediate ORAM arrays by obliviously eliminating excess dummy
tuples, reducing the intermediate cardinalities of our results
and improving performance. Any ORAM implementation iscompatible with Shrinkwrap, as long as its I/O characteristics can be similarly defined as in Table 2.

RAM Model

6.2

When integrating a new protocol, we first create an operator cost model that captures the execution cost of each
operator. For a RAM based protocol, we model the cost of
secure computations costo (N) for commonly used relational
operators in Table 2, where N is the set of cardinalities of
input tables of operator o. The cost function considered inthis work focuses on the I/O cost of each relational operator
in terms of reads and writes from a secure array.
We let cread (n) and cwrite (n) be the unit cost for reading
and writing of a tuple from a secure array of size n respectively. Secure arrays protect their contents from attackers by
guaranteeing that all reads or writes access the same number of memory locations. Typically, the data structures will
shuffle either their entire contents or their access path oneach access, with different implementations providing performance ranging from O(log n) to O(n log2 (n)) per read or
write [2, 53]. This variable I/O cost guarantees that an observer cannot look at memory access time or program traces
to infer sensitive information.
Given the unit cost for reading and writing, we can represent the cost of secure computation for each operator as
the sum of reading cost and writing cost. For example, thecost function for a Filter operator costF ilter (N = {n1 }) is
the cost of reading n1 number of input records and writing n1 number of output records. For a Join operator over
two input tables, the cost function costJoin (N = {n1 , n2 })equals to the sum of n1 number of records reading from thefirst secure array of size n1 , (n1 ∗ n2 ) number of record reading from the second array of size n2 , and (n1 ∗ n2 ) numberof record writes, i.e. n1 ∗ cread (n1 ) + n1 ∗ n2 ∗ cread (n2 ) +n1 ∗ n2 ∗ cwrite (n1 ∗ n2 ). The other operators are modeled
similarly in Table 2. The cost function for copying froman array of size n to an array of size n0 can be modeled as
costc (n, n0 ) = n0 ∗ cread (n) + n0 ∗ cwrite (n0 ).
In this work, we use ObliVM [32] to implement our RAM
based relational operators, under a SMCQL [4] private data
federation design. We chose ObliVM due to its compiler,
which allows SMCQL to easily convert operators written as
C-style code into secure computation programs. However,Shrinkwrap can support more recent ORAM implementations such as DORAM [12] by summarizing their cost behavior as in Table 2 and using those operator costs in our costmodel. In SMCQL, private intermediate results are held insecure arrays, i.e., oblivious RAM (ORAM), and operators
are compiled as circuits that receive an ORAM as input,
evaluate the operator, and output the result ORAM to the

Circuit Model

Alternatively, if a private data federation uses a circuit
based protocol to express database operators, we can estimate the cost of an operator o, costo (N), with ngates gatesin its circuit, a maximum circuit depth of dcircuit , nin elements of input, and an output size of nout as:
costop (N) = cin ∗ nin + cg ∗ ngates + cd ∗ dcircuit + cout ∗ nout ,where cin and cout account for the encoding and decoding
costs needed for a given protocol, cg and cd account for thecosts due to the gate count and circuit P
depth respectively,
the number of input element is nin =nj ∈N nj and theQnumber of output element is nout = nj ∈N nj .
The generic nature of this model allows us to capture theperformance features of all circuit-based secure computation protocols. For example, in this work we utilize EMP
toolkit [51], a state of the art circuit protocol, in conjunction with Shrinkwrap. As EMP has not been used in private
data federations, we implemented EMP with SMCQL. Instead of compiling operators into individual circuits, EMP
compiles a SQL query into a single circuit, though it stillpads intermediate results within the circuit. In this setting,
we can still apply Shrinkwrap as we did in the RAM model,
where we minimize the padding according to our differential
privacy guarantees. Instead of modifying the ORAM, we
directly modify the circuit to eliminate dummy tuples.
For both our RAM model and our circuit model implementations, Shrinkwrap uses a cost model to estimate theexecution cost of intermediate result padding. With themodel, we can carry out our privacy budget optimization
and allocation as seen in Section 5. Shrinkwrap’s protocol
agnostic design allows it to optimize the performance of secure computation, regardless of the implementation.

6.3

M-Party Support

In this work, we implement Shrinkwrap using two party
secure computation protocols, meaning that we run our experiments over two data owners. However, Shrinkwrap supports additional data owners. By leveraging the associativity of our operators, we can convert all m party computations into a series of binary computations. For example,
assume we want to join to tables R and S, which are horizontally partitioned across 3 data owners as R1, R2, R3,
and S1, S2, S3. We can join across the 3 data owners as:(R1 ./ S1) ∪ (R1 ./ S2) ∪ (R3 ./ S3) ∪ (R2 ./ S1) ∪ (R2 ./S2) ∪ (R2 ./ S3) ∪ (R3 ./ S1) ∪ (R3 ./ S2) ∪ (R3 ./ S3). We

314

Table 3: HealthLNK query workload.
Name
Dosage Study
Comorbidity
AspirinCount
3-JoinQuery
SELECT DISTINCT d.pid FROM diagnoses d, medications m WHERE d.pid = m.pid AND medication = ’aspirin’ AND
icd9 = ’circulatory disorder’ AND dosage = ’325mg’
SELECT diag, COUNT(*) cnt FROM diagnoses WHERE pid ∈ cdiff cohort ∧ diag <> ’cdiff’ ORDER BY cnt DESC LIMIT 10;
SELECT COUNT(DISTINCT pid) FROM diagnosis d JOIN medication m on d.pid = m.pid
JOIN demographics demo on d.pid = demo.pid WHERE d.diag = ’heart disease’ AND m.med = ’aspirin’ AND d.time <= m.time;
SELECT COUNT(DISTINCT pid) FROM diagnosis d JOIN medication m on d.pid = m.pid
JOIN demographics demo on d.pid = demo.pid JOIN demographics demo2 ON d.pid = demo2.pid
WHERE d.diag = ’heart disease’ AND m.med = ’aspirin’ AND d.time <= m.time;

can execute this series of binary joins using two party securecomputation then union the results. With this construction,
we can scale Shrinkwrap out to any number of parties. However, this algorithm is not efficient due to naively carryingout m2 secure computation operations for every m parties
we compute over. We can use m party secure computation
protocols [3, 5, 20], which have fewer high-level operatorsand made large performance strides, but these protocols arestill expensive. We leave performance improvements in thissetting for future work.

7.

Query Workload: For our experiments, we chose three
representative queries based on clinical data research protocols [23, 43] and evaluate Shrinkwrap on this workload using de-identified medical records from the HealthLNK datarepository. We also generate synthetic versions of Aspirin
Count that contain additional join operators. We refer tothese queries by the number of join operators, e.g., 3-Joinfor 3 join operators. The queries are shown in Table 3.
Configuration: Shrinkwrap query processing runs on topof PostgreSQL 9.5 running on Ubuntu Linux. We evaluated our two-party prototype on 6 servers running in pairs.
The servers each have 64 GB of memory, 7200 RPM NLSAS hard drives, and are on a dedicated 10Gb/s network.
Our results report the average runtime of three runs per experiment. We implement Shrinkwrap under both the RAM
model (using ObliVM [33]) and circuit model (using EMP[51]).
For most experiments, we show results using the RAM model,
though corresponding circuit model results are similar. Unless otherwise specified, the results show the end-to-end runtime of a query with output policy 1, i.e., true results.

RESULTS

We now look at Shrinkwrap performance using both realworld and synthetic datasets and workloads. First, we cover
our experimental design and setup. Next, we evaluate theend to end performance of our system and show the performance vs privacy trade-off under both true and differentially private answer settings. Then, we look at how
Shrinkwrap performs at the operator level and the accuracyof our cost model, followed by a discussion of our budget
splitting strategies. Finally, we examine how Shrinkwrap
scales to larger datasets and more complex queries.

7.1

7.2

End-to-end Performance

In our first experiment, we look at the the end to end performance of Shrinkwrap compared to baseline private data
federation execution. For execution, we set  to 0.5, δ to
0.00005, and use the optimal budget splitting approach.
In Figure 5, we look at the overall performance of four
queries under Shrinkwrap for both RAM model and circuit
model secure computation. For Comorbidity, the execution
does not contain any join operators, meaning that there is no
explosion in intermediate result cardinality, so Shrinkwrap
provides fewer benefits. Dosage Study contains a join operator with a parent distinct operator. Applying differential privacy to the output of the join improves performanceby close to 5x under the RAM model, but sees fewer benefits under the circuit model. Aspirin Count contains two
joins and sees an order of magnitude improvement under theRAM model and a 2x improvement under the circuit model.
Finally, 3-Join has an enormous cardinality blow-up, allowing Shrinkwrap to improve its performance by 33x under theRAM model and 35x under the circuit model. In Section 7.6,
we examine this effect of join operators on performance. Although implementation in the circuit model outperforms theRAM model by an order of magnitude, Shrinkwrap gives
similar efficiency improvements in both systems.

Experimental Setup

For this work, we implemented Shrinkwrap on top of an
existing healthcare database federation that uses SMCQL [4].
This private data federation serves a group of hospitals thatwish to analyze the union of their electronic health record
systems for research while keeping individual tuples private.
A clinical data research network (CDRN) is a consortiumof healthcare sites that agree to share their data for research.
CDRN data providers wish to keep their data private. We
examine this work in the context of HealthLNK [44], a CDRN
for Chicago-area healthcare sites. This repository contains
records from seven Chicago-area healthcare institutions, eachwith their own member hospitals, from 2006 to 2012, totaling about 6 million records. The data set is selected from adiverse set of hospitals, including academic medical centers,
large county hospitals, and local community health centers.
Medical researchers working on HealthLNK develop SQL
queries and run them on data from a set of healthcare sites.
These researchers are the clients of the private data federation and the healthcare sites are the private data owners.
Dataset: We evaluate Shrinkwrap on medical data fromtwo Chicago area hospitals in the HealthLNK data repository [44] over one year of data. This dataset has 500,000
patient records, or 15 GB of data. For additional evaluation, we generate synthetic data up to 750 GB based on thissource medical data. To simplify our experiments, we use apublic patient registry for common diseases that maintains
a list of anonymized patient identifiers associated with these
conditions. We filter our query inputs using this registry.

7.3

Privacy, Performance, and Accuracy

We consider the performance vs privacy trade-off provided
by Shrinkwrap and evaluate the effect of the execution privacy budget on query performance. For this experiment, we
use the 3-Join query with the optimal budget splitting approach, fix the total privacy budget  = 1.5 and δ = 0.00005,

315

1000000

100000Without Shrinkwrap
With Shrinkwrap

10000
Execution Time (s)Average Execution Time (s)100000
10000
1000
100
10

1000
100
10
1

1
Comorbidity

Dosage Study Aspirin Count

03-Join

0.5

1

1.5

Privacy Budget, 𝜖 1→lQuery(a) RAM Model (ObliVM),(a) Performance v.s. 1→l .
100000Without Shrinkwrap
With Shrinkwrap

10000
Execution Time (s)Average Execution Time (s)

1000

100

10

1000
100
10

1
Comorbidity

Dosage Study

Aspirin Count

1

3-Join

0

Query

20
40
60
Final Result Error (# of tuples)80(b) Circuit Model (EMP)(b) Performance v.s. Error.

Figure 5: End-to-End Shrinkwrap Performance for All
Queries at  = 0.5, δ = .00005.

Figure 6: Privacy, Performance, and Accuracy Tradeoffs.
Computed using different levels of privacy budget for performance 1→l ∈ {0.1, ..., 1.5}. Executed using RAM Model,
3-Join,  = 1.5, δ = 0.00005.

and use output setting 2, i.e. differentially private final answers. We vary the privacy budget for performance δ1−lfrom 0.1 to 1.5 and fix δ1→l = δ. The remaining privacy
budget −1→l is spent on the query output using a Laplacemechanism.
In Figure 6a, we see the execution time as a function of
the privacy budget for performance (1→l ). As the privacy
budget for performance 1→l increases, the execution timedecreases. A lower budget means that more noise must bepresent in the intermediate result cardinalities, which translates to larger cardinalities and higher execution time variance. We know that I/O cost dominates the Shrinkwrap
cost model, so larger cardinalities mean more I/O accesses,
which causes lower performance.
In Figure 6b, we show the accuracy versus privacy tradeoff by varying the privacy budget for performance 1→l . We
report the execution time and the error introduced to thefinal query answer at various privacy budget for performance1→l < 1.5. Out of a total possible output size of 5500 tuples,the query output is 10/5500 = 0.18% of the total possible
output size. If we allow additive noise of 0.36% (20/5500),
we get a 100x performance improvement. Since the total
privacy  is fixed, the more we spend for performance (larger
1→l ), the less privacy budget we have at the output, i.e., as
our execution time improves, our output noise increases.

7.4

budget evenly across all the operators, eager inserts the entire budget at the first operator, and uses the Shrinkwrap
cost model, along with cardinality estimates, to identify an
optimal budget split. We also include an oracle approachthat shows the performance of Shrinkwrap if true cardinalities are used in the cost model to split the budget insteadof cardinality estimates. Note that oracle does not satisfy
differential privacy, but gives an upper bound on the best
performance achievable through privacy budgeting. For thisexperiment, we use the Aspirin Count and 3-Join queries
since they contain multiple operators where Shrinkwrap generates differentially-private cardinalities and set the privacy
parameters usable during execution to  = 0.5 and δ =.00005.
Figure 7 displays the relative speedup of all three approaches and the oracle for both queries over the baseline,
fully padded, private data federation execution. All three
Shrinkwrap approaches provide significant performance improvements, ranging from 3x to 33x. As expected, optimal performs best for both queries. We also see that eager
performs better for Aspirin Count, while uniform performs
better for 3-Join.
The benefits of minimized intermediate result cardinalities cascades as those results flow through the operator tree.
By using the entire budget on the first join operator in Aspirin Count, the eager approach maximizes the effect of theintermediate result cardinality reduction, and as a result,outperforms the uniform approach. However, for the 3-Join

Evaluating Budget Splitting Strategies

We first examine the relative performance of the threebudget splitting strategies introduced in Section 6: uniform, eager, and optimal. Recall that uniform splits the316Uniform

Eager

OptimalSpeedup over Full Padding

Baseline

Oracle

30
25x

25
20
15
8x
7x 8x

10
5
0

4x

3x

Aspirin Count

3-JoinUniform

Eager

OptimalOracle10000

33x 34x35

Average Execution Time (s)

40

1000

100

10

1
Join M.

Query

Join D.
Distinct
Query Operator

Total

Figure 7: Shrinkwrap execution speedup over baseline using different budget strategies. Executed using RAM model,
 = 0.5, δ = .00005

Figure 8: Per operator performance using different budget
strategies. Executed using Aspirin Count, RAM model,  =0.5, δ = .00005

query, the presence of the additional join operator overrides
the cascading cardinality benefit of the first join operator.
The uniform approach outperforms the eager approach byensuring that all three of the join operators receive differentially private cardinalities. The optimal approach outperforms both eager and uniform by combining the best of bothworlds. Optimal applies differential privacy to all operators,
like uniform, but it uses a larger fraction of the budget on
earlier operators, like eager.
Looking at the oracle approach, we can evaluate the accuracy of our cost model. For privacy reasons, our cost model
does not use the true cardinalities. Here, we see that the
optimal approach, which uses estimated cardinalities, andthe oracle approach, which uses true cardinalities, provide
similar performance. In experiments using Aspirin Count,
we calculate the correlation coefficient between the true execution time and the estimated execution time based on our
cost model as .998 for the circuit model and .931 for theRAM model, given a  = 0.5, δ = .00005. We see that
the Shrinkwrap cost model provides a reasonably accurate
prediction of the true cost.

the first join and reduces the intermediate cardinality byan order of magnitude. The optimal approach uses enoughbudget to reduce the intermediate cardinality, but not asmuch as eager.
The next operator, DISTINCT, also sees a large performance benefit. All three budget splitting approaches reduce
the runtime for DISTINCT by about an order of magnitude.
Since the baseline intermediate cardinality for DISTINCT ismuch larger, the uniform approach generates a differentiallyprivate cardinality that reduces the intermediate result size
and improves performance. The eager approach does nothave any additional budget to use, but the effect of the previous intermediate cardinality cascades through the query
tree and reduces the execution time for DISTINCT as well.
Finally, the optimal approach applies its remaining budget
to see a significant performance improvement.
In the Aspirin Count query, the three budget splitting approaches allocate the budget between three operators andprovide an insight into the trade-off between early and latebudget allocation. We see wildly varying execution times foreach of the operators, with different operators providing thebulk of the performance cost depending on the budget strategy. Here, the optimal strategy gives the best performance.
The substantial variance in execution for these operators
demonstrates the value of the added accuracy that our I/O
cost model provides.

7.5

Operator Breakdown

Now, we look at the execution time by operator to see
where Shrinkwrap provides the largest impact. We include
only private operators in the figure. For this experiment we
use the Aspirin Count query with  = 0.5 and δ = 0.00005.
We show the execution times for the baseline, fully padded
approach for intermediate results, as well as the uniform,
eager, and optimal budget splitting approaches.
Figure 8 shows the execution times of each operator in the
Aspirin Count query. Note that Shrinkwrap does not apply
any differential privacy until the output of Join M. (Join on
Medications), so we see no speed-up in the actual Join M.
operator, only in the later query operators.
The first operator to see a benefit from Shrinkwrap is
Join D. (Join on Demographics), the second join in thequery. Shrinkwrap generates a differentially private cardinality for the output of the previous join, Join M., according to the selected budget splitting approach. For uniform, the allocated budget is not large enough to generatea differentially-private cardinality that is smaller than the
fully padded cardinality. In fact, the overhead of calculating the differentially-private cardinality actually causes theoperator runtime to go above the baseline runtime. For eager, Shrinkwrap spends the entire budget on the output of

7.6

Join Scale Up

We now look at how Shrinkwrap scales with more complex workloads. From our experiments, we know that the
number of joins in a query has an extremely large impact on
execution time. More complex workloads typically containmore nested statements and require more advanced SQL
processing, but can be broken down into a series of simpler
statements. This work focuses on complexity as a functionof the join count in order to target the largest performancebottleneck in a single SQL statement.
In our experiment, we scale the join count and measure theperformance. Since Shrinkwrap applies differential privacy
at the operator outputs, we measure the performance impact
of join operators by looking at the execution time of their
immediate parent operator. For consistency, we truncate thenumber of non-inherited input tuples of each join to equalmagnitudes and use  = 0.5 and δ = 0.00005 for all runs.
From Figure 9, we see how execution time scales as afunction of the join count. As the number of joins increases,317

1000000

8.
Baseline

Shrinkwrap

Within the literature, different approaches exist to improve query processing in private data federations, such as
databases based on homomorphic encryption, TEEs, differential privacy, and cloud computation [1, 29, 30, 36, 45, 54].
Shrinkwrap, on the other hand, provides general-purpose,
hardware-agnostic, in-situ SQL evaluation with provable privacy guarantees and exact results.
PINQ [36] introduced the first database with differential privacy, along with privacy budget tracking and sensitivity analysis for operator composition. We extend thiswork by applying its privacy calculus to private data federations. Follow on work in differential privacy appears in
DJoin [38], where the system supports private execution ofcertain SQL operators over a federated database with strong
privacy guarantees and noisy results. Shrinkwrap supports
a larger set of database operators for execution and insteadof using noisy results to safeguard data, Shrinkwrap uses
noisy cardinalities to improve performance.
He et al. [22] applied computational differential privacy
in join operators for private record linkage and proposed athree desiderata approach to operator execution: precision,
provability, and performance. Shrinkwrap incorporates thisstyle of join execution and approach to execution trade-offs.
Pappas et al. [42] showed that by trading small bits of privacy for performance within provable bounds using bloom
filters, systems can provide scalable DBMS queries over arbitrary boolean queries. Shrinkwrap applies this pattern ofprovable privacy versus performance trade-offs to the larger
set of non-boolean arbitrary SQL queries.
Both Opaque [56] and Hermetic [54] use cost models toestimate performance slowdowns due to privacy-preserving
computation. In both cases, they use secure enclaves tocarry out private computation, which provides constantcost I/O. As such, their cost models cannot account for thevariable-cost I/O present in Shrinkwrap.

Execution Time (s)100000
10000
1000
100
10
1

1 Join2 Joins
Number of Joins

3 Joins

Figure 9: Aspirin Count with synthetic join scaling. Executed using RAM model.  = 0.5, δ = .00005
Without Shrinkwrap

With Shrinkwrap

Execution Time (s)

10000

1000

100

10

1
1x

5x 10x 15x 20x 25x 30x 35x 40x 45x 50xSynthetic Data Size, Above Baseline

Figure 10: Aspirin Count with synthetic data scaling. Executed using Circuit model.  = 0.5, δ = .00005
the execution time also increases. To find the source of theperformance slowdown, we can look at the Shrinkwrap costmodel. For each join operator, the baseline private data federation fully pads the output. If the join inputs were bothof size n, then the output would be n2 . As the number ofjoins increase, the cardinality rises from n to n2 to n3 . The
exponential increase in output cardinality requires significantly more I/O accesses, which cause the large slow downin performance. Shrinkwrap applies differential privacy to
reduce the output size at each join, reducing the magnitudeof each join output. While Shrinkwrap still sees a significant
growth in execution time as a function of the join count, theoverall performance is orders of magnitudes better.

7.7

RELATED WORK

9.

CONCLUSIONS AND FUTURE WORKIn this work, we introduce Shrinkwrap, a protocol-agnostic
system for differentially-private query processing that significantly improves the performance of private data federations. We use a computational differential privacy mechanism to selectively leak statistical information within provable privacy bounds and reduce the size of intermediate results. We introduce a novel cost model and privacy budget
optimizer to maximize the privacy, performance, and accuracy trade-off. We integrate Shrinkwrap into existing private data federation architecture and collect results using
real-world medical data.
In future research, we hope to further improve the performance of private data federations and the efficiency ofShrinkwrap. We are currently investigating novel secure array algorithms and data structures to improve I/O accesstime, privacy budget optimizations over multiple queries,and extensions of private data federations using additional
secure computation protocols and cryptographic primitives.

Data Size Scale Up

We evaluate the performance of Shrinkwrap with increasing data sizes. We leverage the higher efficiency of ourcircuit model protocol, EMP [51], to examine the effect ofShrinkwrap on larger input data sizes. Without Shrinkwrap,
the RAM model protocol, ObliVM [33], needs 1.3 hours to
run the Aspirin Count query and at 50x, 65 hours to complete. Instead, we use EMP which completes in 15 minutes.
Figure 10 shows the execution time with and without
Shrinkwrap using an implementation of EMP [51] on our
Aspirin Count reference query. We generated synthetic data
based on the original tables, giving us an effective maximum
data size of 750 GB. In Figure 10, we see that Shrinkwrap
provides a significant improvement during execution. As
the data size grows, our performance improvement grows as
well, reflecting the power and flexibility of Shrinkwrap.

Acknowledgments: We thank Abel Kho, Satyender Goel,
Katie Jackson, and Jess Joseph Behrens for their guidance
and assistance with CAPriCORN and HealthLNK data. We
also thank the HealthLNK team for sharing de-identified
electronic health record data for this study.

318

10.

REFERENCES[26] M. S. Islam, M. Kuzu, and M. Kantarcioglu. Access patterndisclosure on searchable encryption: Ramification, attack andmitigation. In Network and Distributed System Security
Symposium (NDSS, 2012.
[27] N. Johnson, J. P. Near, and D. Song. Towards Practical
Differential Privacy for SQL Queries. PVLDB, 11(5):526–539,
2018.
[28] P. Kocher, D. Genkin, D. Gruss, W. Haas, M. Hamburg,
M. Lipp, S. Mangard, T. Prescher, M. Schwarz, and Y. Yarom.
Spectre Attacks: Exploiting Speculative Execution. 2018.
[29] S. Laur, R. Talviste, and J. Willemson. From oblivious AES toefficient and secure database join in the multiparty setting.
Lecture Notes in Computer Science, 7954 LNCS:84–101, 2013.
[30] S. Laur, J. Willemson, and B. Zhang. Round-efficient Oblivious
Database Manipulation. ISC’11, pages 262–277, 2011.
[31] M. Lipp, D. Gruss, R. Spreitzer, C. Maurice, and S. Mangard.
ARMageddon : Cache Attacks on Mobile Devices. USENIX
Security, pages 549–564, 2016.
[32] C. Liu, Y. Huang, E. Shi, J. Katz, and M. Hicks. Automating
Efficient RAM-Model Secure Computation. 2014 IEEE
Symposium on Security and Privacy, pages 623–638, 2014.
[33] C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi. ObliVM :A Programming Framework for Secure Computation. Oakland,
pages 359–376, 2015.
[34] A. Machanavajjhala, D. Kifer, J. M. Abowd, J. Gehrke, and
L. Vilhuber. Privacy: Theory meets practice on the map. In
ICDE, 2008.
[35] R. McKenna, G. Miklau, M. Hay, and A. Machanavajjhala.
Optimizing error of high-dimensional statistical queries under
differential privacy. PVLDB, 11(10):1206–1219, 2018.
[36] F. D. McSherry. Privacy integrated queries: an extensible
platform for privacy-preserving data analysis. In 2009 ACM
SIGMOD, pages 19–30. ACM, 2009.
[37] I. Mironov, O. Pandey, O. Reingold, and S. Vadhan.
Computational differential privacy. In CRYPTO, 2009.
[38] A. Narayan and A. Haeberlen. DJoin: Differentially private joinqueries over distributed databases. Proceedings of the 10th
USENIX Symposium, page 14, 2012.
[39] M. Naveed, C. V. Wright, S. Kamara, and C. V. Wright.
Inference Attacks on Property-Preserving Encrypted
Databases. In Proceedings of the 22nd ACM SIGSAC
Conference on Computer and Communications Security,
pages 644–655. ACM, 2015.
[40] K. Nayak, X. S. Wang, S. Ioannidis, U. Weinsberg, N. Taft, andE. Shi. GraphSC : Parallel Secure Computation Made Easy.
[41] V. Nikolaenko, S. Ioannidis, U. Weinsberg, M. Joye, N. Taft,and D. Boneh. Privacy-preserving matrix factorization. In
Proceedings of the 2013 ACM SIGSAC conference on
Computer & communications security, pages 801–812. ACM,
2013.
[42] V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. G.
Choi, W. George, A. Keromytis, and S. Bellovin. Blind seer: A
scalable private DBMS. Proceedings - IEEE Symposium on
Security and Privacy, pages 359–374, 2014.
[43] PCORI. Characterizing the Effects of Recurrent Clostridium
Difficile Infection on Patients. IRB Protocol, ORA: 14122,
2015.
[44] PCORI. Exchanging de-identified data between hospitals forcity-wide health analysis in the Chicago Area HealthLNK datarepository (HDR). IRB Protocol, 2015.
[45] R. Popa and C. Redfield. CryptDB: protecting confidentiality
with encrypted query processing. SOSP, pages 85–100, 2011.
[46] J. Saia and M. Zamani. Recent Results in Scalable Multi-Party
Computation. 2014.
[47] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie,
and T. G. Price. Access path selection in a relational databasemanagement system. In Proceedings of the 1979 ACM
SIGMOD international conference on Management of data,
pages 23–34. ACM, 1979.
[48] S. Vadhan. The Complexity of Differential Privacy. Springer
International Publishing, 2017.
[49] J. Van Bulck, M. Minkin, O. Weisse, D. Genkin, B. Kasikci,
F. Piessens, M. Silberstein, T. F. Wenisch, Y. Yarom,
R. Strackx, and K. Leuven. Foreshadow: Extracting the Keys
to the Intel SGX Kingdom with Transient Out-of-Order
Execution. Proceedings of the 27th USENIX Security
Symposium, pages 991–1008, 2018.
[50] N. Volgushev, M. Schwarzkopf, B. Getchell, A. Lapets,
M. Varia, and A. Bestavros. Conclave Workflow Manager for
MPC, 2018.

[1] A. Arasu, S. Blanas, K. Eguro, R. Kaushik, D. Kossmann,
R. Ramamurthy, and R. Venkatesan. Orthogonal Security with
Cipherbase. CIDR, 2013.
[2] A. Arasu and R. Kaushik. Oblivious Query Processing. ICDT,
pages 26–37, 2014.
[3] G. Asharov and Y. Lindell. The BGW protocol for
perfectly-secure multiparty computation. Cryptology andInformation Security Series, 10(189):120–167, 2013.
[4] J. Bater, G. Elliott, C. Eggen, S. Goel, A. Kho, and J. Rogers.
SMCQL: Secure Querying for Federated Databases. PVLDB,
10(6):673–684, 2017.
[5] D. Beaver, S. Micali, and P. Rogaway. The Round Complexity
of Secure Protocols. ACM Symposium on Theory ofComputing STOC, pages 503–513, 1990.
[6] M. Bellare, V. T. Hoang, S. Keelveedhi, and P. Rogaway.
Efficient garbling from a fixed-key blockcipher. In S&P, pages
478–492. IEEE, 2013.
[7] V. Bindschaedler, P. Grubbs, D. Cash, T. Ristenpart, andV. Shmatikov. The tao of inference in privacy-protected
databases. PVLDB, 11(11):1715–1728, 2018.
[8] D. Bogdanov, L. Kamm, S. Laur, P. Pruulmann-Vengerfeldt,
R. Talviste, and J. Willemson. Privacy-preserving statistical
data analysis on federated databases. In Annual Privacy
Forum, pages 30–55. Springer, 2014.
[9] G. Chen, S. Chen, Y. Xiao, Y. Zhang, Z. Lin, and T. H. Lai.
SgxPectre Attacks: Leaking Enclave Secrets via Speculative
Execution. 2018.
[10] S. S. Chow, J.-H. Lee, and L. Subramanian. Two-party
computation model for privacy-preserving queries over
distributed databases. In NDSS, 2009.
[11] C. Clifton, M. Kantarcioglu, J. Vaidya, X. Lin, and and M.
Zhu. Tools for Privacy Preserving Distributed Data Mining.
ACM SIGKDD Explorations, 4(2), 2002.
[12] J. Doerner and A. Shelat. Scaling ORAM for Secure
Computation. Proceedings of the 2017 ACM SIGSAC
Conference on Computer and Communications Security CCS ’17, pages 523–535, 2017.
[13] C. Dwork. Differential privacy. Proceedings of the 33rd
International Colloquium on Automata, Languages andProgramming, pages 1–12, 2006.
[14] C. Dwork and A. Roth. The algorithmic foundations ofdifferential privacy. Found. Trends Theor. Comput. Sci., 2014.
[15] K. E. Emam. Heuristics for de-identifying health data. IEEE
Security & Privacy, 6(4):58–61, 2008.
[16] Ú. Erlingsson, V. Pihur, and A. Korolova. Rappor:
Randomized aggregatable privacy-preserving ordinal response.
In Proceedings of the 2014 ACM SIGSAC conference on
computer and communications security, pages 1054–1067.
ACM, 2014.
[17] A. Ferraiuolo, R. Xu, D. Zhang, A. C. Myers, and G. E. Suh.
Verification of a Practical Hardware Security Architecture
Through Static Information Flow Analysis. ACM SIGARCH
Computer Architecture News, 45(1):555–568, 2017.
[18] O. Goldreich. Towards a theory of software protection andsimulation by oblivious rams. In STOC, pages 182–194, New
York, NY, USA, 1987. ACM.
[19] O. Goldreich. Foundations of Cryptography: Volume 2, Basic
Applications. Cambridge University Press, New York, NY,
USA, 2004.
[20] O. Goldreich, S. Micali, and A. Wigderson. How to Play Any
Mental Game. Stoc ’87, pages 218–229, 1987.
[21] M. T. Goodrich and M. Mitzenmacher. Privacy-preserving
access of outsourced data via oblivious RAM simulation. In
ICALP, 2011.
[22] X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava.
Composing Differential Privacy and Secure Computation. In
Proceedings of the 2017 ACM SIGSAC Conference on
Computer and Communications Security - CCS ’17,
number 1, pages 1389–1406, New York, New York, USA, 2017.
[23] A. F. Hernandez, R. L. Fleurence, and R. L. Rothman. The
ADAPTABLE Trial and PCORnet: shining light on a newresearch paradigm. Annals of internal medicine,
163(8):635–636, 2015.
[24] Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure
two-party computation using garbled circuits. In USENIX
Security 2011, 2011.
[25] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending
oblivious transfers efficiently. In CRYPTO, LNCS, pages
145–161, 2003.

319

[51] X. Wang, A. J. Malozemoff, and J. Katz. EMP-Toolkit:
Efficient Multiparty Computation Toolkit.
https://github.com/emp-toolkit, 2016.
[52] X. Wang, A. J. Malozemoff, and J. Katz. Faster secure
two-party computation in the single-execution setting. Lecture
Notes in Computer Science (including subseries Lecture
Notes in Artificial Intelligence and Lecture Notes in
Bioinformatics), 10212 LNCS:399–424, 2017.
[53] X. S. Wang, K. Nayak, C. Liu, T.-H. H. Chan, E. Shi,
E. Stefanov, and Y. Huang. Oblivious Data Structures.
Proceedings of the 2014 ACM SIGSAC Conference on
Computer and Communications Security - CCS ’14, pages
215–226, 2014.
[54] M. Xu, A. Papadimitriou, A. Feldman, and A. Haeberlen.
Using Differential Privacy to Efficiently Mitigate Side Channels
in Distributed Analytics. In Proceedings of the 11th European
Workshop on Systems Security - EuroSec’18, pages 1–6, New
York, New York, USA, 2018. ACM Press.
[55] A. C. Yao. Protocols for secure computations. In Proceedingsof the 23rd Annual Symposium on Foundations of Computer
Science, SFCS ’82, pages 160–164, Washington, DC, USA,1982. IEEE Computer Society.
[56] W. Zheng, A. Dave, J. G. Beekman, R. A. Popa, J. E.
Gonzalez, and I. Stoica. Opaque: An oblivious and encrypted
distributed analytics platform. In Proceedings of the 14th
USENIX Conference on Networked Systems Design and
Implementation, NSDI’17, pages 283–298, Berkeley, CA, USA,2017. USENIX Association.

320