Oct 2026· Proceedings on Privacy Enhancing Technologies· Vol 2026, pp. 983-1005· 0 citations· 48 references
Computer Science
TL;DR
This work expands the understanding of attacks in this setting by investigating a broader class of functionalities, namely: Private Set Union, PSU-Cardinality, and Meta’s multi-key private matching (MKPM) functionality, and investigates possible mitigations for deploying such systems.
Abstract
Recent work (Falzon and Tang USENIX 2025) has shown that a protocol participant who behaves honestly but strategically chooses its inputs can break input privacy in the Private Join and Compute functionality. In this work, we expand our understanding of attacks in this setting by investigating a broader class of functionalities, namely: Private Set Union (PSU), PSU-Cardinality (PSU-CA), and Meta’s multi-key private matching (MKPM) functionality.
We begin with a simple yet novel attack on PSU that fully reconstructs the intersection using only two protocol invocations and forms the conceptual foundation for our more complex attacks. We also show that any attack on PSI-Cardinality, such as that of Guo et al. (USENIX 2023), lifts to an attack on PSU-CA that recovers the intersection with only three additional queries. For the MKPM protocol, we distinguish its intended matching functionality from the protocol-specific leakage, give an attack against the intended functionality, and then show that exploiting the additional leakage enables even stronger attacks, including partial reconstruction of the other party’s records from a single protocol invocation.
We conclude by discussing possible mitigations for deploying such systems. Our analysis demonstrates limitations of existing secure multi-party computation security definitions and highlights the real-world privacy risks associated with deploying these functionalities in practice.
We present Orq, a system that enables collaborative analysis of large private datasets using cryptographically secure multiparty computation (MPC). Orq protects data against semi-honest or malicious parties and can efficiently evaluate relational queries with multi-way joins and aggregations that have been considered notoriously expensive under MPC. To do so, Orq eliminates the quadratic cost of secure joins by leveraging the fact that, in practice, the structure of many real queries allows us to join records and apply the aggregations “on the fly” while keeping the result size bounded. On the system side, Orq contributes generic oblivious operators, a data-parallel vectorized query engine, a communication layer that amortizes MPC network costs, and a dataflow API for expressing relational analytics — all built from the ground up. We evaluate Orq in LAN and WAN deployments on a diverse set of workloads, including complex queries with multiple joins and custom aggregations. When compared to state-of-the-art solutions, Orq significantly reduces MPC execution times and can process one order of magnitude larger datasets. For our most challenging workload, the full TPC-H benchmark, we report results entirely under MPC with Scale Factor 10 — a scale that had previously been achieved only with information leakage or the use of trusted compute.
Eli Baum, Sam Buxbaum, Nitin Mathai et al.· ACM Transactions on Computer...· 0 citations
Private set intersection (PSI) and its circuit variant (Circuit-PSI, CPSI) are core tools for privacy-preserving analytics. Unlike plain PSI that directly reveals intersecting elements, CPSI outputs secret shares of intersection indicators (and associated-value shares), which can be reused in subsequent MPC tasks without disclosing element-level membership. This paper presents a practical two-stage framework for secure intersection cardinality: we instantiate CPSI following VOLE-PSI, then compute |X ∩Y| via Paillier-based homomorphic aggregation over CPSI indicator shares. The contribution is primarily a systems-oriented composition and analysis of these building blocks, with element-level privacy preserved and only the final aggregate cardinality revealed to the receiver.We provide a complete protocol description, a correctness argument, a complexity analysis, and a semi-honest simulation-based security discussion. We further present an experimental evaluation covering protocol breakdown, scalability, and several clearly labeled derived/estimated scenario tables. The results show clear scaling up to 220-level set sizes and identify the main practical bottlenecks, including ciphertext expansion and communication-aware batching. Overall, the framework offers an implementable and extensible solution for privacy-preserving cardinality analytics in realistic two-party settings.
Hai Zhang, Yiyun Guo, Li-Yan Shang et al.· International Conference on...· 0 citations
Combining secure multi-party computation (MPC) with differential privacy (DP) enables multiple parties to release aggregate statistics without a trusted curator, and the core primitive is the protocol to sample noise from a continuous distribution under finite-precision arithmetic. In this paper, we revisit the continuous noise sampling protocols and present several improvements in both security and efficiency. We start by identifying a vulnerability in widely used sample-and-scale constructions. We demonstrate that the scaling operation in arithmetic circuits confines the noise to a sparse, publicly known set of values, so that an adversary can observe the released noisy queries and decide which dataset produced them. As concrete demonstrations, we instantiate attacks on two systems employing such ``flawed''sampling protocols: Orchard (OSDI'20) for DP secure aggregation and DP-BREM$^+$ (USENIX Sec'25) for DP federated learning. We report a near-$100\%$ attack success rate on both systems, under any noise scaler $s\geq 2$ used in practice. The leakage we reveal is intrinsic to the scaling operation, and direct repairs either substantially sacrifice utility or add significant precision bits to make the sampling more expensive. To address the security and efficiency issues together, we turn to discrete sampling at the granularity of individual biased bits. We make several optimizations to the sampler and prove its security. Our implementation achieves $4\times \sim 612\times$ speedup over existing secure discrete samplers and orders-of-magnitude speedup over the insecure sample-and-scale paradigm, with negligible utility loss compared to the ideal continuous mechanism.
Existing Capture-the-Flag (CTF) platforms trust a single organizer, offer limited auditability, and are vulnerable to infrastructure-level manipulation. We propose zk–MPSFV, a zk-SNARK-based, multi-phase sub-flag verification scheme that replaces centralized scoring with an on-chain, zero-knowledge, publicly verifiable scoreboard. Challenges are decomposed into sub-challenges arranged as a directed acyclic graph (DAG): a team unlocks the next step only after proving completion of all parent nodes. Sub-flags and decryption keys are jointly generated by n organizers and released via an off-chain ($t, n$) Shamir–BLS threshold signature produced through multi-party computation (MPC), preventing any single organizer from leaking or altering keys. Teams submit zk-PLONK proofs that the contract verifies, timestamps, and records immutably. Under standard assumptions (collision-resistant hashing, SNARK soundness/zero-knowledge, IND-CCA2 ECIES, and at least t honest organizers), we prove that zk–MPSFV achieves the stated security goals, including DAG-gated progress, anti-replay, and threshold-robust organizer security, while out-of-band flag sharing remains out of scope. On a three-organizer testbed with 30 simulated teams, setup costs 0.45 ms per sub-flag, proof generation averages 5.34 s on an 8-core system, and on-chain verification costs $\approx$ 170kL2 gas on zkSync Era with a median fee of 1.33 $\times 10^{-6}$ ETH (about ${\$}$0.0046 at ${\$}$3,435/ETH). Stress replays sustain $\approx$ 7 proof transactions/s up to 5000 proofs; extrapolating to 50,000 proofs (1000 teams $\times$ 50 submissions) yields $\approx$ 0.0665 ETH (about ${\$}$200–${\$}$228) and $\approx$ 2 hours of settlement time. Overall, zk-MPSFV is practical for small- to mid-scale, audit-ready progression CTFs.
S. Khanji, Behzad Abdolmaleki, John A. Clark et al.· IEEE Computer Security Found...· 0 citations
Graph encryption schemes (GES) enable secure outsourcing of graph data while supporting efficient queries. This report provides a comprehensive analysis of structural leakage in GES for single-pair shortest path (SPSP) queries, integrating findings from two recent works. First, we analyze PathGES, a scheme designed to resist query recovery attacks through heavy-light decomposition (HLD) and canonical fragment encoding. Our analysis reveals that PathGES suffers from significant imbalances in HLD decomposition, with over 99% of token-path mappings being one-to-one on real-world datasets, enabling both the Falzon-Paterson attack and side-channel inference of path lengths. Second, we present Fragment Tree attack that exploits these structural weaknesses to recover query contents, achieving up to 10.24% exact recovery on sparse graphs. Third, we introduce BlindGES, an enhanced scheme incorporating a Merge-and-Divide mechanism and two-level multimap index that reduces one-to-one mappings to below 20%, cuts setup time by 50%, reduces storage overhead by 32%, and limits path length leakage to under 1%. This report systematically presents attack methodologies, defense mechanisms, security proofs, and experimental evaluations on seven real-world datasets.
Threshold signatures distribute trust across multiple parties, eliminating single points of failure and reducing insider and key-exfiltration risks—properties that are increasingly important for high-assurance deployments and recently emphasized by NIST’s Multi-Party Threshold Cryptography (MPTC) initiative. We present a practical t-out-of-n threshold variant and emulation of MAYO, a post-quantum signature candidate to NIST’s call for additional signatures. Our proposal builds upon the threshold MAYO design of Celi, Escudero and Niot (PQCrypto 2025), which we significantly refine to achieve practical performance. To this end, we introduce two algorithmic modifications to MAYO tailored for the distributed setting: (1) Explicit- Salt MAYO, which allows for pre-determined salts to enable a single-round online phase; and (2) Depth-Reduced MAYO, which restructures the signing algorithm to minimize the depth of secret-dependent operations. We then propose a unified protocol framework that integrate these techniques, plus other MPC specific optimizations, with the goal of minimizing online latency. Finally, we provide a concrete instantiation and local emulation in the dishonest majority setting, secure against active adversaries. Our emulation shows that threshold signing is practical at typical threshold sizes and amenable to deployment. By releasing an open-source implementation and reporting end-to-end performance, this work offers a concrete reference for the thresholdization of post-quantum signatures. Clearly the aforementioned framework is not limited to MAYO, and can be applied to the UOV family of signatures more generally.
Diego F. Aranha, Giacomo Borin, Sof'ıa Celi et al.· IACR Cryptology ePrint Archi...· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
