USENIX Security2025Top-tier venue
Improved Secure Two-party Computation from a Geometric Perspective
Hao Guo, Liqiang Peng, Haiyang Xue, Li Peng, Weiran Liu, Zhe Liu, Lei Hu
Abstract
Multiplication and other non-linear operations are widely recognized as the most costly components of secure two-party computation (2PC) based on linear secret sharing. Moreover, the comparison protocol (or Wrap protocol) is essential for various operations such as truncation, signed extension, and signed non-uniform multiplication. This paper aims to optimize these protocols by avoiding invoking the costly comparison protocol, thereby improving their efficiency. We propose a novel approach to study 2PC from a geometric perspective. Specifically, we interpret the two shares of a secret as the horizontal and vertical coordinates of a point in a Cartesian coordinate system, with the secret itself represented as the corresponding point. This reformulation allows us to address the comparison problem by determining the region where the point lies. Furthermore, we identify scenarios where the costly comparison protocol can be replaced by more efficient evaluating AND gate protocols within a constrained range. Using this method, we improve protocols for truncation, signed extension and signed non-uniform multiplication, all of which are fundamental to 2PC. In particular, for the one-bit error truncation protocol and signed extension protocols, we reduce the state-of-the-art communication complexities of Cheetah (USENIX'22) and SirNN (S&P'21) from ≈ λ(l + 1) to ≈ λ in two rounds, where l is the input length and λ is the security parameter. For signed multiplication with non-uniform bit-width, we reduce the communication cost of SirNN's by 40% to 60%.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- CrypTFlow2: Practical 2-Party Secure Inference cites Oblivious Neural Network Predictions via MiniONN Transformations
- CrypTFlow2: Practical 2-Party Secure Inference cites SecureML: A System for Scalable Privacy-Preserving Machine Learning
- Oblivious Neural Network Predictions via MiniONN Transformations cites SecureML: A System for Scalable Privacy-Preserving Machine Learning
- ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation cites MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer
- ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation cites SecureML: A System for Scalable Privacy-Preserving Machine Learning
- Reliable and Private Utility Signaling for Data Markets cites SecureML: A System for Scalable Privacy-Preserving Machine Learning
- Efficient and High-Accuracy Secure Two-Party Protocols for a Class of Functions with Real-number Inputs cites CrypTFlow2: Practical 2-Party Secure Inference
- Efficient and High-Accuracy Secure Two-Party Protocols for a Class of Functions with Real-number Inputs cites Oblivious Neural Network Predictions via MiniONN Transformations
- Efficient and High-Accuracy Secure Two-Party Protocols for a Class of Functions with Real-number Inputs cites SecureML: A System for Scalable Privacy-Preserving Machine Learning
Cited by top-tier papers2
- Reliable and Private Utility Signaling for Data MarketsLi Peng, Jiayao Zhang, Yihang Wu, Weiran Liu et al.SIGMOD 2026 · 1 citation
- Efficient and High-Accuracy Secure Two-Party Protocols for a Class of Functions with Real-number InputsHao Guo, Zhaoqian Liu, Liqiang Peng, Shuaishuai Li et al.USENIX Security 2026 · 1 citation
Builds on13
- SecureML: A System for Scalable Privacy-Preserving Machine LearningPayman Mohassel, Yupeng ZhangS&P 2017 · 2,107 citations
- Oblivious Neural Network Predictions via MiniONN TransformationsJian Liu, Mika Juuti, Yao Lu, N. AsokanCCS 2017 · 800 citations
- MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious TransferMarcel Keller, Emmanuela Orsini, Peter SchollCCS 2016 · 487 citations
- ABY2.0: Improved Mixed-Protocol Secure Two-Party ComputationArpita Patra, Thomas Schneider, Ajith Suresh, Hossein YalameUSENIX Security 2021 · 307 citations
- CrypTFlow2: Practical 2-Party Secure InferenceDeevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran et al.CCS 2020 · 294 citations
Related papers
- Bicoptor: Two-round Secure Three-party Non-linear Computation without Preprocessing for Privacy-preserving Machine LearningLijing Zhou, Ziyu Wang, Hongrui Cui, Qingrui Song et al.S&P 2023
- Efficient 2PC for Constant Round Secure Equality Testing and ComparisonTianpei Lu, Xin Kang, Bingsheng Zhang, Zhuo Ma et al.USENIX Security 2025
- Improved Primitives for MPC over Mixed Arithmetic-Binary CircuitsDaniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri et al.CRYPTO 2020 · 123 citations
- Sublinear Distributed Product Checks on Replicated Secret-Shared Data over Z2k Without Ring ExtensionsYun Li, Daniel Escudero, Yufei Duan, Zhicong Huang et al.CCS 2024 · 1 citation
- Cheetah: Lean and Fast Secure Two-Party Deep Neural Network InferenceZhicong Huang, Wen-jie Lu, Cheng Hong, Jiansheng DingUSENIX Security 2022
