Memory and Round-Efficient MPC Primitives in the Pre-Processing Model from Unit Vectorization
Type
conference paper
Date Issued
2022-05
Author(s)
Abstract
In this paper, we propose memory- and round-efficient protocols for securely evaluating arithmetic primitives. We focus on secure two-party computation over the ring ℤ2k that achieves security against semi-honest adversaries and works in the pre-processing model. Our protocols rely on the unit vectorization technique introduced by Boyle et al. (TCC 2019). The unit vectorization technique provides online-optimal protocols for several fundamental operations in the pre-processing model. However, a relatively large memory cost for correlated randomness is required, which might become an obstacle in a large-scale application. In order to achieve both memory and communication efficiency, we propose a size reduction method that uses unit vectorization only for short-length inputs, and based on this, construct two-round protocols for equality test, detecting the most significant non-zero bit, detecting wrap-around, and less-than comparison. In addition, as applications of these results, we provide practically efficient protocols for integer division, integer square root, integer logarithm, and modular exponentiation.
Language
English
HSG Classification
contribution to scientific community
Start page
858
End page
872
Pages
15
Event Title
AsiaCCS 2022
Event Location
Nagasaki, Japan
Event Date
May 30-June 3
Subject(s)
Division(s)
Eprints ID
269452
File(s)![Thumbnail Image]()
Name
Memory and Round-Efficient MPC Primitives in the Pre-Processing Model from Unit Vectorization.pdf
Size
1.25 MB
Format
Adobe PDF
Checksum (MD5)
9121ea29b09eed84a4d58ecddefbe62f