BlindStep speeds up secure collaboration in data matching
BlindStep: A Secure One-Step Kernel for Privacy-Preserving Collaborative Reasoning
Cryptography and Security
Summary
When two people or groups try to combine their private information without revealing too much, they need a careful way to work together securely. The authors designed BlindStep, a special tool that helps two parties securely score and select the best matching items without exposing sensitive details in the process. They tested different methods and found some versions of BlindStep run much faster and require less communication than others, depending on the network conditions. This helps keep privacy intact while making the collaboration more efficient.
What this means in practice
- •For data privacy teams: Implement secure data matching steps that limit information exposure and improve speed in two-party collaborations.
- •For cloud security engineers: Integrate efficient privacy-preserving kernels for online secure computations between semi-trusted cloud services.
Authors
Xiaoxian Liu, Xingyu Tan, Chen Chen, Xiaoyang Wang
Abstract
A recurring step in two-party collaborative workflows combines a private candidate frontier with a partner's compatible evidence, scores the resulting candidates, and retains only a small frontier. Direct execution can expose intermediate candidates, local scores, or unauthorized evidence provenance. Existing MPC platforms and PSI protocols provide useful building blocks, but they do not define a unified post-alignment boundary for bounded-slot aggregation, fail-closed overflow handling, retained-frontier selection, and downstream disclosure. We present BlindStep, a fixed-shape MPC-online kernel for one such post-alignment step between two semi-honest parties. Given a frontend realizing the bounded-slot contract and an application enforcing the reveal policy $ρ$, BlindStep provides a per-invocation simulation-based guarantee in the $F_{\mathrm{align}}$-hybrid model: the kernel leaks only public setup parameters, fixed execution-shape metadata, a global overflow bit, and $ρ$-authorized Layer-2 disclosures. The guarantee excludes malicious security and multi-invocation composition, and treats frontend leakage and offline preprocessing separately. Within this kernel boundary, we implement six semi2k realizations in MP-SPDZ, crossing two sharing styles and three top-K strategies: H-variants compare over arithmetic shares, while B-variants convert packed ranking values to Boolean shares before selection. Under LAN, B-Queue is 6-7 times faster and uses about 40 times less communication than H-Queue at N = 256 and 2048. Against H-Sort on the same backend, B-Queue achieves speedups of 21 and 30 times and communication reductions of 204 and 290 times at N = 2048 and 8192, respectively. Under the evaluated N = 256, 100 ms RTT WAN profile, H-Sort becomes fastest, showing that round complexity can dominate backend choice for the measured MPC-online kernel.