We propose a new private Approximate Nearest Neighbor (ANN) search scheme named Pacmann that allows a client to perform ANN search in a vector database without revealing the query vector to the server. Unlike prior constructions that run encrypted search on the server side, Pacmann carefully offloads limited computation and storage to the client, no longer requiring computationally-intensive cryptographic techniques. Specifically, clients run a graph-based ANN search, where in each hop on the graph, the client privately retrieves local graph information from the server. To make this efficient, we combine two ideas: (1) we adapt a leading graph-based ANN search algorithm to be compatible with private information retrieval (PIR) for subgraph retrieval; (2) we use a recent class of PIR schemes that trade offline preprocessing for online computational efficiency. Pacmann achieves significantly better search quality than the state-of-the-art private ANN search schemes, showing up to 2.5$\times$ better search accuracy on real-world datasets than prior work and reaching 90\% quality of a state-of-the-art non-private ANN algorithm. Moreover on large datasets with up to 100 million vectors, Pacmann shows better scalability than prior private ANN schemes with up to 62\% reduction in computation time and 22\% reduction in overall latency.

We consider how to design an anonymous data collection protocol that enforces compliance rules. Imagine that each client contributes multiple data items (e.g., votes, location crumbs, or secret shares of its input) to an abstraction of an anonymous network, which mixes all clients' data items so that the receiver cannot determine which data items belong to the same user. Now, each user must prove to an auditor that the set it contributed satisfies a compliance predicate, without identifying which items it contributed. For example, the auditor may want to ensure that no voter voted for the same candidate twice, or that a user's location crumbs are not too far apart in a given time interval.

Differential obliviousness (DO) is a privacy notion which mandates that the access patterns of a program satisfy differential privacy. Earlier works have shown that in numerous applications, differential obliviousness allows us to circumvent fundamental barriers pertaining to fully oblivious algorithms, resulting in asymptotical (and sometimes even polynomial) performance improvements. Although DO has been applied to various contexts, including the design of algorithms, data structures, and protocols, its compositional properties are not explored until the recent work of Zhou et al. (Eurocrypt'23). Specifically, Zhou et al. showed that the original DO notion is not composable. They then proposed a refinement of DO called neighbor-preserving differential obliviousness (NPDO), and proved a basic composition for NPDO. In Zhou et al.'s basic composition theorem for NPDO, the privacy loss is linear in k for k-fold composition. In comparison, for standard differential privacy, we can enjoy roughly √k loss for k-fold composition by applying the well-known advanced composition theorem given an appropriate parameter range. Therefore, a natural question left open by their work is whether we can also prove an analogous advanced composition for NPDO. In this paper, we answer this question affirmatively. As a key step in proving an advanced composition theorem for NPDO, we define a more operational notion called symmetric NPDO which we prove to be equivalent to NPDO. Using symmetric NPDO as a stepping stone, we also show how to generalize NPDO to more general notions of divergence, resulting in Rényi-NPDO, zeroconcentrated-NPDO, Gassian-NPDO, and g-NPDO notions. We also prove composition theorems for these generalized notions of NPDO.

We construct a sublinear-time single-server preprocessing Private Information Retrieval (PIR) scheme with an optimal tradeoff between client storage and server computation (up to poly-logarithmic factors). Our scheme achieves amortized $\tilde O(\sqrt n )$ server and client computation and $O(\sqrt n )$ online communication per query, and requires ${\tilde O_\lambda }(\sqrt n )$ client storage. Unlike prior single-server PIR schemes that rely on heavy cryptographic machinery such as Homomorphic Encryption, our scheme relies only on Pseudo-Random Functions (PRF). To the best of our knowledge, Piano is the first practical single-server sublinear-time PIR scheme, and we outperform the state-of-the-art single-server PIR by 10×-300×. In comparison with the best known two-server PIR scheme, Piano enjoys comparable performance but our construction is considerably simpler. Experimental results show that for a 100GB database and with 60ms round-trip latency, Piano achieves 93ms response time, while the best known prior scheme requires 11s or more.

Blockchain systems must be secure and offer high performance. These systems rely on transaction broadcast mechanisms to provide both of these features. Unfortunately, in today’s systems, the broadcast mechanisms are highly inefficient.We present Mercury, a new transaction broadcast protocol designed for high performance blockchains. Mercury shortens the transaction propagation delay using two techniques: a virtual coordinate system and an early outburst strategy. Simulation results show that Mercury outperforms prior propagation schemes and decreases overall propagation latency by up to 44%. When implemented in Conflux, an open-source high-throughput blockchain system, Mercury reduces transaction propagation latency by over 50% with less than 5% bandwidth overhead.

Vector mean estimation is a central primitive in federated analytics. In vector mean estimation, each user $i \in[n]$ holds a real-valued vector $v_{i} \in[-1,1]^{d}$, and a server wants to estimate the mean of all n vectors; we would additionally like to protect each user’s privacy. In this paper, we consider the k-sparse version of the vector mean estimation problem. That is, suppose each user’s vector has at most k non-zero coordinates in its d-dimensional vector, and moreover, $k \ll d$. In practice, since the universe size d can be very large (e.g., the space of all possible URLs), we would like the per-user communication to be succinct, i.e., independent of or (poly-)logarithmic in the universe size.In this paper, we show matching upper- and lower-bounds for the k-sparse vector mean estimation problem under local differential privacy (LDP). Specifically, we construct new mechanisms that achieve asymptotically optimal error as well as succinct communication, either under user-level-LDP or event-level-LDP. We implement our algorithms and evaluate them on synthetic and real-world datasets. Our experiments show that we can often achieve one or two orders of magnitude reduction in error compared with prior work under typical choices of parameters, while incurring insignificant communication cost.

We present vacuum filters, a type of data structures to support approximate membership queries. Vacuum filters cost the smallest space among all known AMQ data structures and provide higher insertion and lookup throughput in most situations. Hence they can be used as the replacement of the widely used Bloom filters and cuckoo filters. Similar to cuckoo filters, vacuum filters also store item fingerprints in a table. The memory-efficiency and throughput improvements are from the innovation of a table insertion and fingerprint eviction strategy that achieves both high load factor and data locality without any restriction of the table size. In addition, we propose a new update framework to resolve two difficult problems for AMQ structures under dynamics, namely duplicate insertions and set resizing. The experiments show that vacuum filters can achieve 25% less space in average and similar throughput compared to cuckoo filters, and 15% less space and >10x throughput compared to Bloom filters, with same false positive rates. AMQ data structures are widely used in various layers of computer systems and networks and are usually hosted in platforms where memory is limited and precious. Hence the improvements brought by vacuum filters can be considered significant.