Search

We present LINQ, the first join protocol with linear complexity (in both running time and communication) under the secure multi-party computation model (MPC). It can also be extended to support all free-connex queries, a large class of select-join-aggregate queries, still with linear complexity. This matches the plaintext result for the query processing problem, as free-connex queries are the largest class of queries known to be solvable in linear time in plaintext. We have then built a query processing system based on LINQ, and the experimental results show that LINQ significantly outperforms the state of the art. For example, it can finish a query on three relations with an output size of 1 million tuples in around 100s in the LAN setting, while existing protocols that support the query cannot finish in an hour. Thus LINQ brings MPC query processing closer to practicality.

Differentially private mechanisms achieving worst-case optimal error bounds (e.g., the classical Laplace mechanism) are well-studied in the literature. However, when typical data are far from the worst case, \emph{instance-specific} error bounds -- which depend on the largest value in the dataset -- are more meaningful. For example, consider the sum estimation problem, where each user has an integer $x_i$ from the domain $\{0,1,\dots,U\}$ and we wish to estimate $\sum_i x_i$. This has a worst-case optimal error of $O(U/\varepsilon)$, while recent work has shown that the clipping mechanism can achieve an instance-optimal error of $O(\max_i x_i \cdot \log\log U /\varepsilon)$. Under the shuffle model, known instance-optimal protocols are less communication-efficient. The clipping mechanism also works in the shuffle model, but requires two rounds: Round one finds the clipping threshold, and round two does the clipping and computes the noisy sum of the clipped data. In this paper, we show how these two seemingly sequential steps can be done simultaneously in one round using just $1+o(1)$ messages per user, while maintaining the instance-optimal error bound. We also extend our technique to the high-dimensional sum estimation problem and sparse vector aggregation (a.k.a. frequency estimation under user-level differential privacy).

We present a protocol in the shuffle model of differential privacy (DP) for the \textit{frequency estimation} problem that achieves error $\omega(1)\cdot O(\log n)$, almost matching the central-DP accuracy, with $1+o(1)$ messages per user. This exhibits a sharp transition phenomenon, as there is a lower bound of $\Omega(n^{1/4})$ if each user is allowed to send only one message. Previously, such a result is only known when the domain size $B$ is $o(n)$. For a large domain, we also need an efficient method to identify the \textit{heavy hitters} (i.e., elements that are frequent enough). For this purpose, we design a shuffle-DP protocol that uses $o(1)$ messages per user and can identify all heavy hitters in time polylogarithmic in $B$. Finally, by combining our frequency estimation and the heavy hitter detection protocols, we show how to solve the $B$-dimensional \textit{1-sparse vector summation} problem in the high-dimensional setting $B=\Omega(n)$, achieving the optimal central-DP MSE $\tilde O(n)$ with $1+o(1)$ messages per user. In addition to error and message number, our protocols improve in terms of message size and running time as well. They are also very easy to implement. The experimental results demonstrate order-of-magnitude improvement over prior work.

A closer integration of machine learning and relational databases has gained steam in recent years due to the fact that the training data to many ML tasks is the results of a relational query (most often, a join-select query). In a federated setting, this poses an additional challenge, that the tables are held by different parties as their private data, and the parties would like to train the model without having to use a trusted third party. Existing work has only considered the case where the training data is stored in a flat table that has been vertically partitioned, which corresponds to a simple PK-PK join. In this paper, we describe secure protocols to compute the join results of multiple tables conforming to a general foreign-key acyclic schema, and how to feed the results in secret-shared form to a secure ML toolbox. Furthermore, existing secure ML systems reveal the PKs in the join results. We strengthen the privacy protection to higher levels and achieve zero information leakage beyond the trained model. If the model itself is considered sensitive, we show how differential privacy can be incorporated into our framework to also prevent the model from breaching individuals' privacy.