Paper 2025/200

Improved Secure Two-party Computation from a Geometric Perspective

Hao Guo, Chinese University of Hong Kong, Shenzhen
Liqiang Peng, Alibaba Group (China)
Haiyang Xue, Singapore Management University
Li Peng, Alibaba Group (China)
Weiran Liu, Alibaba Group (China)
Zhe Liu, Zhejiang Lab
Lei Hu, Institute of Information Engineering, Chinese Academy of Sciences
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. Multiplication and non-linear operations are well known to be the most expensive protocols in secure two-party computation (2PC). Moreover, the comparison protocol (or 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 to in two rounds, where 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\%.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2025
Contact author(s)
guohao g @ outlook com
plq270998 @ alibaba-inc com
haiyangxc @ gmail com
jerry pl @ alibaba-inc com
weiran lwr @ alibaba-inc com
sduliuzhe @ gmail com
hulei @ iie ac cn
History
2025-02-20: last of 2 revisions
2025-02-11: received
See all versions
Short URL
https://ia.cr/2025/200
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2025/200,
      author = {Hao Guo and Liqiang Peng and Haiyang Xue and Li Peng and Weiran Liu and Zhe Liu and Lei Hu},
      title = {Improved Secure Two-party Computation from a Geometric Perspective},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/200},
      year = {2025},
      url = {https://eprint.iacr.org/2025/200}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.