Bicoptor: Two-round Secure Three-party Non-linear Computation without Preprocessing for Privacy-preserving Machine Learning

The overhead of non-linear functions dominates the performance of the secure multiparty computation (MPC) based privacy-preserving machine learning (PPML). This work introduces a family of novel secure three-party computation (3PC) protocols, Bicoptor, which improve the efficiency of evaluating non-linear functions. The basis of Bicoptor is a new sign determination protocol, which relies on a clever use of the truncation protocol proposed in SecureML (S&P 2017). Our 3PC sign determination protocol only requires two communication rounds, and does not involve any preprocessing. Such sign determination protocol is well-suited for computing non-linear functions in PPML, e.g. the activation function ReLU, Maxpool, and their variants. We develop suitable protocols for these non-linear functions, which form a family of GPU-friendly protocols, Bicoptor. All Bicoptor protocols only require two communication rounds without preprocessing. We evaluate Bicoptor under a 3-party LAN network over a public cloud, and achieve more than 370,000 DReLU/ReLU or 41,000 Maxpool (find the maximum value of nine inputs) operations per second. Under the same settings and environment, our ReLU protocol has a one or even two orders of magnitude improvement to the state-of-the-art works, Falcon (PETS 2021) or Edabits (CRYPTO 2020), respectively without batch processing.

In this updated version of our paper, which was originally presented at S&P 2023 [1], we address certain security concerns raised by Xu et al [2] in his paper regarding our DReLU protocol (Alg. 2). The concerns stem from an omission of a standard step: resharing, in our protocol. In MPC, resharing is free and default. In this latest version, we have included a detailed explanation of this aspect in App. E. 1. For example, for ξ = x = 23 = 0b00010111, ℓx = 8, λ = 5, and ξ λ-1 = ξ 4 .

2. In general, MPC offline phase includes both preprocessing and distributing shared randomness. The overhead of distributing shared randomness (usually one time) is much cheaper than that of preprocessing. It is worth distinguishing between these two ideas for the rest of the paper. Most previous MPC-based PPML works [14], [15], [16], [18], [20], [21], [22], [23], [27] require preprocessing which is heavily computed.

3. We select the honest-majority and passive-secure settings in Edabits and Falcon. Edabits [27] does not have a Maxpool design.