MnLargeSymbols’164 MnLargeSymbols’171

#  SPECIAL: Synopsis Assisted Secure Collaborative Analytics

Chenghong Wang  Indiana University<EMAIL_ADDRESS>,  Lina Qiu  Boston University
<EMAIL_ADDRESS>,  Johes Bater  Tufts University<EMAIL_ADDRESS>and  Yukui
Luo  Umass Dartmouth<EMAIL_ADDRESS>
###### Abstract.

Secure collaborative analytics (SCA) enable the processing of analytical SQL
queries across multiple owners’ data, even when direct data sharing is not
feasible. Although essential for strong privacy, the large overhead from data-
oblivious primitives in traditional SCA has hindered its practical adoption.
Recent SCA variants that permit controlled leakages under differential privacy
(DP) show a better balance between privacy and efficiency. However, they still
face significant challenges, such as potentially unbounded privacy loss,
suboptimal query planning, and lossy processing.

To address these challenges, we introduce SPECIAL, the first SCA system that
simultaneously ensures bounded privacy loss, advanced query planning, and
lossless processing. SPECIAL employs a novel synopsis-assisted secure
processing model, where a one-time privacy cost is spent to acquire private
synopses (table statistics) from owner data. These synopses then allow SPECIAL
to estimate (compaction) sizes for secure operations (e.g., filter, join) and
index encrypted data without extra privacy loss. Crucially, these estimates
and indexes can be prepared before runtime, thereby facilitating efficient
query planning and accurate cost estimations. Moreover, by using one-sided
noise mechanisms and private upper bound techniques, SPECIAL ensures strict
lossless processing for complex queries (e.g., multi-join). Through a
comprehensive benchmark, we show that SPECIAL significantly outperforms
cutting-edge SCAs, with up to $80\times$ faster query times and over
$900\times$ smaller memory for complex queries. Moreover, it also achieves up
to an $89\times$ reduction in privacy loss under continual processing.

##  1\. Introduction

Organizations, such as hospitals, frequently hold sensitive data in separate
silos to comply with privacy laws, despite the valuable insights that could be
gained from sharing this information. Recent advancement of Secure
Collaborative Analytics (SCA) (Eskandarian and Zaharia, 2017; Qin et al.,
2022; Roy Chowdhury et al., 2020; Wang et al., 2021, 2022; Bater et al., 2017,
2018; Liagouris et al., 2023; Poddar et al., 2021; Bater et al., 2020; He et
al., 2015) provides an exciting solution to tackle this dilemma. These systems
leverage advanced multi-party secure computation (MPC) (Yao, 1986) primitives
to empower multiple data owners, who previously could not directly share data,
to collaboratively process analytical queries over their combined data while
ensuring the privacy of each individual’s data.

While MPC can effectively conceal data values (Yao, 1986), its security
guarantees do not immediately extend to the protection of execution
transcripts. Consequently, data-dependent processing patterns such as memory
traces and read/write volumes can still reveal critical information, risking
privacy breaches (Cash et al., 2015; Kellaris et al., 2016; Blackstone et al.,
2019; Oya and Kerschbaum, 2021; Grubbs et al., 2018; Shang et al., 2021; Zhang
et al., 2016) even when the core data remains encrypted. To ensure strong
privacy, modern SCA systems also utilize data-oblivious primitives that
exhaustively pad query processing complexities to a worst-case, data-
independent upper bound (Bater et al., 2017; Liagouris et al., 2023; Poddar et
al., 2021). However, such stringent protections can largely reduce system
efficiency and hinder the generalization of conventional optimization
techniques to SCA, which are typically data-dependent (Liagouris et al.,
2023). To address this, recent efforts (Qin et al., 2022; Wang et al., 2021,
2022; Bater et al., 2018) have introduced differentially private SCA (DPSCA).
This approach allows controlled information leakage under differential privacy
(Dwork et al., 2014) to mitigate constant worst-case overhead. For instance,
systems under this model can dynamically compact intermediate query sizes to a
noisy estimate close to actual sizes, avoiding exhaustive padding. As such,
queries under DPSCA experience largely boosted efficiencies (e.g., up to
$10^{5}\times$ faster (Wang et al., 2022)) compared to their “no leakage”
counterparts. Despite these substantial performance gains, existing DPSCAs
still face critical limitations that impede their practical uses, as
elaborated below:

$\bullet$ L-1. Unbounded privacy loss. Most DPSCA systems utilize a per-
operator privacy expenditure model (Bater et al., 2018; Wang et al., 2021; Qin
et al., 2022; Chu et al., 2021; Chan et al., 2022; Wang et al., 2022), meaning
each query operator (e.g., join, filter) independently consumes a portion of
the privacy budget. This approach can lead to either unbounded privacy loss or
the forced cessation of query responses upon budget exhaustion. To mitigate
this, some studies (Zhang et al., 2023; Bogatov et al., 2021; Qiu et al.,
[n.d.]) propose private, locality-sensitive grouping, incurring a one-time
privacy cost to pre-group data based on specific attributes. Subsequent
queries on those attributes can be directly applied to a smaller subset and
need no additional privacy budget. However, this method only supports simple
queries (e.g., point and range); complex queries like joins still suffer from
unbounded privacy loss.

$\bullet$ L-2. Suboptimal execution plan. Conventional query planners can pre-
estimate sizes for equivalent plans of a given query and select the most
efficient plan with minimized intermediate sizes before execution
(Silberschatz et al., 2011; Blasgen et al., 1981). In contrast, SCA systems
lack this capability, and even DPSCA designs (Qin et al., 2022; Wang et al.,
2022; Zhang et al., 2023; Wagh et al., 2021; Bater et al., 2018, 2020) can
only reactively determine plan sizes during runtime. This inherent limitation
often forces existing systems to settle for less efficient query plans, such
as suboptimal join orders, which lead to significantly inflated intermediate
sizes (§ 7.2) and substantially hinder performance.

$\bullet$ L-3. Lossy processing. Noise from randomized mechanisms in DPSCA
also introduces a unique accuracy issue (e.g., losing tuples after
compaction), and unfortunately, no existing design can provide deterministic
accuracy guarantees for complex queries (Wang et al., 2021; Wagh et al., 2021;
Wang et al., 2022; Zhang et al., 2023; Groce et al., 2019). Furthermore,
stronger privacy settings can further increase noise variance, which amplifies
errors, significantly impacting the utility of SCA systems.

###  1.1. Overview of SPECIAL.

In this work, we introduce SPECIAL, an innovative SCA system designed to
address all these challenges simultaneously through a new paradigm called
synopsis-assisted secure processing. At its core, SPECIAL incurs a one-time
privacy cost to gather DP synopses (statistics of base tables) from owners’
data. These synopses are then used to compact query intermediate results,
index encrypted data, and enhance SCA query planning. Notably, SPECIAL is the
first system to provide all of the following benefits: (1) Bounded privacy—it
manages complex queries, such as multi joins, within strict privacy limits;
(2) Advanced query planning—it builds an advanced SCA planner that can exploit
plan sizes before runtime; and (3) Lossless processing—it ensures exact
results with no data omissions. An overview of SPECIAL’s architecture is shown
in Figure 1.

Figure 1. Overview of SPECIAL workflow.

SPECIAL operates under a standard server-aided MPC model (Kamara et al., 2011)
with three key participants: data owners, at least two SPECIAL servers, and a
vetted analyst. The process starts with data owners securely outsourcing their
data (e.g. using secret sharing (Kamara et al., 2011; Wang et al., 2021; Zhang
et al., 2023; Wang et al., 2022)), and privately release a set of DP synopses
(table statistics) to the servers. Once the data and synopses are ready,
analysts can then submit queries on the outsourced data. To process queries,
SPECIAL uses synopses to privately estimate tight result compaction bounds or
build private indexes for faster access, thus avoiding exhaustive padding.
Crucially, this information is exploit before runtime, so that SPECIAL can
pre-identify an optimal secure execution plan that minimizes intermediate
sizes and overall costs. Finally, the optimized plan is executed via MPC
across the secret-shared data, and the results are securely returned to the
analyst.

In the SPECIAL prototype, we adopt the same privacy model used in existing
DPSCA designs, assuming a computationally bounded, “honest-but-curious”
adversary (Goldreich, 2004) who can compromise up to $n-1$ out of $n$ owners
and $m-1$ out of $m$ servers. SPECIAL ensures that such an adversary can only
learn a limited leakage profile $\mathsf{Lkg}$ about honest parties’ data,
which strictly adheres to DP constraints. Note that, SPECIAL’s core
components, including synopses management and query planning do not leverage
raw data at all. Thus, any of the servers, alone or jointly, can manage these
tasks. Also, once analysts are authorized by data owners, they are considered
trusted, and additional randomization of query results is not required. It is
worth mentioning that SPECIAL’s corruption model (e.g. all except one) is
entirely determined by the underlying MPC, and SPECIAL’s design does not
modify them at all. Hence, one may also opt to a weaker corruption model, such
as a supermajority of owners and servers must remain uncorrupted (Liagouris et
al., 2023; Tan et al., 2021), to enhance efficiency.

###  1.2. Unique challenges and key contributions

Leveraging DP synopses in SCA holds significant promise for achieving our
desired objectives. However, this also introduces unique challenges. Below, we
highlight the key challenges and summarize our non-trivial contributions to
address them:

$\bullet$ C-1. How to select proper synopses? Even a single relation can have
numerous options for generating synopses, such as using different attributes
or their combinations. However, improper selection can lead to large errors
(e.g. using too many synopses or leverage high-dimensional attributes (Zhang
et al., 2021)), or reduced functionalities (e.g., using only simple attributes
(Zhang et al., 2023)). Hence, a key challenge is selecting a limited set of DP
synopses to optimize the privacy budget for complex query processing. Our
approach is informed by two observations: (i) secure joins are resource-
intensive and need prioritized acceleration, and (ii) synopses for common
filtering predicates are vital as they allow pre-built indexes on base
relations for fast access. Consequently, we propose a focused strategy (§ 4)
that targets low-dimensional (1D and 2D) attributes frequently involved in
joins and filters within a representative workload.

$\bullet$ C-2. How to enforce lossless processing? Private synopses do not
immediately implies lossless guarantees. Thus, a second challenge is designing
practical approaches to achieve lossless results without violating privacy
goals. To address this, we employ one-sided DP noise (either strictly positive
or negative, § 4) for generating synopses and design novel primitives (§ 5)
based on them to pessimistically estimate filter cardinalities and intervals
of index structures. This enable us to efficiently discard unnecessary records
during processing without breaking privacy and lossless guarantees. To ensure
lossless processing of complex joins, we extend upon cutting-edge join upper
bound techniques (Hertzschuch et al., 2021) to privately estimate join
compaction sizes using available synopses. To our knowledge, this is the first
study to support private join upper bound estimation.

$\bullet$ C-3. How DP synopses can empower efficient query processing? The use
of DP synopses in SCA is largely underexplored, leaving a knowledge gap
regarding their potential to enhance query efficiency. To navigate this
potential, we explore various use of synopses in accelerating secure
processing including private indexes SPEidx (§ 5.2), and compacted oblivious
operations SPEop (§ 5.3). We then develop a Selinger-style query planner (§ 6)
that supports both standard secure operators and SPEop. Employing a customized
cost model and tailored heuristics, this planner efficiently generates optimal
execution plans for queries using a mix of standard and SPEop operators. This
in essence, also address the limitations of sub-optimal execution plans
inherent in standard DPSCA.

$\bullet$ C-4. How to systematically evaluate SPECIAL? A major challenge in
SCA design evaluation is the absence of open-source benchmarks. We address
this by initiating an open-source evaluation platform accessible to the
public, utilizing public Financial data (Rel, [n.d.]) (1.1M rows and 59
columns), and designing eight test queries ranging from simple linear to
complex 5-way joins. We evaluated our prototype SPECIAL alongside the state-
of-the-art DPSCA system, Shrinkwrap (Bater et al., 2018), and conventional
SCA, SMCQL (Bater et al., 2017). Results indicate that SPECIAL outperforms
Shrinkwrap, reducing query latency by up to $80.3\times$, and SMCQL, with at
least a $114\times$ reduction in query latency. Additionally, SPECIAL improves
memory efficiency in complex join processing by more than $900\times$ compared
to both systems. Moreover, scaling experiments show that SPECIAL can
effectively scale linear and binary joins up to $8\times$ (8.8M rows) and
5-way joins up to $4\times$ (4.4M rows) workloads. All benchmarks, including
our prototype implementation, are open-sourced and available at (Lovingmage,
2024).

The remainder of the paper is structured as follows: We begin with essential
background in § 2 and a formal definition of our privacy model in § 3 before
delving into design details. § 4 discusses the SPECIAL catalog design,
including synopses selection and generation. § 5 details novel synopses-
assisted secure database operators, and § 6 describes our planner design.
Benchmark evaluations are presented in § 7, followed related works and
conclusions.

##  2\. Background

General notations. We consider the logical database $\mathcal{D}$ to contain
multiple private relations $\\{D_{1},D_{2},...\\}$, where each relation
$D_{i}$ is belongs owned by a specific party $P_{i}$, where $D\in\mathcal{D}$
is owned by a specific owner and has a set of attributes as $attr(D)$. The
domain for attribute $A\in attr(D)$ is given by $dom(A)$, and the combined
domain for a collection of attributes
$\mathbf{A}=\\{A_{1},A_{2},...\\}\subseteq attr(D)$ is denoted as
$dom(\mathbf{A})=\prod_{A\in\mathbf{A}}dom(A)$. For a tuple $t\in D$, and
$\mathbf{A}\subseteq attr(D)$, we denote $t.\mathbf{A}$ as the attribute value
of $\mathbf{A}$ in $t$
Frequency (count). Given $D$, and $\mathbf{A}\subseteq attr(D)$, and
$\mathbf{v}\in dom(\mathbf{A})$, the frequency (count) of $\mathbf{v}$ in $D$
is the total number of tuples $t\in D$ with $t.\mathbf{A}=\mathbf{v}$. In
addition, the max frequency moments (MF) of $\mathbf{A}$ is defined as
${\mathtt{mf}}(\mathbf{A},D)=\max_{\mathbf{v}\in dom(\mathbf{A})}|\\{t\in
D\mid t.\mathbf{A}=\mathbf{v}\\}|$.
Histograms. Given $D$, and $\mathbf{A}\subseteq attr(D)$, the (equal-width)
histogram $\mathbf{h}(\mathbf{A},D)=(c_{1},c_{2},...,c_{m})$ is a list of
counts for the attribute values in $\mathbf{A}$. Specifically, $\mathbf{h}$
partitions111We use a condensed notation that omits arguments when
$\mathbf{A}$ and $D$ are obvious. $dom(\mathbf{A})$ into $m$ “equal-sized”
domain intervals $(B_{1},...,B_{m})$, and each count $c_{i}\in\mathbf{h}$
corresponds to the total number of $t\in D$ such that $t.\mathbf{A}$ fall
within $B_{i}$.

Multi-party secure computation (MPC). MPC (Yao, 1986; Goldreich, 2009; Micali
et al., 1987; Ben-Or et al., 2019) is a cryptographic techniques to allow a
group of participants $P_{1},P_{2},...$ to jointly compute a function
$f(x_{1},x_{2},...)$ over their respective private input $x_{i}$. MPC ensures
that no unauthorized information is revealed to any involved party, excepted
the desired output of function $f$, emulating a computation as if performed by
a trusted third party. Earlier MPC typically require all parties to
participate in intensive computations. Recent schemes (Kamara et al., 2011;
Scholl et al., 2017; Mohassel and Zhang, 2017) allow these computations to be
offloaded to multiple powerful servers without sacrificing original security
guarantees, known as the server-aided MPC. In this approach, each party, say
$P_{i}$, secretly shares their inputs, $x_{i}$ to servers. These servers then
jointly evaluate an MPC that functionally replicates the logic of first
reconstructing the secrets $x_{1},x_{2},\ldots$ and then evaluating
$f(x_{1},x_{2},\ldots)$. Depending on designs, the result may be directly
returned to the parties or re-shared among the servers for later retrieval. By
default, SPECIAL considers server-aided MPC with two non-colluding servers.

Secret sharing and secure array. SPECIAL uses the $2$-out-of-$2$ boolean
secret share (Araki et al., 2016) over ring $\mathbb{Z}_{2^{32}}$ for securely
outsourcing owners’ data and storing query execution results. Specifically,
each data, $x$, is divided into two shares: $x1,x2$ that are uniformly
distributed over the ring $\mathbb{Z}_{2^{32}}$ such that $x=x1\oplus x2$.
Each server $S_{i}$ receives one secret shares, $s_{i}$, where
$i\in\\{0,1\\}$. By retrieving shares from any two servers, an authorized
party can successfully reconstruct the value of $x$. However, a single server
alone learns nothing about $x$. For clarity and to abstract out the lower-
level details, we leverage a logically unified data structure, namely the
secure array (Wang et al., 2022; Bater et al., 2018), denoted as
$\langle\mathbf{x}\rangle=\left(\langle x_{1}\rangle,\langle
x_{2}\rangle,...\right)$, which is a collection of secret-shared relational
tuples.

Oblivious (relational) operators. Oblivious operators are specific MPC
protocols, applied over secure arrays, that implement database operator
functionalities such as filter, join, and aggregation. Specifically, an
oblivious operator
$\langle\mathbf{o}\rangle\leftarrow\mathsf{\textbf{op}}(\langle\mathbf{a}\rangle,\langle\mathbf{b}\rangle,...)$
accepts one or more secure arrays as inputs, performs database operations over
the inputs, and then writes the result to an output secure array. Moreover,
the oblivious property stipulates that absolutely no memory access pattern
information is disclosed (Chang et al., 2022; Ramachandran and Shi, 2021;
Liagouris et al., 2023) (or in other words, the memory access is fully
independent from input data) during the protocol’s execution. Since revealing
output size can also enable numerous reconstruction attacks, recent designs of
oblivious operators also consider hiding output volumes, i.e., by padding the
outputs to their maximum sizes. Thus, unless otherwise stated, we assume that
all the subsequent oblivious operators mentioned have considered volume-
hiding.

Differential privacy (Dwork et al., 2014). DP ensures that modifying a single
input data tuple to a mechanism produces only a negligible change in its
output. To elaborate, consider $D$ and $D^{\prime}$ as two databases differing
by just one tuple—termed as neighboring databases. Then:

###### Definition 2.1 ($(\epsilon,\delta)$-differential privacy).

_Given $\epsilon>0$, and $\delta\in(0,1)$. A randomized mechanism
$\mathcal{M}$ is said to be $(\epsilon,\delta)$-DP if for all pairs of
neighboring databases $D,D^{\prime}$, and any possible output $o\subset
Range(\mathcal{M})$, the following holds:_

$\textup{Pr}\left[\mathcal{M}(D)\in o\right]\leq
e^{\epsilon}\textup{Pr}\left[\mathcal{M}(D^{\prime})\in o\right]+\delta$

##  3\. Privacy Model

In this section, we formally define the privacy definitions of SPECIAL and
explain the corresponding semantics. Similar to previous work on DPSCA (Wang
et al., 2022; Zhang et al., 2023), we follow computational DP (SIM-CDP)
(Mironov et al., 2009) framework for privacy model formulation.

###### Definition 3.1 (Secure protocol with DP leakage).

Given a party (owner) $P$ with private data $D$ and a randomized mechanism
$\mathsf{Lkg}(D)$, referred to as the leakage profile of $P$’s data. Consider
$\Pi$ a secure query processing protocol applied to $D$. The protocol $\Pi$ is
said to be secure with DP leakage if, for any honest party $P$ with data $D$
and any probabilistic polynomial time (p.p.t.) adversary $\mathcal{A}$:

  * •

$\mathsf{Lkg}(D)$ satisfies $(\epsilon,\delta)$-DP (definition 2.1).

  * •

There exists a p.p.t. simulator $\mathcal{S}$ with only access to public
parameters $\mathsf{pp}$ and the output of $\mathsf{Lkg}(D)$ that satisfies:

(1)
$\begin{split}&\textup{Pr}\left[\mathcal{A}\left(\mathsf{VIEW}^{\Pi}(\mathcal{D},\mathsf{pp})=1\right)\right]\\\
&\leq\textup{Pr}\left[\mathcal{A}\left(\mathsf{VIEW}^{\mathcal{S}}(F(\mathcal{D}),\mathsf{pp})\right)=1\right]+\mathsf{negl}(\kappa)\end{split}$

where $\mathsf{VIEW}^{\Pi}$, and $\mathsf{VIEW}^{\mathcal{S}}$ denotes the
adversary’s view against the protocol execution and the simulator’s outputs,
respectively. And $\mathsf{negl}(\kappa)$ is a negligible function related to
a security parameter $\kappa$.

Simply put, Definition 3.1 specifies that as long as there is at least one
honest owner, the knowledge any p.p.t. adversary can obtain about this owner’s
data from observing $\Pi$ execution transcripts is bounded to what can be
inferred from the outputs of an $(\epsilon,\delta)$-DP mechanism
$\mathsf{Lkg}$. By default, we define $\mathsf{Lkg}$ within
$(\epsilon,\delta)$-tuple level DP (Dwork et al., 2010), that’s said primary
privacy objective is to protect individual tuples. However, due to group-
privacy properties (Kifer and Machanavajjhala, 2011; Xiao and Xiong, 2015) of
DP, privacy can extend across multiple tuples and to user-level, as long as a
user owns a limited number of tuples. Throughout this paper, our focus remains
on developing algorithms that guarantee tuple-level privacy, while upholding
all stated privacy guarantees, albeit with potentially different privacy
parameters.

###### Theorem 3.2.

The privacy of SPECIAL adheres to Definition 3.1

###### Proof.

Due to space concerns, we defer the complete privacy proof of SPECIAL to
Appendix A. ∎

##  4\. SPECIAL Synopses

SPECIAL maintains independent DP synopses for all outsourced data. Each
synopsis holds noisy statistics that reflect the corresponding data’s
distributional traits. As per our core design idea, these statistics will be
used to dynamically optimize query processing—for example, by estimating tight
compaction bounds or enabling fast access to eliminate unnecessary tuples,
which significantly compacts intermediate query sizes, all without any extra
privacy cost.

Challenges. A major design challenge is selecting proper synopses to achieve
our design goals. This involves decisions such as attribute selection,
combinations thereof, and the types of statistics used (e.g., histograms,
min/max/avg, frequency counts, etc.). Using too many attributes or leveraging
complex (high-dimensional) combinations can introduce significant noise (Zhang
et al., 2021) and increase storage costs. Another challenge involves privately
releasing synopses to aid in lossless processing, such as result compaction
and private indexing. Ensuring lossless compaction requires consistently
overestimating the output sizes of subplans. Supporting lossless indexes is
even more complex: for a given indexed range $D[\mathsf{lo},\mathsf{hi}]$, we
need to overestimate the upper index $\mathsf{hi}$ and underestimate the lower
index $\mathsf{lo}$. Unfortunately, traditional DP methods, which typically
use symmetric additive noises, struggle to ensure these conditions.

Key ideas. We observe that joins are more resource-intensive than any other
operations. For instance a $k$-way oblivious join can incur a $O(n^{k})$
complexity if without optimisations (Bater et al., 2017, 2018; Wang et al.,
2022; Zheng et al., 2017; Eskandarian and Zaharia, 2017). Hence, joins require
prioritized acceleration. Moreover, synopses available for frequently queried
filter attributes on base relations are vital (Wang et al., 2022) as well.
These statistics not only help to compact input data at an early stage before
heavy joins, but also enable fast indexing (§ 5.2) for quick data access.
Hence, to address the first challenge, our key idea is to focus on commonly
queried join and base relation filter attributes, as well as their low-
dimensional combinations.

To tackle the second challenge, our key idea is twofold. First, to ensure
lossless result compaction of filters and indexing, we employ one-sided DP
noise to generate private histograms that either overestimate or underestimate
attribute distributions consistently. Second, to achieve lossless compaction
of join outputs, we integrate noisy max frequency moments (MF) into the
synopses. This integration enables us to extend upon advanced join upper bound
techniques (Hertzschuch et al., 2021) to privately estimate join compaction
sizes without losing data (§ 5.2).

###  4.1. Synopses generation

Steered by our key ideas, we now elaborate on our synopsis generation details.
The general process is outlined as follows: Initially, the SPECIAL servers
selects appropriate attributes to generate private synopses, which are then
distributed to owners. The owners create the synopses using a DP mechanism and
upload them to SPECIAL servers. Finally, the server applies post-processing to
these synopses to aid in query processing.

Attributes selection (servers). The first step is to identify a smaller set of
attributes for deriving synopses. In general, we consider the existence of a
representative workload, $Q_{\mathsf{R}}$ (Kotsogiannis et al., 2019), which
can be sourced from a warm-up run of SPECIAL or annotated by the
administrator. Note that this process do not incur any private data thus is
leakage-free. The servers first identify representative attribute pairs,
$\mathsf{pair}=\\{\mathsf{pair}_{k}\\}_{k\geq 1}$, for each private relation
$D\in\mathcal{D}$ via $Q_{\mathsf{R}}$. The designated pairs include: (i)
2-way attribute pairs, which correspond to frequently queried _filter-join
key_ combinations; (ii) frequently queried individual attributes not covered
by these pairs. By default, each
$\mathsf{pair}_{k}=(A_{\mathsf{ft}},A_{\mathsf{j}})$ contains two valid
attributes (case i), but either $A_{\mathsf{ft}}$ or $A_{\mathsf{j}}$ may be
empty (case ii).

Synopses release (owners). Next, servers pushes the identified pairs to each
owner, and subsequently, the owner independently dispatches a private synopsis
and returns it to servers. In what follows, we focus on the DP synopses
generation mechanism evaluated by each owner, Algorithm 1 illustrates the
overall flow.

Algorithm 1 DP synopsis generation $\mathcal{M}_{\mathtt{synop}}$ (in the view
of $P$)

1:Input: $\mathsf{pair}=\\{\mathsf{pair}_{k}\\}_{k\geq 1}$ from servers;
private data $D$.

2:$P$ self-determines privacy parameters $\epsilon,\delta$, and init
$\mathtt{synop}\leftarrow\emptyset$

3:for each $\mathsf{pair}_{k}$ do

4:
$\mathbf{h}(\mathsf{pair}_{k},D)\leftarrow\mathsf{HistGen}(\mathsf{pair}_{k},D)$

5:DP histograms:

6:
$\mathbf{h}^{+}(\mathsf{pair}_{k},D)\leftarrow\mathbf{h}+\mathsf{Lap}^{+}(\epsilon,\delta,\mathbf{h}.\mathsf{shape})$

7:
$\mathbf{h}^{-}(\mathsf{pair}_{k},D)\leftarrow\mathbf{h}+\mathsf{Lap}^{-}(\epsilon,\delta,\mathbf{h}.\mathsf{shape})$

8:$\triangleright$ adding independently sampled noise to every bin of
$\mathbf{h}^{+}$, $\mathbf{h}^{-}$

9:DP max frequencies:

10: if $A_{\mathsf{j}}\in\mathsf{pair}_{k}=\emptyset$ or $A_{\mathsf{j}}$ is
unique valued then $\mathtt{MF}_{k}=\emptyset$

11: else if $A_{\mathsf{ft}}\in\mathsf{pair}_{k}\neq\emptyset$ then

12:$\triangleright$ assuming $\mathbf{h}$ partitions $dom(A_{\mathsf{ft}})$
into $\\{B_{1},...,B_{m}\\}$

13: $D^{\ell}\leftarrow\sigma_{A_{\mathsf{ft}}\in B_{\ell}}(D)$ for
$\ell=1,2,...,m$

14: compute noisy MF table,
$\mathtt{MF}_{k}=\\{\widehat{\mathtt{mf}}(A_{\mathsf{j}},D^{\ell})\\}_{1\leq\ell\leq
m}$

15: else $\mathtt{MF}_{k}=\widehat{\mathtt{mf}}(A_{\mathsf{j}},D)$

16: $\mathtt{synop}\leftarrow\mathtt{synop}\cup(\mathsf{pair}_{k},\\{{\bf
h}^{+},{\bf h}^{-}\\},\mathtt{MF}_{k})$

17:release $\mathtt{synop}$, $\epsilon$, $\delta$ to servers

Generally, we expect owners to set a desired privacy budget for their data
(using parameters $\epsilon$ and $\delta$) before initiating the synopsis
generation. For each $\mathsf{pair}_{k}$, the owner first creates a histogram
$\mathbf{h}(\mathsf{pair}_{k},D)$. By default, we assume there exist global
parameters, i.e. bin sizes of each attribute, which guide all owners to
partition attributes consistently. Next, the owner derives two noisy
histograms, $\mathbf{h}^{+}(\mathsf{pair}_{k},D)$, and
$\mathbf{h}^{-}(\mathsf{pair}_{k},D)$ by adding independently sampled one-
sided Laplace noises to every bin of $\mathbf{h}(\mathsf{pair}_{k},D)$.

###### Definition 4.1 (One-sided Laplace variable).

_$\mathsf{Lap}^{+}(\epsilon,\delta)=\max(0,z)$ (resp.
$\mathsf{Lap}^{-}(\epsilon,\delta)=\min(0,z)$) is a one-sided Laplace random
variable in the range of $[0,\infty)$ (resp. $(-\infty,0]$) if $z$ is drawn
from a distribution with the following density function_

(2)
$\begin{split}\textup{Pr}\left[z=x\right]=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}e^{-\epsilon|x-\mu|}\end{split}$

_where $\mu=1-\frac{1}{\epsilon}\ln(\delta(e^{\epsilon}+1))$ (resp.
$\mu=\frac{1}{\epsilon}\ln(\delta(e^{\epsilon}+1))-1$)._

The one-sided Laplace noise can be strictly positive ($\mathsf{Lap}^{+}$) or
negative ($\mathsf{Lap}^{-}$). This ensures that $\mathbf{h}^{+}$ always
overestimates the actual histogram, while $\mathbf{h}^{-}$ consistently
underestimates it. For the ease of description, we refer
$\mathbf{H}(\mathsf{pair}_{k},D)=\\{\mathbf{h}^{+},\mathbf{h}^{-}\\}$ as the
bounding histogram of attribute $\mathsf{pair}_{k}$, with $\mathbf{h}^{+}$,
and $\mathbf{h}^{-}$ to be the upper and lower histograms, respectively.

We continue with the details of the (noisy) MFs generation. Assume both
$A_{\mathsf{ft}},A_{\mathsf{j}}\neq\emptyset$, and the
$\mathbf{h}(\mathsf{pair}_{k},D)$ partitions $dom(A_{\mathsf{ft}})$ into
$\\{B_{1},...,B_{m}\\}$. The mechanism $\mathcal{M}_{\mathtt{synop}}$
generates a table of noisy MFs,
$\\{\widehat{\mathtt{mf}}(A_{\mathsf{j}},D^{\ell})\\}_{\ell\geq 1}$, where
each entry $\widehat{\mathtt{mf}}(A_{\mathsf{j}},D^{\ell})$ is an independent
MF statistic for $A_{\mathsf{j}}$ over specific filtered data on
$A_{\mathsf{ft}}$, such that

(3)
$\widehat{\mathtt{mf}}(A_{\mathsf{j}},D^{\ell})\leftarrow\widehat{\max}_{\epsilon}\left(\mathcal{G}_{\mathbf{count}(A_{\mathsf{j}})}\left(\sigma_{A_{\mathsf{ft}}\in
B_{\ell}}(D)\right)\right)$

here $\mathcal{G}_{\mathbf{count}(A_{\mathsf{j}})}$ is a group-by-count
operation over $A_{\mathsf{j}}$, and $\widehat{\max}_{\epsilon}$ is a report
noisy max mechanism (Dwork et al., 2014). It first adds i.i.d. noise from the
exponential distribution $\mathsf{Exp}(\frac{2}{\epsilon})$ to each grouped
count, then outputs the largest noisy count. We stress that
$\mathcal{M}_{\mathtt{synop}}$ will not generate noisy MFs for non-join key
attributes, and when $A_{\mathsf{ft}}$ is empty, a global MF will be generated
instead of MF tables (Alg 1:10). Moreover, since SPECIAL enables owners to
label attributes as unique-valued, if $A_{\mathsf{j}}$ is known to be unique-
valued, then $\smash{\widehat{\mathtt{mf}}(A_{\mathsf{j}},\cdot)}$ is always
1. Nevertheless, as exponential noises are non-negative, thus
$\widehat{\mathtt{mf}}\geq\mathtt{mf}$ holds for all cases. Given the
discussion so far, we summarize SPECIAL synopses as:

###### Definition 4.2 (SPECIAL synopses).

Given representative workload $Q_{\mathsf{R}}$, we consider for each relation
$D$, its corresponding synopsis $\mathtt{synop}$ to be the collection of
$\\{(\mathsf{pair}_{k},\mathbf{H}(\mathsf{pair}_{k},D),\mathtt{MF}_{k})\\}_{k\geq
1}$, such that

  * •

$\mathsf{pair}_{k}$ is a frequently queried attribute (pair) over $D$ found in
$Q_{\mathsf{R}}$.

  * •

$\mathbf{H}$ is the private bounding histogram for $\mathsf{pair}_{k}$ over
$D$.

  * •

$\mathtt{MF}_{k}$ represents a collection of privately overestimated join key
MFs that corresponds to a group of tuples in $\mathbf{h}$, categorized by
$\mathsf{pair}_{k}.A_{\mathsf{ft}}$.

###### Theorem 4.3.

Given $|\mathsf{pair}|=c$, $\epsilon,\delta>0$, the synopsis generation
(Algorithm 1) is $(\hat{\epsilon},\hat{\delta})$-DP where $\hat{\epsilon}\leq
6\epsilon\sqrt{c\ln(1/\delta)}$, and $\hat{\delta}=(c+1)\delta$

For space concern, we move the complete proof to Appendix A. In a sketch,
adding $\mathsf{Lap}^{+}$ (or $\mathsf{Lap}^{-}$) to a single bin is
$(\epsilon,\delta)$-DP. By parallel and sequential composition, generating
$\mathbf{{H}}$ is $(2\epsilon,2\delta)$-DP. Moreover, each report noisy max is
$(\epsilon,0)$-DP, and by parallel composition, the generation of the entire
MF table is also $(\epsilon,0)$-DP. In this way, we know that the generation
of each $(\mathsf{pair}_{k},\mathbf{H},\mathtt{MF}_{k})$ is at most
$(3\epsilon,\delta)$-DP. Given there are in total $c$ such pairs, and thus the
total privacy loss is subject to $c$-fold advanced composition (Dwork et al.,
2014).

Synopsis transformations. We say that one can perform transformations on
released synopses without incurring extra privacy loss, per the post-
processing theorem of DP (Dwork et al., 2014). Now, we briefly outline key
synopsis transformations relevant to the SPECIAL design. First, given any (2d)
bounding histogram $\mathbf{H}(\mathsf{pair},D)$ with both
$A_{\mathsf{ft}},A_{\mathsf{j}}\in\mathsf{pair}$ are non-empty, one can derive
the (1d) bounding histograms, i.e. $\mathbf{H}(A_{\mathsf{j}},D)$ and
$\mathbf{H}(A_{\mathsf{ft}},D)$, for any single attribute $A_{\mathsf{ft}}$ or
$A_{\mathsf{j}}$ by marginal sums
$\mathbf{h}^{+},\mathbf{h}^{-}\in\mathbf{H}(\mathsf{pair},D)$ over
$A_{\mathsf{j}}$ or $A_{\mathsf{ft}}$, respectively. This enables the creation
of statistics on individual attributes, even when $A_{\mathsf{ft}}$ and
$A_{\mathsf{j}}$ are not included as a standalone synopsis attribute.
Moreover, it’s possible to derive relevant join key statistics even following
a selection on the base relation. For example, given
$A_{\mathsf{ft}},A_{\mathsf{j}}\in\mathsf{pair}\neq\emptyset$, and let
$D^{\prime}\leftarrow\sigma_{A_{\mathsf{ft}}\in vals}(D)$, one can obtain the
(1d) bounding histogram $\mathbf{H}(A_{\mathsf{j}},D^{\prime})$ by conducting
a selective marginal sum of
$\mathbf{h}^{+},\mathbf{h}^{-}\in\mathbf{H}(\mathsf{pair},D)$ over bins of
$A_{\mathsf{ft}}$ that intersect with $vals$. Beyond bounding histograms, join
key MFs over pre-filtered data can also be computed by

(4)
$~{}\widehat{\mathtt{mf}}(A_{\mathsf{j}},D^{\prime})=\min\left(\textstyle\sum_{B_{\ell}\cap
vals\neq\emptyset}\widehat{\mathtt{mf}}(A_{\mathsf{j}},D^{\ell}),\widehat{\mathtt{mf}}(A_{\mathsf{j}},D)\right)$

Note that $\widehat{\mathtt{mf}}(A_{\mathsf{j}},D)$ exists if $A_{\mathsf{j}}$
is also included as a standalone synopsis attribute; otherwise, Eq 4 yields
only the first term.

##  5\. SPECIAL Primitives

We now outline key secure database operations offered by SPECIAL. A major
challenge in designing synopsis-assisted secure processing is the evident
knowledge gap on how private synopses could potentially accelerate oblivious
query processing. To bridge this gap, we explore various uses of synopses,
such as creating private indexes (SPEidx 5.2) and designing compacted
oblivious operations (SPEop 5.3). Moreover, as discussed earlier, joins are
the most intensive operations. Hence, we extensively optimize join algorithms,
synergizing both private indexing and compaction techniques to develop a
novel, parallel-friendly oblivious join (§ 5.3). Another challenge in
primitive design arises from ensuring lossless guarantees. To address this, we
integrate mechanisms into our designs that pessimistically estimate selection
cardinalities, indexing ranges, and complex join sizes, using a combination of
available synopses and advanced upper bound techniques (Hertzschuch et al.,
2021). For clarity, we’ll assume, WLOG., that all input relations below are of
size $n$ and all 1d histograms contain $m$ bins.

###  5.1. Basic Operations

SPECIAL supports conventional fully-oblivious operators (Bater et al., 2017).
In general, these operators function logically the same as non-private ones,
but their execution transcripts are completely data independent, with results
consistently padded to the worst-case maximum.

Default data access SeqACC. By default, all query executions proceed with a
standard data access, loading all data into a secure array using a sequential
scan222In the context of a secret-shared array $\langle D\rangle$, this step
can be each server sequentially load the respective secret shares of $D$ into
memory, readying them for MPC.. Additionally, each loaded tuple gets a secret
bit (initially ‘0’), $\mathsf{ret}$, used to mark tuple validity.

SELECT. is the secure version of filter $\sigma_{p}(R)$. It conducts a linear
scan over secure array $\langle R\rangle$ for relation $R$ and updates the
$\mathsf{ret}$ bit: ‘1’ for tuples satisfying predicate $p$ and ‘0’ for
others. Every tuple’s $\mathsf{ret}$ bit is updated, regardless of whether it
matches the predicate.

PROJECT. discards irrelevant attributes for relation stored in $\langle
R\rangle$. Note that the secret bit $\mathsf{ret}$ cannot be discarded by a
PROJECT.

JOIN. implements the secure version of $\theta$-join,
$R_{0}\Join_{\theta}R_{1}$. It processes two secure arrays $\langle
R_{0}\rangle$ and $\langle R_{1}\rangle$, computing their cartesian product
$\langle R_{0}\times R_{1}\rangle$ and then using SELECT to mark the joined
tuples. It’s important to note that JOIN expands output, always padding it to
the worst-case max (product of input sizes).

COUNT, SUM, MIN/MAX are the aggregation primitives. The operators linearly
scan a secure array and continuously update a secret-shared aggregation value
after each tuple access.

ORDER-BY, DISTINCT, GROUP-BY(AGG). are built on the oblivious sort primitive
(Batcher, 1968). Specifically, ORDER-BY obliviously sorts a secure array
according to a given attribute. DISTINCT sorts a secure array first, then
performs a linear scan to identify unique tuples. For instance, among
consecutively sorted identical tuples, it sets the $\mathsf{ret}$ bit of the
last tuple to ‘1’ and the rest to ‘0’. GROUP-BY(AGG) starts by using DISTINCT
to identify unique tuples. For each distinct tuple ($\mathsf{ret}$ set to
‘1’), it appends an aggregation value derived from the tuple and a dummy
attribute (e.g., ‘-1’) for non-distinct tuples.

###  5.2. SPECIAL Index SPEidx

In conventional databases, indexes are powerful data structures that map
attribute values to positions within a sorted array, enabling fast data
access. However, generalizing such feature to SCA remains largely
underexplored with existing solutions facing significant limitations such as
high data loss (Roy Chowdhury et al., 2020), dependence on complex data
structures filled with dummy tuples (Zhang et al., 2023; Bogatov et al.,
2021), and limited query capabilities (i.e., linear queries across fixed
attributes). Moreover, these methods only index base relations. SPEidx
innovatively overcomes these issues by enabling the creation of lossless
indexes directly on outsourced data or query intermediate results, without the
need for additional structures or dummy injections.

In general, SPEidx builds upon the typical indexing model that utilizes
cumulative frequencies (CF) (Kraska et al., 2018). Specifically, given $D$
sorted by $A\in attr(D)$, all records $t\in D$ where $t.A=x$ can be indexed by
the interval $[g(x-1),g(x)]$, where $g(x)=|\\{t\mid t.A\leq x\\}|$ is the CF
function. For better illustration, we show an example index lookup in Figure
2: to get all records with an attribute value of 24, one may compute
$[g(23),g(24)]=[217,248]$ and access the relevant data from the subset
$D[217:248]$. To make this indexing method private and lossless, the key idea
of SPEidx is to derive two noisy CF curves from synopses (e.g. bounding
histograms). One curve, $g^{+}(x)$, consistently overestimates $g(x)$, while
the other, $g^{-}(x)$, consistently underestimates it. Then for any attribute
value $x$, we can now derive a private interval $[g^{-}(x-1),g^{+}(x)]$ that
losslessly indexes all desired records. For instance, as illustrated in Figure
2, the SPECIAL index might estimate the index range for attribute value 24 as
$[g^{-}(23),g^{+}(24)]=[198,267]$.

Figure 2. True index (left) vs. SPECIAL index (right) for $x=24$

In what follows, we provide the formal explanations on how SPEidx derives
indexes from DP synopses. Specifically, SPEidx first determines the bounding
histograms $\mathbf{H}(A,D)$, which may be either transformed from an
available 2D histogram $\mathbf{H}(\mathsf{pair},D)$ with $A\in\mathsf{pair}$,
or sourced directly if $\mathbf{H}(A,D)$ is already included in the synopses.
It then constructs the noisy mapping as follows:

###### Definition 5.1 (SPECIAL index).

_Given $D$ sorted by $A$, the bounding histogram
$\mathbf{H}(A,D)=\\{\mathbf{h}^{+},\mathbf{h}^{-}\\}$, and assume
$\mathbf{h}^{+}=(c^{+}_{1},...,c^{+}_{m})$,
$\mathbf{h}^{-}=(c^{-}_{1},...,c^{-}_{m})$ partitions $dom(A)$ into
$\\{B_{1},...,B_{m}\\}$. We say
$\textsc{SPEidx}(A,D)=\\{\mathsf{idx}_{i}=[\mathsf{lo}_{i},\mathsf{hi}_{i}]\\}_{1\leq
i\leq m}$ is the SPECIAL index of $D$ over $A$ with:_

  * •

$\forall~{}i\geq 1$_,_ $\mathsf{hi}_{i}=\min(|D|,\sum^{i}_{k=1}c^{+}_{k})$.

  * •

$\mathsf{lo}_{1}=0$_, and_ $\forall~{}i\geq 2$,
$\mathsf{lo}_{i}=\sum^{i-1}_{k=1}\max(0,c^{-}_{k})$.

By this construction, all tuples $t\in D$ such that $t.A\in B_{i}$ will be
organized into the subset $D[\mathsf{idx}_{i}]\subseteq D$. This subset can be
quickly accessed if $D$ is already sorted, without the need for special data
structures or inclusion of dummy tuples. Depending on how bounding histograms
are constructed, $\textsc{SPEidx}(A,D)$ can support indexing lookups with
varying granularity. This can range from indexing individual attribute values
(where each $B_{i}$ corresponds to a single domain value) to indexing a range
of of values. The bounding histogram’s pessimistic estimation ensures that all
tuples where $t.A\in B_{i}$ are accurately contained within
$D[\mathsf{idx}_{i}]$, thereby achieving lossless indexing. In contrast to
existing methods that are limited to indexing base relations (Roy Chowdhury et
al., 2020; Bogatov et al., 2021; Zhang et al., 2023), SPEidx extends its
capabilities to create private indexes on query intermediate results. For
instance, consider $D^{\prime}\leftarrow\sigma_{A^{*}\in vals}(D)$ where the
attribute pair $(A^{*},A)$ is included in $\mathtt{synop}$. Here, SPEidx can
derive $\mathbf{H}(A,D^{\prime})$ from $\mathbf{H}(A^{*},D)$ and subsequently
build indexes on $D^{\prime}$. Importantly, since index creation is a post-
processing activity using available DP synopses, it incurs no additional
privacy loss.

Indexed store and fast data access IdxAcc. SPEidx enables the exploration of a
new storage layout for organizing outsourced data, namely indexed datastore,
that facilities private data access. Specifically, by analyzing a
representative workload $Q_{\mathsf{R}}$, one may identify the “hottest”
attribute per base relation, sort them according to the “hottest” attribute,
and then build indexes over the sorted data. This storage layout enables fast
indexed access (IdxAcc) to retrieve a compact subset of data from the
outsourced relations, thereby eliminating the need for a full table sequential
scan (SeqAcc) potentially bypassing selection operations (§ 5.3). We emphasize
that the SPECIAL design does not require replicating the outsourced datastore
to accommodate multiple query types (Bogatov et al., 2021; Zhang et al.,
2023). However, creating compact replicas (e.g., column replicas (Huang et
al., 2020) over frequently queried attributes) can be optionally employed to
enhance query processing speed. Moreover, the generation of all aforementioned
objects (indexed store and column replicas) requires only three primitives:
projection, oblivious sorting, and SPEidx, all achieved without extra privacy
loss. In other words, this implies that one can selectively adjust these
objects to align with dynamic query workloads, without incurring any privacy
costs.

###  5.3. SPECIAL Operators SPEop

We introduce SPEop, a set of novel synopsis-assisted operators that maintain
full obliviousness (e.g., operators’ execution cause no privacy loss) while
enabling lossless compaction. To our knowledge, SPEop is the first primitive
of its kind in any SCA system.

Oblivious compaction: OPAC. We first introduce the fundamental operation of
oblivious compaction, a key component for many SPEop primitives. Given input
$\langle R\rangle$, OPAC sorts it based on the secret bit $\mathsf{ret}$,
moving tuples with $\mathsf{ret}=$ ‘1’ to the front. Then, OPAC retains only
the first $k$ tuples from the sorted array. The compaction is lossless if $k$
is greater than or equal to the number of tuples with $\mathsf{ret}=$ ‘1’;
otherwise, it is lossy.

SPECIAL selections: (OP)SELECT, (SP)SELECT, (DC)SELECT. Let $R$ to be a
relation and $A\in attr(R)$, we now introduce three advanced selections that
implements $\sigma_{A\in vals}(R)$.

Algorithm 2 $\mathtt{CardEst}(\sigma_{A\in vals}(R),\mathtt{synop})$

1:$\mathbf{h}=\emptyset$, $c=0$

2:if $\mathbf{H}(A,R)\in\mathtt{synop}$ then
$\mathbf{h}\leftarrow\mathbf{h}^{+}\in\mathbf{H}(A,R)$

3:else if $\exists~{}\mathsf{pair}\in\mathtt{synop}$, s.t. $A\in\mathsf{pair}$
then

4: $\mathbf{h}\leftarrow$ marginal sum $\mathbf{h}^{+}\in\mathbf{H}(A,R)$ over
$\left(\mathsf{pair}\setminus A\right)$.

5:else return $cs=|R|$

6:return $cs=\min(|R|,\sum_{i=1}^{m}c_{i}\in\mathbf{h}:\left(B_{m}\cap
vals\neq\emptyset\right))$

(OP)SELECT. is mainly implemented based on the oblivious compaction (OPAC)
operation. Specifically, the operation first conducts a standard SELECT on the
input secure array $\langle R\rangle$ to label selected tuples, followed by an
OPAC to to eliminate a large portion of non-matching tuples. To determine the
compaction size $cs$, (OP)SELECT examines the synopsis of $R$ and
pessimistically estimates the cardinality of $\sigma_{A\in vals}(R)$ as shown
in Algorithm 2. Since $cs$ never underestimates the actual cardinality, and
thus, the compaction is lossless with no missing tuples. Moreover, as OPAC is
fully oblivious and $cs$ is determined completely from post-processing over DP
synopsis, thus, (OP)SELECT causes no privacy loss.

(SP)SELECT. The running complexity of (OP)SELECT depends on OPAC, which is
typically linearithmic (see § 6.1 or (Sasy et al., 2022)). However, when
$\mathtt{CardEst}(\sigma_{A\in vals}(R),\mathtt{synop})$ is relatively small,
oblivious selection can be achieved without necessarily incurring linearithmic
cost. Specifically, we consider (SP)SELECT, which first creates an empty
output array $\langle R_{o}\rangle$ with size equals to $cs$ before any
computations. Next, it evaluates two linear scans over $\langle R\rangle$,
where the first scan obliviously marks all selected tuples, and in the second
scan, it privately writes all marked tuples into $\langle R_{o}\rangle$.
Specifically, in the second scan, (SP)SELECT internally maintains the last
actual write position $\mathsf{idx}$ in $\langle R_{o}\rangle$. Then for every
newly accessed tuple $\langle t\rangle$ in $\langle D\rangle$, a write action
occurs on all tuples in $\langle R_{o}\rangle$. If $\langle t\rangle$ is
selected, then an actual write is made that writes $\langle t\rangle$ to
$\langle R_{o}[\mathsf{idx}+1]\rangle$ and a dummy write333In the context of
the secret-shared secure array $\langle\mathbf{a}\rangle$, a dummy write to
$\langle\mathbf{a}[i]\rangle$ is simply a re-sharing of $\mathbf{a}[i]$
through secure protocols without changing its value. is made to elsewhere. If
not, dummy writes are made throughout $\langle R_{o}\rangle$. Similarly,
(SP)SELECT does not yield additional privacy loss, and the complexity is
linear in its input.

(DC)SELECT. Finally, if the underlying data is already indexable on $A$, a
direct selection over the data can be applied that bypasses secure
computations. The operator simply looks up $\textsc{SPEidx}(A,R)$, and
accesses $R[a,b]$, where
$a=\min_{i}(\mathsf{idx}_{i}.\mathsf{lo}),b=\max_{i}(\mathsf{idx}_{i}.\mathsf{hi})$,
where $\mathsf{idx}_{i}$ dentoes the index in $\textsc{SPEidx}(A,R)$ where
$B_{i}\cap vals\neq\emptyset$.

SPECIAL join: (MX)JOIN. We now introduce a novel MF-Index based oblivious join
operation. The advancements of (MX)JOIN stand out in two key aspects compared
to existing oblivious joins. First, compared to the standard JOIN, (MX)JOIN
stands out for its ability to significantly compact the output size, coupled
with a highly parallelizable fast processing mode. Second, existing oblivious
joins with DP leakages typically require additional privacy budget to learn
join sensitivity (Dong et al., 2022) or necessitate truncations on joined
tuples (Wang et al., 2022; Bater et al., 2018). Moreover, (MX)JOIN is unique
as the first oblivious join that enables lossless output compaction without
extra privacy loss. We illustrate the construction details in Algorithm 3.

Algorithm 3 (MX)JOIN (base and pre-filtered relations)

1:Input: relations $R_{0}$, $R_{1}$; join attribute $A_{\mathsf{j}}$.

2:if $\mathsf{MXReady}(R_{0},R_{1})==\mathsf{True}$ then
$\mathsf{BucketJoin}(R_{0},R_{1},A_{\mathsf{j}})$

3:else if $R_{0}$, $R_{1}$ are either base or pre-filtered relation then

4: for $b\in\\{0,1\\}$ do

5: derive $\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{b})$ from
$\mathtt{synop}_{b}$ (§ 4)

6: build index
$\textsc{SPEidx}(A_{\mathsf{j}},R_{b})=\\{\mathsf{idx}_{i}\\}_{i=1,..,m}$ (§
5.2)

7: if $\forall b~{}$, $\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{b})$, and
$\textsc{SPEidx}(A_{\mathsf{j}},R_{b})\neq\mathsf{null}$ then

8: oblivious sort $R_{0}$, $R_{1}$ on $A_{\mathsf{j}}$,
$\mathsf{BucketJoin}(R_{0},R_{1},A_{\mathsf{j}})$

9: else assert “not applicable for (MX)JOIN”

10:$\mathsf{BucketJoin}(R_{0},R_{1},A_{\mathsf{j}})$:

11:for $i=1,2,...,m$ do

12: compute
$O_{i}\leftarrow(R_{0}[\mathsf{idx}_{i}]\Join_{A_{\mathsf{j}}}R_{1}[\mathsf{idx}_{i}])$
via basic JOIN

13:
$cs_{i}\leftarrow\min\left(\frac{|R_{0}[\mathsf{idx}_{i}]|}{\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{0})},\frac{|R_{1}[\mathsf{idx}_{i}]|}{\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{1})}\right)\times{\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{0})}\cdot{\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{1})}$

14: $R_{\mathsf{out}}\leftarrow
R_{\mathsf{out}}\cup{\texttt{OPAC}}(O_{i},cs_{i})$

15:return $R_{\mathsf{out}}$

In general, (MX)JOIN can be applied to two types of data: the base and pre-
filtered relations where the join key attribute is contained by the synopses.
Specifically, (MX)JOIN starts with computing the join key MFs (Alg 3:4) and
constructing private indexes (Alg 3:5) for both inputs. All these operations
are conducted through “privacy cost-free” transformations using available DP
synopses. Once these objects are obtained, the algorithm employs oblivious
sort to rearrange both inputs (Alg 3:6,7), rendering them indexable with
tuples logically distributed into independent buckets by join key values.
Next, (MX)JOIN simply adopts standard JOIN to join tuples exclusively within
the same buckets (Alg 3:10). Finally, (MX)JOIN performs per-bucket output
compaction, where it first determines the _MF join bound_ (Hertzschuch et al.,
2021) for each bucket join and invokes OPAC to compact the output according to
the learned size (Alg 3:11,12). As bucket-wise operations are independent, the
aforementioned steps lend themselves well to parallelized processing. For
better illustration, we visualize (MX)JOIN’s processing flow in Figure 3.

Figure 3. Example processing flow of (MX)JOIN.

Since (MX)JOIN derives join compaction sizes completely from post-processing
of DP synopses, it thus incurs no extra privacy loss. Moreover this design
choice also eliminates the need for computing join sensitivities — a major
hurdle in existing — as accurate join sensitivity estimation is hard and
typically requires a significant privacy budget (Dong et al., 2022).
Additionally, the noisy MF bounds guarantee that compaction sizes are
consistently overestimated, ensuring lossless compaction of join results.

##  6\. SPECIAL Planner

A major limitation of existing DPSCA designs is sub-optimal execution
planning. Without the ability to pre-estimate intermediate result sizes,
traditional methods cannot identify the most efficient execution strategies.
To address this, SPECIAL employs an innovative query planner that leverages
available synopses for plan size estimation, enabling optimal execution
planning.

At a high level, our planner is modeled on the Selinger-style (cost-based)
optimizer (Blasgen et al., 1981). It uses a bottom-up, dynamic programming
approach to enumerate all equivalent secure execution plans for a given query
and estimate their costs to select the optimal one. However, challenges in the
design space still remain. First, the introduction of SPECIAL primitives can
significantly impact the cost modeling for oblivious operations, rendering
existing models (Bater et al., 2018; Liagouris et al., 2023) ineffective.
Additionally, the equivalent plan search space is extensive, requiring further
strategies to simplify the search space. To address these challenges, we first
conduct a comprehensive analysis of the complexities of SPECIAL primitives and
develop a new cost model (§ 6.1) for SPECIAL planner. Next, we design
protocol-specific heuristics (§ 6.2) tailored for the SPECIAL planner to
simplify the plan search space. Note that existing features of the Selinger-
style optimizer, such as plan enumerations, are not within our contributions.
For detailed understanding of these features, we encourage readers to explore
the original _IBM System R_ paper (Blasgen et al., 1981).

###  6.1. Cost Model

Similar to the cost model proposed by Shrinkwrap (Bater et al., 2018), we view
the cost of a secure execution plan cost as a combination of each operator’s
I/O and secure evaluation costs. In addition, we formulate these costs as
functions over their processed data sizes. Specifically, given a plan with
$\ell$ operators, $\mathsf{op}_{1},...,\mathsf{op}_{\ell}$, and let
$\mathbf{I}=\\{{I}_{1},...,{I}_{\ell}\\}$,
$\mathbf{O}=\\{{O}_{1},...,{O}_{\ell}\\}$, to be the input and output sizes of
each operators. The plan cost is formulated as:

(5)
$\mathsf{Cost}=\textstyle\sum_{i=1}^{\ell}C^{\mathsf{op}_{i}}_{\mathsf{in}}(I_{i})+C_{\mathsf{eval}}^{\mathsf{op}_{i}}(I_{i})+C^{\mathsf{op}_{i}}_{\mathsf{out}}(O_{i})$

Here, $C_{\mathsf{in}}$ represents the data access cost (input I/O), primarily
capturing the expenses when moving data from persistent storage to an in-
memory secure array. If the accessed data has already loaded into memory,
$C_{\mathsf{in}}$ becomes negligible. $C_{\mathsf{out}}$ denotes the output
I/O cost, modeling the expenses when writing operator results into output
arrays. $C_{\mathsf{eval}}$ accounts for the secure computing expenses for
evaluating each operators, typically constituting the dominant cost. Note
that, in practice, the exact formulas for $C_{\mathsf{in}},C_{\mathsf{out}}$,
and $C_{\mathsf{eval}}$ can vary depending on the specific secure protocol
employed (garbled circuits (Yao, 1986), secret sharing (Micali et al., 1987),
etc.) as well as the particular hardware configurations in use. Nonetheless,
the understanding of the asymptotic costs is adequate for comprehending the
principles of our query planning and optimization strategies (Liagouris et
al., 2023; Bater et al., 2018). In what follows, we provide detailed analysis
on the asymptotic costs for each SPECIAL operator. Similarly, we assume that
all input data sizes mentioned henceforth in this section are of size $n$, and
all 1D histograms have $m$ bins. Table 1 summarizes the operator costs.

Table 1. Asymptotic costs for secure operators

Operator | Input I/O ($C_{\mathsf{in}}$) | Eval. ($C_{\mathsf{eval}}$) | Output I/O ($C_{\mathsf{out}}$)
---|---|---|---
PROJECT | $O(n)$ | N/A | $O(n)$
Agg. | $O(n)$ | $O(n)$ | $O(1)$
Group & Order | $O(n)$ | $O(n\log^{2}n)$ | $O(n)$
SELECT | $O(n)$ | $O(n)$ | $O(n)$
(OP)SELECT | $O(n)$ | $O(n\log n)$ | $\mathsf{hist\\_bound}$
(SP)SELECT | $O(n)$ | $O(n)$ | $O(1)$
(DC)SELECT | $\mathsf{idx\\_bound}$ | N/A | N/A
JOIN | $O(n)$ | $O(n^{2})$ | $O(n^{2})$
(MX)JOIN | $O(n)$ | $O(n^{2})^{*}$ | $\mathsf{mf\\_bound}$

∗Assuming the maximum size of the indexed buckets is bounded by
$O(\frac{n}{\log n})$.

Oblivious sorting and compaction. Oblivious sorting and compaction (OPAC) are
crucial for many SPEop operators, so we will begin our analysis with these two
primitives. While oblivious sorting algorithms with optimal $O(n\log n)$
complexity exist, they often necessitate either impractically large constants
(Ajtai et al., 1983; Goodrich, 2014) or client-side memory (Asharov et al.,
2020), both do not fit with SCA scenario. Consequently, we will consider the
well-established bitonic sorting based implementation for oblivious sort,
which come with $O(n\log^{2}n)$ complexity. Nonetheless, efficient OPAC
implementations with $O(n\log n)$ complexity remain achievable (Sasy et al.,
2022)

Projection, grouping and aggregation. The PROJECT accesses private relations
and discards unnecessary columns independently on each server, without secure
computations. Thus, I/O costs dominate this operation, with both input and
output costs bounded by $O(n)$. The costs of ORDER-BY, DISTINCT, and GROUP-BY
are primarily due to oblivious sorting, resulting in a complexity of
$O(n\log^{2}n)$. Additionally, as these operators do not reduce output sizes,
both $C_{\mathsf{in}}$ and $C_{\mathsf{out}}$ are bounded by $O(n)$. Finally,
the cost of aggregations, i.e. COUNT, SUM, and MIN/MAX subjects to a oblivious
linear scan, typically outputting a single secret-shared value. Hence, its
$C_{\mathsf{eval}}$ is bounded by $O(n)$, with $C_{\mathsf{in}}$ at $O(n)$ and
$C_{\mathsf{out}}$ at $O(1)$.

Selections. The primary cost of SELECT stems from an oblivious linear scan,
making $C_{\mathsf{eval}}$ within $O(n)$. Since SELECT does not shrink the
output size, both $C_{\mathsf{in}}$ and $C_{\mathsf{out}}$ are within $O(n)$.
(OP)SELECT requires an oblivious compaction (OPAC) before writing outputs,
where OPAC usually yields an $O(n\log n)$ complexity (Sasy et al., 2022).
Consequently, its $C_{\mathsf{eval}}$ is bounded by $O(n\log n)$ with input
I/O cost same as SELECT. However, as (OP)SELECT compacts output size,
$C_{\mathsf{out}}$ is reduced to $\mathsf{hist\\_bound}=O\left(\sum_{B_{i}\cap
vals\neq\emptyset}|B_{i}|\right)$, where $B_{i}\cap vals\neq\emptyset$ are
bins in the synopsis histogram intersecting with selection conditions. If
$\sum_{B_{i}\cap vals\neq\emptyset}|B_{i}|\sim O(1)$, (SP)SELECT becomes
preferable, with its running cost dominated by a two-phase linear scan, and
thus $C_{\mathsf{eval}}$ is now $O(n)$, and the output cost is $O(1)$.
(DC)SELECT is the most efficient selection, though it requires indexable input
data. It simply loads indexed data into secure arrays without secure
computations or result write-backs. As such, both $C_{\mathsf{evals}}$ and
$C_{\mathsf{out}}$ are negligible, with $C_{\mathsf{in}}$ within
$\mathsf{idx\\_bound}=O\left(\max_{i}(\mathsf{idx}_{i}.\mathsf{hi})-\min_{i}(\mathsf{idx}_{i}.\mathsf{lo})\right)$.
Here, $\mathsf{idx}_{i}$ are indexed regions that intersect with selection
conditions.

Joins. Both JOIN and (MX)JOIN have $O(n)$ data access costs, but differ in
$C_{\mathsf{eval}}$ and $C_{\mathsf{out}}$. JOIN, using a Cartesian product
approach, doesn’t reduce output size, so both $C_{\mathsf{eval}}$ and
$C_{\mathsf{out}}$ are within $O(n^{2})$. Compared to JOIN, in the worst-case
scenario where the join keys follow a highly biased distribution, i.e. max
bucket size reaches $O(n)$, (MX)JOIN’s asymptotic cost is at most $O(n^{2}\log
n)$. However, when join keys are distributed more uniformly, the cost can be
asymptotically better. For instance, with $m=\log n$ and assuming a max bucket
size of $O(\frac{n}{\log n})$, each bucket join costs $O(\frac{n^{2}}{\log
n})$, leading to a total cost of $O(n^{2})$, equivalent to JOIN. Recall that
bucket joins in (MX)JOIN can be executed concurrently, hence, the processing
latency is indeed dominated by the bucket-wise cost, i.e. $O(\frac{n^{2}}{\log
n})$. Additionally, the output cost is lowered from $O(n^{2})$ to the sum of
per-bucket MF upper bounds (Alg 3:11), which can be substantially less if the
join key MFs are relatively low.

###  6.2. Heuristics

H-1. Filter push down. Filter pushdown is a widely used optimization technique
in conventional databases, where it involves moving the selection operation to
the earliest stage in the data processing pipeline, such as directly to the
base relation. This reduces the amount of data that needs to be loaded,
transferred, and processed, by following operators especially complex joins.
However, in SCA designs, data obliviousness typically necessitates padding
selection sizes to the worst-case scenario, rendering filter pushdown
ineffective (Liagouris et al., 2023; Eskandarian and Zaharia, 2017; Zheng et
al., 2017; Poddar et al., 2021). With SPEop selections, the selection outputs
can be significantly compacted, making filter pushdown effective again.
Therefore, we include filter push down as one of the optimization heuristic
for SPEplan.

H-2. Predicates fusion. Let $R$ to be any relation,
$A_{1},A_{2},...,A_{k}\subseteq attr(D)$, and
$\mathbf{v}=\\{v_{1},v_{2},...,v_{k}\\}$. We say that for multiple selection
over $R$ such that $\sigma_{A_{1}\in v_{1}}(...\sigma_{A_{k}\in v_{k}}(R))$,
one can always fuse them into one selection
$\sigma_{\mathbf{A}\subset\mathbf{v}}(R)$. This can reduce the number of
secure computation invocations from $k$ rounds to just one. Additionally, the
selection size can be estimated as
$\min_{A_{i}}\left(\mathtt{CardEst}(\sigma_{A_{i}\in v_{i}}(R))\right)$.

H-3. Join statistics propagation. A key property of SPECIAL join, (MX)JOIN, is
that the output is already indexed and bucketized by the join key. Therefore,
for any output $R$ of (MX)JOIN computing $R_{0}\Join_{A_{\mathsf{j}}}R_{1}$, a
new index $\textsc{SPEidx}(A_{\mathsf{j}},R)$ across $R$ can be easily
derived. Moreover, as per (Hertzschuch et al., 2021), one can also update the
MF for $R$ by computing
$\widehat{\mathtt{mf}}(A_{\mathsf{j}},R)=\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{0})\times\widehat{\mathtt{mf}}(A_{\mathsf{j}},R_{1})$.
As a result, we say that the output of (MX)JOIN as _MF-and-index-ready_ ,
enabling direct application of another (MX)JOIN on the same join attribute.

##  7\. Evaluation

In this section, we present evaluation results of our proposed framework.
Specifically, we address the following questions:

  * •

Question-1: Does SPECIAL offer efficiency advantages over current SCA
approaches? To what extent can SPECIAL enhance efficiency compared to existing
state-of-the-arts (SOTAs)?

  * •

Question-2: For the DP-based SPECIAL design, is there a trade-off between
privacy and efficiency? Can we adjust privacy levels to achieve various
efficiency objectives?

  * •

Question-3: Can SPECIAL scale complex analytical (e.g. multi-way join) queries
to large-scale (multi-million rows) datasets?

###  7.1. Experimental setups

We briefly outline our experimental setup, covering the baseline systems,
prototype SPECIAL implementation, workloads, datasets, and default
configurations.

Baseline systems and SPECIAL prototype. We compare SPECIAL with two baseline
systems: Shrinkwrap (Bater et al., 2018), the SOTA DPSCA, and SMCQL (Bater et
al., 2017), a typical SCA system using exhaustive padding for leakage hiding,
also used as a baseline for Shrinkwrap. For consistency, we consider the same
circuit-model implementations for both baseline systems and the SPECIAL
prototype. While some works (Poddar et al., 2021; Liagouris et al., 2023)
similar to SMCQL use exhaustive padding but improve efficiency through
protocol-level optimizations, we exclude them from our benchmarks for fair
comparison concerns. However, it’s important to note that these optimizations
are orthogonal to both the baseline systems and our designs. We re-implement
important query features for the two baseline systems, and built SPECIAL using
the same MPC package, specifically the sh2pc-0.2.2 protocol within
EMPtoolkit-0.2.5. Since managing DP synopses and generating indexes do not
involve secure computations, thus we implement the related features using
Python (3.7) scripts. All implementations are open-sourced (Lovingmage, 2024).

Datasets and workloads. Although SMCQL and Shrinkwrap use the HealthLNK
dataset, it is not public data and thus not accessible to the broader research
community. Hence, we developed a new benchmark based on a publicly available
dataset, and mimic Shrinkwrap’s workload to create a set of testing queries.
Specifically, we use the Czech Financial Dataset (Rel, [n.d.]), an anonymized
Czech bank transaction dataset for loan applications. This dataset comprises 8
relational tables with a total of 55 columns and 1.1 million rows. For scaling
experiments, we use the raw data and schema to generate synthetic data with up
to 10 million rows. Shrinkwrap’s benchmark evaluates four queries: a range
query, two 2 binary joins, and a 3-way join. Mirroring this approach, we
designed eight query workloads based on the Financial data. All workloads are
selection-projection-join (SPJ) queries followed by statistical aggregations
such as count, count distinct, and group by. The workloads range from simple
linear queries to complex multi-way joins. Due to space limitations, a brief
summary of the workloads is provided in Table 2, with the full specification
in Appendix B.

Table 2. Query workloads

Query No. | Type | Description
---|---|---
Q1 | Linear | Point query with single predicate.
Q2 | Linear | Range query with conjunctive predicates.
Q3 | Binary Join | Non-expanding binary join.
Q4 | Binary Join | Expanding binary join.
Q5 | Multi Join | 3-way mixed non-expanding and expanding joins.
Q6 | Multi Join | 3-way all expanding joins.
Q7 | Multi Join | 4-way mixed non-expanding and expanding joins.
Q8 | Multi Join | 5-way mixed non-expanding and expanding joins.

Default configurations. For SPECIAL, each relational table is assigned a fixed
privacy budget with $\epsilon=1.5$ and $\delta=0.00005$ to release synopses.
This setup ensures that the total privacy loss per table does not exceed
$\epsilon=1.5$. For all equal-width histograms generated in SPECIAL, we
configure them to have at most 8 bins. For Shrinkwrap, we use a privacy budget
of $\epsilon=1.5$ and $\delta=0.00005$ for each query processing, as specified
in (Bater et al., 2018). However, Shrinkwrap does not provide bounded privacy
loss guarantees, so the privacy guarantee of Shrinkwrap will be no better than
SPECIAL. We conduct all experiments on bare-metal Mac machines with M2 Max
CPUs and 96GB unified memory. In addition, we consider Q2, Q4, Q8 are default
testing queries in each query type, and are used as the representative
workload to guide synopses. Moreover, for baseline systems, as they do not
have join ordering optimizations, thus we will assume a random join order for
them.

Figure 4. In-depth comparisons in execution plans: (i) The exhaustive padding
in SMCQL can lead to significant memory blowup; (ii) Both SMCQL and Shrinkwrap
suffer from suboptimal join ordering; (iii) Although Shrinkwrap reduces
intermediate sizes, it still requires substantial memory to materialize the
Cartesian-style standard oblivious join; (iv) SPECIAL effectively identifies
optimal join orders and significantly reduces intermediate materialization
sizes; (v) The IdxAcc method in SPECIAL not only bypasses secure selections
but also directly reduces input I/O costs.

###  7.2. End-to-end performance comparisons

To address Question-1, we first conduct an end-to-end performance comparison
of SPECIAL, Shrinkwrap, and SMCQL across the full benchmark workloads (Q1-Q8).
We use two typical performance metrics, query execution time and memory usage
in our evaluations. The results are summarized in Figure 5 and Figure 6. Due
to significant memory consumption, SMCQL cannot complete the full benchmark
and stops at Q4. Therefore, we only include full statistics up to Q3, and for
Q4, we provide a projected performance evaluation using 10% of the input data.

Figure 5. End-to-end comparison: query latency Figure 6. End-to-end
comparison: memory usage

Observation 1. SPECIAL significantly outperforms all baseline systems in query
latency, achieving performance gains of up to $3618.3\times$ for linear
queries, $114\times$ for binary joins, and $80.3\times$ for multi-joins.
Figure 5 shows significant performance gains of SPECIAL in contrast to
Shrinkwrap and SMCQL. For linear queries, SPECIAL exhibits substantial
performance gains, achieving up to $3618.3\times$ improvement (Q2), primarily
due to its index-based fast data access. This approach not only reduces large
I/O costs but also eliminates the need for secure computation by enabling
direct data retrieval via DP indexes. We observe that in binary joins, SPECIAL
has a less pronounced advantage over Shrinkwrap. This is because Shrinkwrap do
not have sub-optimal planning issue when dealing with binary join—as there is
only one join order. Hence, the performance gains for SPECIAL in Q3 and Q4
stem solely from fast data access and the efficient (MX)Join method. However,
for more complex multi-way joins, SPECIAL’s advantage becomes more pronounced
again due to its ability to select the optimal join order. For instance,
Shrinkwrap shows more than $80\times$ slow down in query latency than SPECIAL
in group Q7.

Observation 2. SPECIAL shows profound improvement in memory usage (Figure 6)
against baseline systems, especially in complex multi-way joins. This is
primarily due to two factors: First, the (MX)JOIN used by SPECIAL is more
memory-efficient compared to the joins implemented by Shrinkwrap and SMCQL.
Second, SPECIAL’s capability to identify optimal execution plans significantly
reduces total intermediate sizes, which is particularly beneficial for complex
joins that suffer from sub-optimal or exhaustive padding in other systems. To
better understand the substantial improvements SPECIAL achieves—for instance,
up to $928.2\times$ over Shrinkwrap and more than $10^{5}\times$ over SMCQL—we
will zoom into a specific query, Q6, and compare the detailed execution plans
of the three systems. The choice of Q6 is strategic because its complexity
sufficiently highlights the differences in execution plans, yet it remains
simple enough for clear visual representation. Our comparison features four
execution plans: a plaintext optimal plan derived directly from the logical
plan using actual cardinalities, illustrating the ground truth optimal
execution; a hypothetical SMCQL plan (since Q6 cannot be completed by SMCQL so
we project the cardinalities); and two actual execution plans from our
experiments with Shrinkwrap and SPECIAL. The detailed comparisons and
observations are summarized in Figure 4.

###  7.3. Privacy comparisons

Continue to address Question-1, we now compare the privacy guarantees between
Shrinkwrap and SPECIAL, with the results detailed in Figure 7. As privacy loss
is independent of query types, our analysis will focus on comparing the
privacy composition curves under continual query answering for both Shrinkwrap
and SPECIAL. We consider two privacy composition models: advanced composition
(Adv.)(Dwork et al., 2014) and concentrated DP composition (CDP)(Bun and
Steinke, 2016).

Figure 7. End-to-end comparison privacy loss.

Observation 3. Under continual query answering, SPECIAL demonstrates
significantly lower privacy loss compared to Shrinkwrap, achieving up to
$89.01\times$ and $38.91\times$ improvements in the Adv. and CDP modes,
respectively. The privacy loss of SPECIAL is bounded to the initial synopsis
release stage, so continual query answering does not incur additional privacy
loss. In contrast, Shrinkwrap’s privacy loss accumulates over time as each new
query allocates a fresh privacy budget. Consequently, its privacy loss
exhibits a logarithmic growth, as shown in Figure 7. This accumulation can
result in significant privacy degradation when processing a large number of
queries. For example, answering 100 queries in Shrinkwrap could result in a
privacy loss of $\epsilon>100$ in Adv. and $\epsilon\approx 60$ in CDP.,
respecitvely, even if each query only uses a small privacy budget of
$\epsilon=1.5$. As such, SPECIAL demonstrate significant improve in privacy
guarantees towards SOTA DPSCA.

###  7.4. Privacy efficiency tradeoffs

We address Question-2 by evaluating SPECIAL at various privacy levels and
observing the performance impacts. Specifically, we maintain $\delta$ constant
while varying $\epsilon$ from $0.1$ to $10$ and assess the performance across
default testing queries (Q2, Q4, Q8). The results are shown in Figure 8 and
Figure 9.

Figure 8. Privacy vs. Performance (query time) Figure 9. Privacy vs.
Performance (memory)

Observation 4. The privacy-efficiency tradeoff generally exists but exhibits
varying trends at different privacy levels. For instance, SPECIAL shows a
clear tradeoff at higher privacy levels ($\epsilon<1$), while at lower privacy
levels ($\epsilon>1$), the tradeoff becomes less pronounced. When $\epsilon$
increases from $0.1$ to $1$, both memory usage and query latency for all test
queries significantly decrease. However, increasing $\epsilon$ from $1$ to
$10$ shows no significant performance gains. This may indicate that once
$\epsilon$ exceeds $1$, the impact of noises on cardinality estimation or
index building is alredy minimal, and further reductions in $\epsilon$ do not
lead to notable improvements. Therefore, if high privacy protection is
required, practitioners should carefully fine-tune privacy parameters to
optimize performance. Conversely, if performance is the priority, setting
$\epsilon$ near 1 is typically sufficient.

Observation 5. Different queries exhibit varying performance sensitivities to
changes in privacy levels. Multi-join queries are significantly affected when
privacy levels change. For instance, the performance overhead of Q8 at
$\epsilon=0.1$ is more than $3\times$ higher than at $\epsilon=1$. In
contrast, linear query (Q2) and binary join (Q4) overhead increases to only
about $1.5\times$ under the same privacy settings. This difference stems from
the error amplification inherent in multi-join operations, which frequently
reuse synopses and require multiple cardinality estimations. Therefore,
practitioners dealing with complex multi-join workloads may need careful fine-
tune privacy parameters, as performance impacts can be substantial.

###  7.5. Scaling experiments

To address Question-3, we stress SPECIAL with scaled workloads by duplicating
the raw financial dataset to sizes of $2\times$, $4\times$, and $8\times$. We
then evaluate the default testing queries on these scaled datasets to assess
SPECIAL’s efficiency. The results are shown in Figure 10.

Figure 10. End-to-end comparison privacy loss.

Observation 6. SPECIAL demonstrates significant potential to scale up to
multi-million records, even when handling complex 5-way joins. Figure 10 shows
SPECIAL’s effective scaling: up to $8\times$ data for linear queries and
binary joins, and up to $4\times$ data for complex 5-way joins like Q8. For
instance, Q2 can be completed within 290ms under $8\times$, and in fact, since
selection is bypassed (due to index access), thus the cost is mainly on I/O
costs. Q4 finishes in 289 minutes at the same scale $8\times$, while the more
complex 5-way join Q8 takes less than 280 minutes for $4\times$ data. As a
reference, Shrinkwrap would require over 1035 minutes to complete Q8 even with
unscaled data (Figure 5). This result can, from another angle, showcase the
significant performance improvements of SPECIAL over current SOTA DPSCA
designs.

##  8\. Discussion

In this section, we discuss potential extensions to accommodate broader data
models and possible adaptations of SPECIAL designs to other secure primitives.

Supporting growing data. In general SPECIAL considers read-intensive
analytical workloads and and a static data model, which is the same as current
SOTA SCA efforts (Poddar et al., 2021; Bater et al., 2018; Liagouris et al.,
2023; Volgushev et al., 2019). In this section, we will briefly discuss how
SPECIAL could be extended to support the growing data model where new records
are continuously added to the logical database (Wang et al., 2022, 2021; Zhang
et al., 2023). One possible strategy involves segmenting the large logical
database into discrete, non-overlapping time intervals, each represented by
its own database with independent synopses. Specifically, for new incoming
data, SPECIAL will initially cache it until a designated time interval
concludes. After this period, SPECIAL will batch all the cached data into a
new database corresponding to the past time interval and release synopses for
this database. As the data within these intervals is disjoint, queries can be
easily partitioned and independently optimized and executed across
corresponding databases in parallel, before being aggregated. Note that prior
to releasing new synopses, all cached data will be processed using standard
SCA processing (e.g. SMCQL). Since each synopses release covers only newly
inserted data, the total privacy loss adheres to parallel composition (Dwork
et al., 2014), and thus the bounded privacy loss still hold.

Adaptability to other secure primitives. Beyond MPC-based SCA, the key design
insights from SPECIAL are transferable to other secure outsourced databases
such as the TEE-based analytical systems (Qiu et al., [n.d.]; Qin et al.,
2022; Eskandarian and Zaharia, 2017; Zheng et al., 2017) or searchable
encryption based private key-value store (Amjad et al., 2021; Groce et al.,
2019; Chen et al., 2018). This is because SPECIAL’s core components, including
synopses management, indexing, query planning, and compaction estimation, can
all be executed without relying on secure computation primitives. For example,
in TEE databases, one may conduct a similar query planning outside the TEE,
with the optimal plan then executed within the TEE for fast oblivious
processing. Similarly, SPECIAL’s design principles could be applied to
searchable encryption to construct private indexes in advance on sorted data,
enable fast and private information retrieval.

##  9\. Related Work

SCA systems. Two main approaches exist for designing MPC-based SCA systems.
The first is peer-to-peer paradigm (Aggarwal et al., 2005; Mouris et al.,
2024; Poddar et al., 2021; Volgushev et al., 2019; Wang and Yi, 2021), where
the goal is to improve efficiency by decomposing analytical queries and
pushing them to data owners, so that they can either directly process in clear
or running MPCs across a smaller group of parties. Unfortunately, this
approach burdens data owners with heavy computational overheads, particularly
for complex operations like joins. Moreover, given real-world data owners
often lack robust computing resources and reliable service capabilities, these
methods are difficult to scale and promise consistent SCA services to external
analysts. On the other hand, the server-aided-MPC model (Wang et al., 2021;
Bater et al., 2018, 2020; Wang et al., 2022; Zhang et al., 2023; Roy Chowdhury
et al., 2020; Kamara et al., 2011; Tan et al., 2021; Knott et al., 2021;
Liagouris et al., 2023; Mohassel and Zhang, 2017) offers a more practical
solution. It allows data owners to outsource both expensive MPC computations
and secure data storage to a set of capable cloud service providers (CSPs),
who then jointly evaluate MPC to provide reliable SCA services. For the
SPECIAL prototype, we focus on the server-aided-MPC model under a strong
corruption assumption, allowing up to $n-1$ of $n$ servers to be compromised
and collate with others. While, as we discussed before, SPECIAL’s core design
principles are protocol-agnostic. This enables interoperability with various
MPC models, including the peer-to-peer settings or a weaker corruption setting
(for performance purpose) where a supermajority of servers need to be honest
(Tan et al., 2021; Knott et al., 2021; Liagouris et al., 2023).

DP leakages. Leakage-abuse attacks (Cash et al., 2015; Kellaris et al., 2016;
Blackstone et al., 2019; Oya and Kerschbaum, 2021; Grubbs et al., 2018; Shang
et al., 2021; Zhang et al., 2016), exploit data-dependent processing patterns,
are persistent threats to SCA systems. To mitigate these risks, oblivious
computation techniques (Keller and Scholl, 2014; Pinkas and Reinman, 2010;
Stefanov et al., 2011; Chang et al., 2022; Mishra et al., 2018; Crooks et al.,
2018; Jönsson et al., 2011; Sasy et al., 2022; Asharov et al., 2020; Wang et
al., 2014; Pettai and Laud, 2015; Wang et al., 2023; Tinoco et al., 2023) have
become the de facto solution—processing data such that the entire execution
transcript (e.g. memory traces and read/write volumes) is padded to a worst-
case constant. While these techniques ensure the strongest privacy guarantees
by eliminating data-dependent leakages, they also introduce a fundamental
contention with modern database optimizations, which often rely heavily on
data-dependent operations (Bater et al., 2018; Wang et al., 2021; Wagh et al.,
2021; Wang et al., 2022). To this end, many recent efforts seek a practical
balance in the privacy-performance trade-off by allowing controlled leakage
under DP (Bater et al., 2018; Wang et al., 2021; Wagh et al., 2021; Wang et
al., 2022; Groce et al., 2019; He et al., 2017; Zhang et al., 2023; Qin et
al., 2022; Chan et al., 2022; Wagh et al., 2016; Chu et al., 2021; Qiu et al.,
[n.d.]; Patel et al., 2019). However, a common issue of these approaches is
unbounded privacy loss. While some works propose to address this (Zhang et
al., 2023; Bogatov et al., 2021; Qiu et al., [n.d.]), their approaches are
restricted to only simple linear queries. Furthermore, existing DP leakage
designs also lack lossless guarantees for complex query processing. The
inherent randomness of DP noises (Wang et al., 2021; Groce et al., 2019; Wang
et al., 2022) and uncertainty in complex join sensitivities (Chu et al., 2021;
Bater et al., 2018; Wang et al., 2022) often lead to improper output
compaction and lose tuples. SPECIAL addresses all these limitations together,
and to our knowledge, is the first system to ensure both bounded privacy and
lossless results for securely processing complex queries.

SCA query planning. Query planning (Silberschatz et al., 2011) is crucial in
conventional databases. A few studies (Bater et al., 2017; Volgushev et al.,
2019; Poddar et al., 2021; Liagouris et al., 2023) explored query planning
within SCA frameworks. Unlike conventional planners, which exploit size
disparities across different execution plans to choose the most efficient one
with minimized plan sizes (Elmasri et al., 2020; Harmouch and Naumann, 2017;
Han et al., 2021), these methods typically prohibit the use of such data-
dependent information. Consequently, they primarily rely on data-independent
metrics for planning. For example, (Bater et al., 2017; Liagouris et al.,
2023; Volgushev et al., 2019) optimize based on the MPC execution costs, while
(Poddar et al., 2021) focuses on decomposing large MPC tasks into smaller
2/3PC ones. Since these methods do not optimize or compact intermediate sizes,
significant query execution overhead from these large sizes remains evident,
especially when processing complex multi-joins (Bater et al., 2018; Liagouris
et al., 2023). Shrinkwrap (Bater et al., 2018) uses DP leakage models and
allows planner to optimize query intermediate sizes in a privacy-preserving
manner. However, it cannot estimate cardinalities before runtime, mandating a
random selection of plan structures (e.g. join order) before execution.
Consequently, planning focuses solely on optimally allocating privacy budgets
across the chosen plan, which often result in suboptimal query executions. In
contrast, SPECIAL offers an advanced query planner capable of pre-estimating
plan sizes and comparing costs among different plan structures before
execution.

##  10\. Conclusion

We introduce SPECIAL, the first SCA system that simultaneously supports: (i)
handling complex queries with bounded privacy loss; (ii) advanced query
planning that effectively exploit plan intermediate sizes before runtime; and
(iii) delivering exact query results without missing tuples. This is achieved
through a novel synopses-assisted SCA design, where a set of private table
statistics are released with one-time privacy cost to guide subsequent secure
SCA planning and processing. The benchmark results demonstrate that SPECIAL
significantly outperforms SOTA SCA systems and scales complex multi-join
queries to multi-million datasets

## References

  * (1)
  * Rel ([n.d.]) [n.d.].  Financial Dataset.  https://relational-data.org/dataset/Financial.  Accessed: 2024-03-30.
  * Aggarwal et al. (2005) Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina, Krishnaram Kenthapadi, Rajeev Motwani, Utkarsh Srivastava, Dilys Thomas, and Ying Xu. 2005.  Two Can Keep A Secret: A Distributed Architecture for Secure Database Services.. In _CIDR_ , Vol. 2005. 186–199.
  * Ajtai et al. (1983) Miklós Ajtai, János Komlós, and Endre Szemerédi. 1983.  An 0 (n log n) sorting network. In _Proceedings of the fifteenth annual ACM symposium on Theory of computing_. 1–9.
  * Amjad et al. (2021) Ghous Amjad, Sarvar Patel, Giuseppe Persiano, Kevin Yeo, and Moti Yung. 2021.  Dynamic volume-hiding encrypted multi-maps with applications to searchable encryption.  _Cryptology ePrint Archive_ (2021).
  * Araki et al. (2016) Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. 2016.  High-throughput semi-honest secure three-party computation with an honest majority. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_. 805–817.
  * Asharov et al. (2020) Gilad Asharov, TH Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2020.  Bucket oblivious sort: An extremely simple oblivious sort. In _Symposium on Simplicity in Algorithms_. SIAM, 8–14.
  * Batcher (1968) Kenneth E Batcher. 1968.  Sorting networks and their applications. In _Proceedings of the April 30–May 2, 1968, spring joint computer conference_. 307–314.
  * Bater et al. (2017) Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel N Kho, and Jennie Rogers. 2017.  SMCQL: Secure Query Processing for Private Data Networks.  _Proc. VLDB Endow._ 10, 6 (2017), 673–684.
  * Bater et al. (2018) Johes Bater, Xi He, William Ehrich, Ashwin Machanavajjhala, and Jennie Rogers. 2018.  Shrinkwrap: efficient sql query processing in differentially private data federations.  _Proceedings of the VLDB Endowment_ 12, 3 (2018).
  * Bater et al. (2020) Johes Bater, Yongjoo Park, Xi He, Xiao Wang, and Jennie Rogers. 2020.  Saqe: practical privacy-preserving approximate query processing for data federations.  _Proceedings of the VLDB Endowment_ 13, 12 (2020), 2691–2705.
  * Ben-Or et al. (2019) Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 2019.  Completeness theorems for non-cryptographic fault-tolerant distributed computation.  In _Providing sound foundations for cryptography: on the work of Shafi Goldwasser and Silvio Micali_. 351–371.
  * Blackstone et al. (2019) Laura Blackstone, Seny Kamara, and Tarik Moataz. 2019.  Revisiting leakage abuse attacks.  _Cryptology ePrint Archive_ (2019).
  * Blasgen et al. (1981) Mike W Blasgen, Morton M Astrahan, Donald D Chamberlin, JN Gray, WF King, Bruce G Lindsay, Raymond A Lorie, James W Mehl, Thomas G Price, Gianfranco R Putzolu, et al. 1981\.  System R: An architectural overview.  _IBM systems journal_ 20, 1 (1981), 41–62.
  * Bogatov et al. (2021) Dmytro Bogatov, Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O’Neill. 2021.  Epsolute: E iciently erying Databases While Providing Differential Privacy.  (2021).
  * Bun and Steinke (2016) Mark Bun and Thomas Steinke. 2016.  Concentrated differential privacy: Simplifications, extensions, and lower bounds. In _Theory of Cryptography Conference_. Springer, 635–658.
  * Cash et al. (2015) David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. 2015.  Leakage-abuse attacks against searchable encryption. In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_. 668–679.
  * Chan et al. (2022) T-H Hubert Chan, Kai-Min Chung, Bruce Maggs, and Elaine Shi. 2022.  Foundations of differentially oblivious algorithms.  _ACM Journal of the ACM (JACM)_ 69, 4 (2022), 1–49.
  * Chang et al. (2022) Zhao Chang, Dong Xie, Sheng Wang, and Feifei Li. 2022.  Towards Practical Oblivious Join. In _Proceedings of the 2022 International Conference on Management of Data_. 803–817.
  * Chen et al. (2018) Guoxing Chen, Ten-Hwang Lai, Michael K Reiter, and Yinqian Zhang. 2018.  Differentially private access patterns for searchable symmetric encryption. In _IEEE INFOCOM 2018-IEEE conference on computer communications_. IEEE, 810–818.
  * Chu et al. (2021) Shumo Chu, Danyang Zhuo, Elaine Shi, and TH Hubert Chan. 2021.  Differentially oblivious database joins: Overcoming the worst-case curse of fully oblivious algorithms.  _Cryptology ePrint Archive_ (2021).
  * Crooks et al. (2018) Natacha Crooks, Matthew Burke, Ethan Cecchetti, Sitar Harel, Rachit Agarwal, and Lorenzo Alvisi. 2018.  Obladi: Oblivious serializable transactions in the cloud. In _13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)_. 727–743.
  * Dong et al. (2022) Wei Dong, Juanru Fang, Ke Yi, Yuchao Tao, and Ashwin Machanavajjhala. 2022.  R2t: Instance-optimal truncation for differentially private query evaluation with foreign keys. In _Proceedings of the 2022 International Conference on Management of Data_. 759–772.
  * Dwork et al. (2010) Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. 2010.  Differential privacy under continual observation. In _Proceedings of the forty-second ACM symposium on Theory of computing_. 715–724.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al. 2014\.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ 9, 3-4 (2014), 211–407.
  * Elmasri et al. (2020) R Elmasri, SB Navathe, R Elmasri, and SB Navathe. 2020.  Fundamentals of Database Systems¡/Title. In _Advances in Databases and Information Systems: 24th European Conference, ADBIS 2020, Lyon, France, August 25–27, 2020, Proceedings_ , Vol. 12245. Springer Nature, 139.
  * Eskandarian and Zaharia (2017) Saba Eskandarian and Matei Zaharia. 2017.  Oblidb: Oblivious query processing for secure databases.  _arXiv preprint arXiv:1710.00458_ (2017).
  * Goldreich (2004) Oded Goldreich. 2004.  _Foundations of Cryptography, Volume 2_.  Cambridge university press Cambridge.
  * Goldreich (2009) Oded Goldreich. 2009.  _Foundations of cryptography: volume 2, basic applications_.  Cambridge university press.
  * Goodrich (2014) Michael T Goodrich. 2014.  Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in o (n log n) time. In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_. 684–693.
  * Groce et al. (2019) Adam Groce, Peter Rindal, and Mike Rosulek. 2019.  Cheaper private set intersection via differentially private leakage.  _Proceedings on Privacy Enhancing Technologies_ 2019, 3 (2019).
  * Grubbs et al. (2018) Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G Paterson. 2018.  Pump up the volume: Practical database reconstruction from volume leakage on range queries. In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_. 315–331.
  * Han et al. (2021) Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al. 2021\.  Cardinality estimation in DBMS: A comprehensive benchmark evaluation.  _arXiv preprint arXiv:2109.05877_ (2021).
  * Harmouch and Naumann (2017) Hazar Harmouch and Felix Naumann. 2017.  Cardinality estimation: An experimental survey.  _Proceedings of the VLDB Endowment_ 11, 4 (2017), 499–512.
  * He et al. (2017) Xi He, Ashwin Machanavajjhala, Cheryl Flynn, and Divesh Srivastava. 2017.  Composing differential privacy and secure computation: A case study on scaling private record linkage. In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. 1389–1406.
  * He et al. (2015) Zhian He, Wai Kit Wong, Ben Kao, David Wai Lok Cheung, Rongbin Li, Siu Ming Yiu, and Eric Lo. 2015.  Sdb: A secure query processing system with data interoperability.  _Proceedings of the VLDB Endowment_ 8, 12 (2015), 1876–1879.
  * Hertzschuch et al. (2021) Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021.  Simplicity Done Right for Join Ordering.. In _CIDR_.
  * Huang et al. (2020) Dongxu Huang, Qi Liu, Qiu Cui, Zhuhe Fang, Xiaoyu Ma, Fei Xu, Li Shen, Liu Tang, Yuxing Zhou, Menglong Huang, et al. 2020\.  TiDB: a Raft-based HTAP database.  _Proceedings of the VLDB Endowment_ 13, 12 (2020), 3072–3084.
  * Jönsson et al. (2011) Kristjän Valur Jönsson, Gunnar Kreitz, and Misbah Uddin. 2011.  Secure multi-party sorting and applications.  _Cryptology ePrint Archive_ (2011).
  * Kamara et al. (2011) Seny Kamara, Payman Mohassel, and Mariana Raykova. 2011.  Outsourcing multi-party computation.  _Cryptology ePrint Archive_ (2011).
  * Kellaris et al. (2016) Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O’neill. 2016.  Generic attacks on secure outsourced databases. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_. 1329–1340.
  * Keller and Scholl (2014) Marcel Keller and Peter Scholl. 2014.  Efficient, oblivious data structures for MPC. In _Advances in Cryptology–ASIACRYPT 2014: 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, ROC, December 7-11, 2014, Proceedings, Part II 20_. Springer, 506–525.
  * Kifer and Machanavajjhala (2011) Daniel Kifer and Ashwin Machanavajjhala. 2011.  No free lunch in data privacy. In _Proceedings of the 2011 ACM SIGMOD International Conference on Management of data_. 193–204.
  * Knott et al. (2021) Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. 2021.  Crypten: Secure multi-party computation meets machine learning.  _Advances in Neural Information Processing Systems_ 34 (2021), 4961–4973.
  * Kotsogiannis et al. (2019) Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. 2019.  Privatesql: a differentially private sql query engine.  _Proceedings of the VLDB Endowment_ 12, 11 (2019), 1371–1384.
  * Kraska et al. (2018) Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018.  The case for learned index structures. In _Proceedings of the 2018 international conference on management of data_. 489–504.
  * Liagouris et al. (2023) John Liagouris, Vasiliki Kalavri, Muhammad Faisal, and Mayank Varia. 2023.  $\\{$SECRECY$\\}$: Secure collaborative analytics in untrusted clouds. In _20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)_. 1031–1056.
  * Lovingmage (2024) Lovingmage. 2024.  Synopsis Assisted Secure Collaborative Analytics.  https://github.com/lovingmage/SPECIAL/.
  * Micali et al. (1987) Silvio Micali, Oded Goldreich, and Avi Wigderson. 1987.  How to play any mental game. In _Proceedings of the Nineteenth ACM Symp. on Theory of Computing, STOC_. ACM New York, NY, USA, 218–229.
  * Mironov et al. (2009) Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. 2009.  Computational differential privacy. In _Annual International Cryptology Conference_. Springer, 126–142.
  * Mishra et al. (2018) Pratyush Mishra, Rishabh Poddar, Jerry Chen, Alessandro Chiesa, and Raluca Ada Popa. 2018.  Oblix: An efficient oblivious search index. In _2018 IEEE symposium on security and privacy (SP)_. IEEE, 279–296.
  * Mohassel and Zhang (2017) Payman Mohassel and Yupeng Zhang. 2017.  Secureml: A system for scalable privacy-preserving machine learning. In _2017 IEEE symposium on security and privacy (SP)_. IEEE, 19–38.
  * Mouris et al. (2024) Dimitris Mouris, Daniel Masny, Ni Trieu, Shubho Sengupta, Prasad Buddhavarapu, and Benjamin Case. 2024.  Delegated Private Matching for Compute.  _Proceedings on Privacy Enhancing Technologies_ (2024).
  * Oya and Kerschbaum (2021) Simon Oya and Florian Kerschbaum. 2021.  Hiding the access pattern is not enough: Exploiting search pattern leakage in searchable encryption. In _30th USENIX security symposium (USENIX Security 21)_. 127–142.
  * Patel et al. (2019) Sarvar Patel, Giuseppe Persiano, Kevin Yeo, and Moti Yung. 2019.  Mitigating leakage in secure cloud-hosted data structures: Volume-hiding for multi-maps via hashing. In _Proceedings of the 2019 ACM SIGSAC conference on computer and communications security_. 79–93.
  * Pettai and Laud (2015) Martin Pettai and Peeter Laud. 2015.  Combining differential privacy and secure multiparty computation. In _Proceedings of the 31st annual computer security applications conference_. 421–430.
  * Pinkas and Reinman (2010) Benny Pinkas and Tzachy Reinman. 2010.  Oblivious RAM revisited. In _Advances in Cryptology–CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30_. Springer, 502–519.
  * Poddar et al. (2021) Rishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng, Raluca Ada Popa, and Joseph M Hellerstein. 2021.  Senate: a $\\{$Maliciously-Secure$\\}$$\\{$MPC$\\}$ platform for collaborative analytics. In _30th USENIX Security Symposium (USENIX Security 21)_. 2129–2146.
  * Qin et al. (2022) Lianke Qin, Rajesh Jayaram, Elaine Shi, Zhao Song, Danyang Zhuo, and Shumo Chu. 2022.  Adore: Differentially oblivious relational database operators.  _arXiv preprint arXiv:2212.05176_ (2022).
  * Qiu et al. ([n.d.]) Lina Qiu, Georgios Kellaris, Nikos Mamoulis, Kobbi Nissim, and George Kollios. [n.d.].  Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures.  ([n. d.]).
  * Ramachandran and Shi (2021) Vijaya Ramachandran and Elaine Shi. 2021.  Data oblivious algorithms for multicores. In _Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures_. 373–384.
  * Roy Chowdhury et al. (2020) Amrita Roy Chowdhury, Chenghong Wang, Xi He, Ashwin Machanavajjhala, and Somesh Jha. 2020.  Crypte: Crypto-assisted differential privacy on untrusted servers. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_. 603–619.
  * Sasy et al. (2022) Sajin Sasy, Aaron Johnson, and Ian Goldberg. 2022.  Fast Fully Oblivious Compaction and Shuffling. In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_. 2565–2579.
  * Scholl et al. (2017) Peter Scholl, Nigel P Smart, and Tim Wood. 2017.  When it’s all just too much: outsourcing MPC-preprocessing. In _Cryptography and Coding: 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings 16_. Springer, 77–99.
  * Shang et al. (2021) Zhiwei Shang, Simon Oya, Andreas Peter, and Florian Kerschbaum. 2021.  Obfuscated access and search patterns in searchable encryption.  _arXiv preprint arXiv:2102.09651_ (2021).
  * Silberschatz et al. (2011) Abraham Silberschatz, Henry F Korth, and Shashank Sudarshan. 2011.  Database system concepts.  (2011).
  * Stefanov et al. (2011) Emil Stefanov, Elaine Shi, and Dawn Song. 2011.  Towards practical oblivious RAM.  _arXiv preprint arXiv:1106.3652_ (2011).
  * Tan et al. (2021) Sijun Tan, Brian Knott, Yuan Tian, and David J Wu. 2021.  CryptGPU: Fast privacy-preserving machine learning on the GPU. In _2021 IEEE Symposium on Security and Privacy (SP)_. IEEE, 1021–1038.
  * Tinoco et al. (2023) Afonso Tinoco, Sixiang Gao, and Elaine Shi. 2023.  $\\{$EnigMap$\\}$:$\\{$External-Memory$\\}$ Oblivious Map for Secure Enclaves. In _32nd USENIX Security Symposium (USENIX Security 23)_. 4033–4050.
  * Volgushev et al. (2019) Nikolaj Volgushev, Malte Schwarzkopf, Ben Getchell, Mayank Varia, Andrei Lapets, and Azer Bestavros. 2019.  Conclave: secure multi-party computation on big data. In _Proceedings of the Fourteenth EuroSys Conference 2019_. 1–18.
  * Wagh et al. (2016) Sameer Wagh, Paul Cuff, and Prateek Mittal. 2016.  Differentially private oblivious ram.  _arXiv preprint arXiv:1601.03378_ (2016).
  * Wagh et al. (2021) Sameer Wagh, Xi He, Ashwin Machanavajjhala, and Prateek Mittal. 2021.  DP-cryptography: marrying differential privacy and cryptography in emerging applications.  _Commun. ACM_ 64, 2 (2021), 84–93.
  * Wang et al. (2021) Chenghong Wang, Johes Bater, Kartik Nayak, and Ashwin Machanavajjhala. 2021.  DP-Sync: Hiding update patterns in secure outsourced databases with differential privacy. In _Proceedings of the 2021 International Conference on Management of Data_. 1892–1905.
  * Wang et al. (2022) Chenghong Wang, Johes Bater, Kartik Nayak, and Ashwin Machanavajjhala. 2022.  IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy.  _arXiv preprint arXiv:2203.05084_ (2022).
  * Wang et al. (2023) Chenghong Wang, David Pujo, Kartik Nayak, and Ashwin Machanavajjhala. 2023.  Private Proof-of-Stake Blockchains using Differentially-private Stake Distortion.  _Cryptology ePrint Archive_ (2023).
  * Wang et al. (2014) Xiao Shaun Wang, Kartik Nayak, Chang Liu, TH Hubert Chan, Elaine Shi, Emil Stefanov, and Yan Huang. 2014.  Oblivious data structures. In _Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security_. 215–226.
  * Wang and Yi (2021) Yilei Wang and Ke Yi. 2021.  Secure yannakakis: Join-aggregate queries over private data. In _Proceedings of the 2021 International Conference on Management of Data_. 1969–1981.
  * Xiao and Xiong (2015) Yonghui Xiao and Li Xiong. 2015.  Protecting locations with differential privacy under temporal correlations. In _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_. 1298–1309.
  * Yao (1986) Andrew Chi-Chih Yao. 1986.  How to generate and exchange secrets. In _27th annual symposium on foundations of computer science (Sfcs 1986)_. IEEE, 162–167.
  * Zhang et al. (2023) Yanping Zhang, Johes Bater, Kartik Nayak, and Ashwin Machanavajjhala. 2023.  Longshot: Indexing Growing Databases Using MPC and Differential Privacy.  _Proceedings of the VLDB Endowment_ 16, 8 (2023), 2005–2018.
  * Zhang et al. (2016) Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. 2016.  All your queries are belong to us: the power of $\\{$File-Injection$\\}$ attacks on searchable encryption. In _25th USENIX Security Symposium (USENIX Security 16)_. 707–720.
  * Zhang et al. (2021) Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. 2021.  $\\{$PrivSyn$\\}$: Differentially Private Data Synthesis. In _30th USENIX Security Symposium (USENIX Security 21)_. 929–946.
  * Zheng et al. (2017) Wenting Zheng, Ankur Dave, Jethro G Beekman, Raluca Ada Popa, Joseph E Gonzalez, and Ion Stoica. 2017.  Opaque: An oblivious and encrypted distributed analytics platform. In _14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17)_. 283–298.

##  Appendix A Privacy Proof

###### Theorem A.1.

The one-sided Laplace mechanism as described in Definition 4.1 satisfies
$(\epsilon,\delta)$-DP.

###### Proof.

WLOG. we illustrate proof details by assuming positive mechanism,
$\mathsf{Lap}^{+}$, and by symmetric, the properties proved here also holds
for $\mathsf{Lap}^{-}$. In general, we write the mechanism as
$\mathcal{M}(D)\leftarrow f(D)+\mathsf{Lap}^{+}(\epsilon,\delta)$, where $f$
is a counting query. Note that the sensitive for counting query is 1, and thus
we will implicitly omit the sensitivity notations.

Given any two neighboring databases $D$ and $D^{\prime}$, and let $c\leftarrow
f(D)$ and $c^{\prime}\leftarrow f(D^{\prime})$, WLOG. we will assume $c\leq
c^{\prime}$. Now we will evaluate three disjoint output domains for $f$,
namely $O_{1}=(-\infty,c)$, $O_{2}=[c,c^{\prime}]$, and
$O_{3}=(c^{\prime},+\infty)$. Since the noise is non-negative, thus it’s clear
that $\textup{Pr}[\mathcal{M}(D)\in O_{1}]=0$ and
$\textup{Pr}[\mathcal{M}(D^{\prime})\in O_{1}]=0$. Next, we evaluate the
domain $O_{3}$ and consider an auxiliary domain $O^{*}=\\{x-c^{\prime}:x\in
O_{3}\\}$. We compute the following ratio:

(6) $\begin{split}\frac{\textup{Pr}[\mathcal{M}(D)\in
O_{3}]}{\textup{Pr}[\mathcal{M}(D^{\prime})\in
O_{3}]}&=\frac{\textup{Pr}[c+\mathsf{Lap}^{+}(\epsilon,\delta)\in
O_{3}]}{\textup{Pr}[c^{\prime}+\mathsf{Lap}^{+}(\epsilon,\delta)\in O_{3}]}\\\
&=\frac{\textup{Pr}[\mathsf{Lap}^{+}(\epsilon,\delta)\in
O^{*}]}{\textup{Pr}[\mathsf{Lap}^{+}(\epsilon,\delta)\in
O^{*}+(c^{\prime}-c)]}\\\
&=\frac{e^{-\epsilon|x-\mu|}}{e^{-\epsilon|x-(c^{\prime}-c)-\mu|}}\\\
&=e^{\epsilon(|x-(c^{\prime}-c)-\mu|-|x-\mu|)}\\\ &\leq
e^{\epsilon(|c^{\prime}-c)|)}~{}~{}(\textup{triangle~{}inequality})\\\
&=e^{\epsilon}\end{split}$

Then we evaluate the last output domain $O_{2}$, and we can see that
$\textup{Pr}[\mathcal{M}(D^{\prime})\in O_{2}]=0$ and
$\textup{Pr}[\mathcal{M}(D)\in O_{2}]\geq 0$, and thus there will be unbounded
privacy loss within the domain of $O_{2}=[c^{\prime},c]$. However, we can
bound this probability by $\delta$, which is equivalent to prove that with
density function

$\textup{Pr}[z=x]=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}e^{-\epsilon|x-\mu|},$

where $\mu=1-\frac{1}{\epsilon}\ln(\delta(e^{\epsilon}+1))$, the probability
of sampling a value $z$ within the range $(-\infty,1]$ is less than or equal
to $\delta$. Since we consider a discrete distribution, thus we compute the
following

(7)
$\begin{split}\Pr[z<1]&=\sum_{x=-\infty}^{0}\frac{e^{\epsilon}-1}{e^{\epsilon}+1}e^{-\epsilon(\mu-x)}\\\
&=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}e^{-\epsilon\mu}\sum_{x=-\infty}^{0}e^{\epsilon
x}\\\
&=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}e^{-\epsilon\mu}\frac{1}{1-e^{-\epsilon}}\quad\text{(geometric
series sum of }e^{\epsilon x})\\\
&=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}e^{-\epsilon\left(1-\frac{1}{\epsilon}\ln(\delta(e^{\epsilon}+1))\right)}\frac{1}{1-e^{-\epsilon}}\quad\text{(substitute
}\mu)\\\
&=\frac{e^{\epsilon}}{e^{\epsilon}+1}e^{-\epsilon+\ln(\delta(e^{\epsilon}+1))}\\\
&=\frac{e^{\epsilon}}{e^{\epsilon}+1}e^{-\epsilon}\delta(e^{\epsilon}+1)\\\
&=\delta.\end{split}$

Combining all these we obtain the following

(8) $\begin{split}\textup{Pr}[\mathcal{M}(D)\in
O]&=\textup{Pr}[\mathcal{M}(D)\in(O_{1}\cup O_{2}\cup O_{3})]\\\
&=\textup{Pr}[\mathcal{M}(D)\in O_{2}]+\textup{Pr}[\mathcal{M}(D)\in O_{3}]\\\
&\leq\delta+e^{\epsilon}\textup{Pr}[\mathcal{M}(D^{\prime})\in(O_{2})]\end{split}$

The claim thus holds. ∎

Next we prove Theorem 4.3.

###### Proof.

(Theorem 4.3) We prove this theorem by analyzing privacy loss using
composition theorems. Generating noisy histograms with one-sided noise is
equivalent to releasing multiple counting queries across disjoint datasets.
Therefore, by the parallel composition theorem (Dwork et al., 2014), each
histogram release is $(\epsilon,\delta)$-DP. The release of the maximum
frequency via a noisy max mechanism is $(\epsilon,0)$-DP. Given $c$ pairs, the
sequential composition theorem (Dwork et al., 2014) applies, resulting in a
total privacy loss under $2c$-fold advanced composition. Consequently, the
entire process adheres to $(\hat{\epsilon},\hat{\delta})$-DP, with
$\hat{\epsilon}\leq 6\epsilon\sqrt{c\ln(1/\delta)}$.

∎

###### Theorem A.2.

The privacy of SPECIAL adheres to Definition 3.1

###### Proof.

Since the entire DP synopses releasing satisfies DP. Thus, we prove this
theorem by constructing a simulator, $\mathcal{S}$, which takes only the DP
synopses as input and can simulate execution transcripts that are
indistinguishable from those of the actual protocol. For ease of notation, we
abstract SPECIAL as a composed secure protocol $\pi$.

We first examine a hybrid protocol, $\pi_{1}$, differing from $\pi$ in that
the secure outsourcing procedure—where owners upload secret shares of their
data to two servers—is replaced by a simulator, $\mathcal{S}_{1}$. This
simulator, which takes no input, simulates secret shares with randomly sampled
data $(x_{1},x_{2})\xleftarrow[]{\mathsf{rd}}\mathbb{Z}_{2^{32}}$. We say that
a $\mathcal{S}_{1}$ must exist that produces results indistinguishable from
the secret shares in $\pi$, as the absence of such a simulator would imply the
non-existence of secure secret sharing techniques. Next, we consider another
hybrid protocol, $\pi_{2}$, which differs from $\pi_{1}$ only in that the
query planning function is replaced by a simulator $\mathcal{S}_{2}$. This
simulator takes as inputs all synopses and a set of random values (simulated
secure outsourced data) generated by $\mathcal{S}_{1}$, and produces a
simulated execution plan for every requested query. We say that an
$\mathcal{S}_{2}$ should also exist with outputs indistinguishable from
$\pi$’s execution plans. Given that Selinger optimizers can pre-generate
execution plans using only table statistics, the non-existence of such a
simulator, $\mathcal{S}_{2}$, would imply the non-existence of Selinger
optimizers, which is contradictory. Finally, we construct
$\mathcal{S}=(\mathcal{S}_{1},\mathcal{S}_{2})$, where $\mathcal{S}_{1}$
simulates secure data outsourcing and $\mathcal{S}_{2}$ simulates query
planning. $\mathcal{S}$ executes the query plan using randomly generated
values from $\mathcal{S}_{1}$ through MPC computation. Since both the
execution plans and input data are indistinguishable from those in $\pi$, the
MPC execution must also be indistinguishable. Otherwise, it would violate the
security guarantees of MPC. ∎

##  Appendix B Query Workloads

We illustrate the benchmark query workloads as follows:

Listing 1: Benchmark query workload