Improved secure two-party computation from a geometric perspective

Author

Hao GUO
Liqiang PENG
Haiyang XUE
Li PENG
Weiran LIU
Zhe LIU
Lei. HU

Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

8-2025

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%.

Discipline

Information Security

Areas of Excellence

Digital transformation

Publication

SEC '25: Proceedings of the 34th USENIX Conference on Security Symposium, Seattle, USA, August 13-15

First Page

4957

Last Page

4974

Identifier

10.5555/3766078.3766333

Publisher

ACM

City or Country

New York

Citation

GUO, Hao; PENG, Liqiang; XUE, Haiyang; PENG, Li; LIU, Weiran; LIU, Zhe; and HU, Lei.. Improved secure two-party computation from a geometric perspective. (2025). SEC '25: Proceedings of the 34th USENIX Conference on Security Symposium, Seattle, USA, August 13-15. 4957-4974.
Available at: https://ink.library.smu.edu.sg/sis_research/10975

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.

Additional URL

https://doi.org/10.5555/3766078.3766333