We present Private Random Access Computations (PRAC), a 3-party Secure Multi-Party Computation (MPC) framework to support random-access data structure algorithms for MPC with efficient communication in terms of rounds and bandwidth. PRAC extends the state-of-the-art DORAM Duoram with a new implementation, more flexibility in how the DORAM memory is shared, and support for Incremental and Wide DPFs. We then use these DPF extensions to achieve algorithmic improvements in three novel oblivious data structure protocols for MPC. PRAC exploits the observation that a secure protocol for an algorithm can gain efficiency if the protocol explicitly reveals information leaked by the algorithm inherently. We first present an optimized binary search protocol that reduces the bandwidth from O(lg² n) to O(lg n) for obliviously searching over n items. We then present an oblivious heap protocol with rounds reduced from O(lg n) to O(lg lg n) for insertions, and bandwidth reduced from O(lg² n) to O(lg n) for extractions. Finally, we also present the first oblivious AVL tree protocol for MPC where no party learns the data or the structure of the AVL tree, and can support arbitrary insertions and deletions with O(lg n) rounds and bandwidth. We experimentally evaluate our protocols with realistic network settings for a wide range of memory sizes to demonstrate their efficiency. For instance, we observe our binary search protocol provides >27× and >3× improvements in wall-clock time and bandwidth respectively over other approaches for a memory with 2^26 items; for the same setting our heap's extract-min protocol achieves >31× speedup in wall-clock time and >13× reduction in bandwidth.

We introduce Grotto, a framework and C++ library for space- and time-efficient (2+1)-party piecewise polynomial (i.e., spline) evaluation on secrets additively shared over ℤ2n. Grotto improves on the state-of-the-art approaches based on distributed comparison functions (DCFs) in almost every metric, offering asymptotically superior communication and computation costs with the same or lower round complexity. At the heart of Grotto is a novel observation about the structure of the ''tree'' representation underlying the most efficient distributed point functions (DPFs) from the literature, alongside an efficient algorithm that leverages this structure to do with a lightweight DPF what state-of-the-art approaches require comparatively heavyweight DCFs to do. Our open-source Grotto implementation supports dozens of useful functions out of the box, including trigonometric and hyperbolic functions with their inverses; various logarithms; roots, reciprocals, and reciprocal roots; sign testing and bit counting; and over two dozen of the most common univariate activation functions from the deep-learning literature.

We present Sabre, a family of sender-anonymous messaging protocols with instances supporting both Twitter-like anonymous bulletin boards and Secure Drop-like mailboxes. Both variants provide strong anonymity while potentially scaling to anonymity sets in the tens of millions and beyond. Sabre protocols inherit their basic structure from Riposte and Express while replacing those schemes’ linear-cost audit protocols with new logarithmic-cost ones. Sabre also incorporates a host of innovations that improve concrete performance by an order of magnitude or more under “ideal” circumstances, while providing asymptotic speedups in the face of resource exhaustion-style DoS attacks.

Abstract We describe the design, analysis, implementation, and evaluation of Pirsona, a digital content delivery system that realizes collaborative-filtering recommendations atop private information retrieval (PIR). This combination of seemingly antithetical primitives makes possible—for the first time—the construction of practically efficient e-commerce and digital media delivery systems that can provide personalized content recommendations based on their users’ historical consumption patterns while simultaneously keeping said consumption patterns private. In designing Pirsona, we have opted for the most performant primitives available (at the expense of rather strong non-collusion assumptions); namely, we use the recent computationally 1-private PIR protocol of Hafiz and Henry (PETS 2019.4) together with a carefully optimized 4PC Boolean matrix factorization.