More Like this

1. Batched Differentially Private Information Retrieval

   Albab, Kinan Dak; Issa, Rawane; Varia, Mayank; Graffi, Kalman (August 2022, 31st USENIX Security Symposium)

   Private Information Retrieval (PIR) allows several clients to query a database held by one or more servers, such that the contents of their queries remain private. Prior PIR schemes have achieved sublinear communication and computation by leveraging computational assumptions, federating trust among many servers, relaxing security to permit differentially private leakage, refactoring effort into an offline stage to reduce online costs, or amortizing costs over a large batch of queries. In this work, we present an efficient PIR protocol that combines all of the above techniques to achieve constant amortized communication and computation complexity in the size of the database and constant client work. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol achieves speedups up to and exceeding 10x in practical settings compared to state of the art PIR protocols, and can scale to batches with hundreds of millions of queries on cheap commodity AWS machines. Our protocol builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party. 

   more » « less
2. Malicious Secure, Structure-Aware Private Set Intersection

   Garimella, Gayathri; Rosulek, Mike; Singh, Jaspal (August 2023, Springer)

   Structure-Aware private set intersection (sa-PSI) is a variant of PSI where Alice’s input set A has some publicly known structure, Bob’s input B is an unstructured set of points, and Alice learns the intersection A ∩ B. sa-PSI was recently introduced by Garimella et al. (Crypto 2022), who described a semi-honest protocol with communication that scales with the description size of Alice’s set, instead of its cardinality. In this paper, we present the first sa-PSI protocol secure against malicious adversaries. sa-PSI protocols are built from function secret sharing (FSS) schemes, and the main challenge in our work is ensuring that multiple FSS sharings encode the same structured set. We do so using a cut-and-choose approach. In order to make FSS compatible with cut-and-choose, we introduce a new variant of function secret sharing, called derandomizable FSS (dFSS). We show how to construct dFSS for union of geometric balls, leading to a malicious-secure sa-PSI protocol where Alice’s input is a union of balls. We also improve prior FSS constructions, giving asymptotic improvements to semi-honest sa-PSI. 

   more » « less
3. PIVA: Privacy-Preserving Identity Verification Methods for Accountless Users via Private List Intersection and Variants

   https://doi.org/10.1007/978-3-031-70896-1_18  

   Hwang, Seoyeon; Jarecki, Stanislaw; Karl, Zane; van_Kempen, Elina; Tsudik, Gene (September 2024, Springer Nature Switzerland)

   Garcia-Alfaro, J; Kozik, R; Choraś, M; Katsikas, S (Ed.)

   Several prominent privacy regulation (e.g., CCPA and GDPR) require service providers to let consumers request access to, correct, or delete, their personal data. Compliance necessitates verification of consumer identity. This is not a problem for consumers who already have an account with a service provider since they can authenticate themselves via a successful account log-in. However, there are no such methods for accountless consumers, even though service providers routinely collect data about casual consumers, i.e., those without accounts. Currently, in order to access their collected data, accountless consumers are asked to provide Personally Identifiable Information (PII) to service providers, which is privacy-invasive. To address this problem, we propose PIVA: Privacy-Preserving Identity Verification for Accountless Users, a technique based on Private List Intersection (PLI) and its variants. First, we introduce PLI, a close relative of private set intersection (PSI), a well-known cryptographic primitive that allows two or more mutually suspicious parties to compute the intersection of their private input sets. PLI takes advantage of the (ordered and fixed) list structure of each party’s private set. As a result, PLI is more efficient than PSI. We also explore PLI variants: PLI-cardinality (PLI-CA), threshold-PLI (t-PLI), and threshold-PLI-cardinality (t-PLI-CA), all of which yield less information than PLI. These variants are progressively better suited for addressing the accountless consumer authentication problem. We prototype and compare its performance against techniques based on regular PSI and garbled circuits (GCs). Results show that proposed PLI and PLI-CA constructions are more efficient than GC-based techniques, in terms of both computation and communication overheads. While GC-based t-PLI and t-PLI-CA execute faster, proposed constructs greatly outperform the former in terms of bandwidth, e.g., our t-PLI protocol consumes less bandwidth. We also show that proposed protocols can be made secure against malicious adversaries, with only moderate increases in overhead. These variants outperform their GC-based counterparts by at least one order of magnitude. 

   more » « less
4. Mario: Multi-round Multiple-Aggregator Secure Aggregation with Robustness against Malicious Actors

   Nguyen, Truong_Son; Lepoint, Tancrède; Trieu, Ni (July 2025, 10th IEEE European Symposium on Security and Privacy (EuroS&P) 2025.)

   Federated Learning (FL) enables multiple clients to collaboratively train a machine learning model while keeping their data private, eliminating the need for data sharing. Two common approaches to secure aggregation (SA) in FL are the single-aggregator and multiple-aggregator models. This work focuses on improving the multiple-aggregator model. Existing multiple-aggregator protocols such as Prio (NSDI 2017), Prio+ (SCN 2022), Elsa (S&P 2023) either offer robustness only in the presence of semi-honest servers or provide security without robustness and are limited to two aggregators. We introduce Mario, the first multipleaggregator Secure Aggregation protocol that is both secure and robust in a malicious setting. Similar to prior work of Prio and Prio+, Mario provides secure aggregation in a setup of n servers and m clients. Unlike previous work, Mario removes the assumption of semi-honest servers, and provides a complete protocol with robustness under malicious clients and malicious servers. Our implementation shows that Mario is 3.40× and 283.4× faster than Elsa and Prio+, respecitively 

   more » « less
5. Updatable Private Set Intersection

   https://doi.org/10.2478/popets-2022-0051  

   Badrinarayanan, Saikrishna; Miao, Peihan; Xie, Tiancheng (March 2022, Proceedings on Privacy Enhancing Technologies)

   Abstract Private set intersection (PSI) allows two mutually distrusting parties each with a set as input, to learn the intersection of both their sets without revealing anything more about their respective input sets. Traditionally, PSI studies the static setting where the computation is performed only once on both parties’ input sets. We initiate the study of updatable private set intersection (UPSI), which allows parties to compute the intersection of their private sets on a regular basis with sets that also constantly get updated. We consider two specific settings. In the first setting called UPSI with addition , parties can add new elements to their old sets. We construct two protocols in this setting, one allowing both parties to learn the output and the other only allowing one party to learn the output. In the second setting called UPSI with weak deletion , parties can additionally delete their old elements every t days. We present a protocol for this setting allowing both parties to learn the output. All our protocols are secure against semi-honest adversaries and have the guarantee that both the computational and communication complexity only grow with the set updates instead of the entire sets. Finally, we implement our UPSI with addition protocols and compare with the state-of-the-art PSI protocols. Our protocols compare favorably when the total set size is sufficiently large, the new updates are sufficiently small, or in networks with low bandwidth. 

   more » « less