Secure multi-party computation (MPC) facilitates privacy-preserving computation between multiple parties without leaking private information. While most secure deep learning techniques utilize MPC operations to achieve feasible privacy-preserving machine learning on downstream tasks, the overhead of the computation and communication still hampers their practical application. This work proposes a low-latency secret-sharing-based MPC design that reduces unnecessary communication rounds during the execution of MPC protocols. We also present a method for improving the computation of commonly used nonlinear functions in deep learning by integrating multivariate multiplication and coalescing diferent packets into one to maximize network utilization. Our experimental results indicate that our method is efective in a variety of settings, with a speedup in communication latency of 10 ∼ 20%.
Secure multi-party computation (MPC) [
In general, privacy-preserving deep learning frameworks
usually adopt secret-sharing-based techniques to avoid
extensive computational overheads [
Our main contributions are as follows: • We propose a low-latency secret-sharing-based method for computing multivariate multiplications and univariate polynomials using network communication that is eficient and reduces unnecessary communication rounds on the fly. • We improve the computation of nonlinear functions by integrating the proposed multivariate multiplication and coalescing diferent packets into one single packet to maximize network utilization. • We conducted experiments to evaluate the efectiveness of our method in the context of models with varying sizes, networks with diferent latency and bandwidth, the accuracy of downstream classification tasks, and the number of participants involved. The results indicate an overall improvement of 10 ∼ 20% in communication latency.
Our setup is primarily focused on arithmetic operations, so we represent all inputs and intermediate results in terms of linear secret sharing between parties, especially in the context of additive secret-sharing schemes.
Apart from the general (, )-Shamir secret sharing
scheme [
When parties wish to share a value , they generate a pseudorandom zero-share that sums to 0. The party that possesses the value adds to their share in secret. To represent lfoating-point numbers, we adopt a fixed-point encoding to encode any floating-point number into a fixed-point representation, . Alternatively, we consider that each is the result of multiplying a floating-point number by a scaling factor = 2 and rounding to the nearest integer, i.e. = ⌊ ⌉. Here is the precision of the fixed-point encoding. To decode a ground-truth floating-point value from , we compute as follows: ≈ /.
It is noteworthy that arithmetic secret shares are homomorphic and can be used to implement secure MPC, especially in the context of linear computation in most cases. Addition. The sum of two secret shared values [] and [] could be directly computed as [] = [] + [], where each party ∈ computes [] = [] + [] without multi-party communications.
Multiplication. Two secret shared values [] and [] are
multiplied using a random Beaver triple [
Linear functions. It is possible to implement functions that consist of linear operations by combining additions and multiplications. Common operations in deep learning, such as element-wise product and convolution, are allowed in a linear paradigm.
Nonlinear functions. Due to the inherent infeasibility of nonlinear functions in the standard arithmetic secretsharing scheme, most works use approximation methods to simulate the outcome of nonlinear functions. In particular, Taylor Expansion, Newton-Rhapson, and Householder methods are commonly used to approximate nonlinear functions using only linear operations. All reciprocal functions, exponential functions, loss functions, kernel functions, and other useful functions in deep learning are calculated this way, for example.
Algorithm 1 Beaver Multiplication Mul([], []) Input: Secret-shared inputs [], [],
([], [], []).
Output: [].
1: ◁ Compute masked values 2: [ ] ← [ − ] = [] − [] 3: [ ] ← [ − ] = [] − [] 4: ◁ Reveal and through one-round communications 5: ← Reveal([ ]) 6: ← Reveal([ ]) 7: return + [] + [] + [] Beaver triple
This section summarizes the notations used throughout this work. We denote [] as a secret sharing of . Reveal([]) means that the ground-truth value is revealed to every party involved in the computation through one-round communications. Since most linear operations are also applicable to element-wise operations and matrix operations, can also represent a vector, matrix, or even a tensor if there is no confusion and ambiguity.
To achieve communication-eficient MPC, various
approaches have been developed to optimize the
communication rounds and the throughput of communication. Ishai
and Kushilevitz [
In recent years, several deep learning frameworks that
preserve privacy have emerged to enable the secure
inference of neural network models. Wagh et al. [
Since Beaver triples illustrate how to multiply two variables with pre-shared triplets, a classic multiplication between multiple variables, such as [], requires several rounds of binary multiplication, i.e. Mul(Mul([], []), []). This naive implementation, however, introduces additional communication rounds during the on-the-fly Reveal process. In general, a -ary multiplication requires − 1 rounds of communication.
To reduce the communication rounds involved in the multivariate multiplications, the basic binary Beaver triple is extended into a general -ary Beaver triple. This results in only one round of communication required throughout the entire process.
Assume the inputs could be represented as {[]}=1. The precomputation and preshared information required by the extended protocol is {}=1. Here 1 := {[ ]}=1 is defined as the set of auxiliary shared values used to blind the the inputs {[]}=1, which is also similar to the Beaver’s idea. Then ( ≥ 2) is defined as the set of shared degree- cross-terms consisting of the variables in 1. For example, 2 could be defined as 2 := {[ ] | ̸= ∧ 1 ≤ ∧ 1 ≤ , , ≤ , ≤
}, and 3 := {[ ] | ̸= ̸= }, and so on. Similar to the construction of [ ] and [ ] in Section 2.2, we define the diference between the inputs and the masks as [ ] := [] − shared [ ] is then made public across all parties without leakage to the ground-truth value of both [] and []. The improvement of our method originates from the following []. The secretequation: =1 ∏︁ = ∏︁( + ) =1 + · · · = ∏︁ + ∑︁
+ ∏︁ .
∏︀ + ∑︁ ,,̸= ∏︀ (1) follows: =1 [∏︁ ] = ∏︁ + ∑︁
[ + · · ·
+ [∏︁ ]. which is preshared across all parties.
Here we informally use the fractional representation, such as ∏︀ , to denote the products of all the terms except for certain ones. Note that this fractional form does not involve any actual division. Also, each secret-shared term of [ ∏︀... ] could be found in the auxiliary sets {}=1, Adaptation of Equation 1 in secret-sharing scheme is as ∏︀ ] + ∑︁ [ ,,̸= ∏︀ ] Since Equation 2 is linear to the secret-sharing terms, all communications could be conducted in parallel, i.e. in a single round of communications. In this case, we could simply reveal all the secret-sharing terms in {}=1 and compute the sharing of final results in constant complexity. The protocol is formally described in Algorithm 2. Algorithm 2 Multivariate Beaver Multiplication of inputs Mul([1], [2], . . . , []) Input: Secret-shared inputs {[]}=1, auxiliary sets 5: ◁ Reveal through one-round communications {}=1.
Output: [∏︀ ].
1: ◁ Compute masked values 2: for ∈ [1, ] do 3: 7: 4: end for 6: parallel for ∈ [1, ] do ←
Reveal([ ])
[ − ] = [] − [] · · ·
+ [∏︀ ] 8: end parallel for 9: ◁ Compute results using preshared {}=1 10: return ∏︀ + ∑︀ [
∏︀ ] + ∑︀ ,,̸= [ ∏︀ ] +
The total rounds of communications are indeed reduced from is performed, but the overall size of communication data − 1 to constant 1 when a regular -ary multiplication increases from linear to exponential. In a naïve implementation, the data size of -ary multiplication is only 3( − 1) for a total transmission of − to a multivariate implementation, it is 2 − 1 to transmit 1 Beaver triples. As opposed the auxiliary sets {}=1. Therefore, in practice, there is a trade-of between communication latency and throughput.
The formal form of univariate polynomials is defined as () = ∑︀
=0 , where refers to the coeficients of
the degree- term. The use of univariate polynomials
enables eficient evaluation and manipulation of polynomial
expressions. According to Damgård et al. [
This method can be implemented in practice by computing a tuple of base terms and then multiplying the tuple by a certain term iteratively, as in the exponentiating by squaring method or the fast modulo algorithm. In other words, a tuple = (1, , . . . , − 1 multiplied by ‖‖ repeatedly to iterate all the terms. The overview of the implementation of univariate polynomials is described in Algorithm 3. Note that : is the subvector ) of size ‖‖ = could be of from position to .
Algorithm 3 Univariate Polynomial Poly([], )
coeficients = Output: ∑︀ =0 [].
2: parallel for ∈ [1, ‖‖] do (0, 1, . . . , ), base terms size ‖‖.
Mul([], . . . , []) ◁ multiplied by [] of
In this section, we take one step further to optimize the commonly used nonlinear functions by leveraging the property of parallelization of our proposed multivariate multiplication.
Exponentiation.
Since exponential functions grow in geometrical speed, approximations based on series expansion generally sufer from a significant reduction in accuracy since we do not know the exact value of the input. Consequently, we resort to the naive iterative approximation, which is capable of utilizing multivariate multiplication effectively: [] = lim →∞ ︂( 1 + [] )︂ . (2) times
[] ← 3: 5: ← 7: ← 9: 10: 11: 12: 13: 0 s e ← ← ← ← 14: end for 15: return 4: end parallel for
(1, [], . . . , [‖‖− 1]) 6: ◁ Iteratively exponentiating
8: for ∈ [0, ⌊ ‖‖ ⌋ − 1] do · ‖ ‖ ( + 1) · ‖ ‖ + : · [‖‖] · ◁ Vectorized Beaver Multiplication During each iteration, the -th power of the previous result is calculated. With increasing iteration rounds , the answer would become closer to the actual results.
Logarithm. The calculation of logarithms relies on the higher-order iterative methods for a better convergence, i.e. Householder methods on = ln :
[ℎ] = 1 − []− [] [+1] = [] − ∑∞︁ 1
=1 [ℎ] Note that the implementation of logarithm is the combination of exponentiation and univariate polynomials. The degree of the polynomials determines the precision of the output.
Reciprocal. The reciprocal function = 1 is calculated using the Newton-Raphson method with an initial guess 0: [+1] = [](2 − [][])
= 2[] − [][][] Trigonometry. Trigonometric functions could be treated as the special case of exponentiation with = 2. The sine and cosine functions are calculated in the field of complex numbers: [sin ] = Im([]) [cos ] = Re([])
Using the above-mentioned nonlinear functions, we can calculate most of the existing loss functions in deep learning, such as the sigmoid, tanh, and cross-entropy functions. Various other common nonlinear functions, such as the softmax function and kernel function, can also be calculated using exponential and reciprocal functions.
The key to achieving low-latency secret-sharing computation is to reduce the total number of rounds of communications among diferent parties. While we introduce a latency-friendly implementation of basic math operations, other kinds of communications, such as precision checking, still require an additional but independent communication round.
In general, the communication involved in multiple math operations could be abstracted as a communication graph, or strictly, as a communication tree. Accordingly, we observe some independent communications that do not afect downstream results can be deferred and combined into one single round of communication. This process is referred to as communication coalescing, and it eliminates unnecessary rounds of communication and improves the utilization of network bandwidth.
The correctness of the multivariate multiplication is trivial based on the observation in Equation 1 and 2. As univariate polynomials are implemented using the same method as the extended fast modulo algorithm, their efectiveness could also be demonstrated by the correctness and security of multivariate multiplication. Coalescing mechanisms only alter the order of communication rounds without modifying the payload, which is also reliable and secure.
Multivariate computations are similarly secure as traditional Beaver multiplications under semi-honest conditions. It is intuitively obvious that since is chosen at random by TTP, the = − value is indistinguishable from a random number. Consequently, the disclosure of [ ] does not reveal any critical information regarding . This assumption holds even if multiple parties, except for the TTP, collude.
To clarify the security of multivariate multiplication formally, we denote [] as the secret share of for party ∈ . The global equations of the multivariate system are as follows: ∑︁[] = ∈ ∑︁[] = ∈ ∑︁[ ] = ∈
. . . . . .
∑︁[1 . . . ] = 1 . . .
∈
[] − [] = [ ]
(3)
with known [ ] for every ∈ to each party. From each
party’s view, these 2 + 2 − 1 equations have Θ(2 ‖‖)
unknown variables. This indicates the dificulty in
determining the exact value of , as shown in [
A party’s view represents all the values it can obtain during its execution. Then the following theorem holds: Theorem 1. Let {′} and {′′} be random values. The distribution of the view of each party is identical when = ′ or = ′′.
This guarantees the security of multivariate multiplication by ensuring the indistinguishability between the random distribution and the view’s distribution.
As part of our proposed methodology, we use CrypTen [
To measure the performance, we perform several
experiments with deep learning models with diferent sizes:
(a) Linear Support Vector Classification (LinearSVC) with
L2 penalty; (b) LeNet [
Each of our experiments is conducted in a simulated multinode environment using Docker. TTP is conducted in an independent environment separate from the normal parties. To manually simulate diferent network environments concerning bandwidth and latency, we utilize the docker-tc tool to adjust the docker network settings accordingly.
To provide a comprehensive evaluation of our proposed method, we adopt metrics from a variety of perspectives. • comp: The computational time cost for evaluating a single data sample in one round. • comm: The time cost of communication associated with evaluating a single data sample in one round. • Size of Transmission Data: The size of transmitted network packets when evaluating a single data sample in one round. • Accuracy: The classification accuracy when evaluated on a particular dataset.
To assess the eficiency of our proposed method, we simulate networks with diferent network latencies: (a) network low with 0.1ms latency, (b) network med with 5ms latency, (c) and network high with 40ms latency. All of these networks have a bandwidth of 1Gbps. Our simulated multinode settings include 3 nodes with an additional TTP by default.
As shown in Table 1, the computation cost of each model is negligible in medium and high latency network settings in comparison to the communication cost. Therefore, we will focus only on the communication costs associated with our proposed method.
Compared to the naïve method implemented by CrypTen, our method illustrated in Section 4.1 remains close since it does not introduce a substantial amount of additional communication payload if the maximum number of input variables is set appropriately. For instance, a 3-ary or 4-ary multiplication would not produce a significant increase in the total size of communications.
It is noteworthy that our proposed method reduces the communication cost in every network setting as compared to the naïve implementation of MPC. Overall, we achieve an improvement of 10 ∼ 20%, which shows significant enhancement in the performance of high-latency environments for practical purposes.
Furthermore, we observe that our proposed method behaves diferently with neural models with diferent architectures. Figure 1 illustrates the communication occupation percentage of ResNet basic blocks and Attention blocks. As can be seen, the attention mechanism is constrained by its communication bottleneck in Softmax operation, while CNN is constrained by its communication via convolutional operations. Considering that our method makes an improved optimization for nonlinear functions, attentionbased models show a significant improvement in latency, with almost a 25% improvement. Additionally, this explains the limited improvement of only 8 ∼ 15% in traditional machine-learning models and CNN-based models.
In this section, we examine the side efects and factors associated with the basic settings, such as the downstream tasks’ accuracy, the number of parties involved, and the trade-of between network latency and bandwidth.
To evaluate the drop in accuracy, we compare our method with both the original baseline and the naïve implementation without a low-latency design. Figure 2 shows that, in relatively small scenarios, both the naïve implementation and our methods are capable of achieving perfect performance as the baselines. Nevertheless, both MPC-based implementations obtain lower accuracy in complex scenarios than the baseline, while our methods perform slightly worse than the naïve implementation. We hypothesize that the multivariate multiplication introduces additional precision requirements, which in turn reduces accuracy.
The throughput and latency of MPC-based methods are Na¨ıve Ours 4
5 # Parties (a) Size of Trans. Data w.r.t # Parties 4
5 # Parties (b) Latency w.r.t # Parties also aefcted by the number of parties involved in the computation. From Figure 2, it can be seen that the communication data size of both methods increases linearly as the number of parties involved increases. There is, however, a tendency for the latency to be worse when there are more parties involved.
Moreover, Figure 3 illustrates how network bandwidth afects communication costs. When suficient bandwidth is available, our method can still optimize the network latency. It is important to note, however, that when the bandwidth becomes the bottleneck, our method would not be any more efective in reducing the overall costs of communication. This indicates that bandwidth remains an important factor in a multi-node MPC setting, especially as the number of nodes in use grows.
Since the proposed multivariate multiplication is based on a finite ring, it is likely to have precision issues that lead to incorrect results. Fortunately, a loss in precision would not significantly afect the overall performance of deep learning, since the loss could be interpreted as random noise and 6 6 distortion in the input data.
Moreover, our proposed method is only applicable to
functions that are based on linear MPC operation. To avoid
heavy communications, a modern MPC-based deep
learning framework would also involve other protocols, such as
Homomorphic Encryption [
This study proposes a secret-sharing-based MPC method for enhancing the linear computation required in deep learning through increased communication utilization. By utilizing the multivariate multiplication and communication coalescing mechanisms, we can reduce the number of unnecessary communication rounds during the execution of both linear and nonlinear deep learning functions. In our experiments, we demonstrate that our proposed methods achieve an overall improvement in latency of 10 ∼ 20% when compared to the naïve MPC implementation. Additionally, it indicates that throughput and downstream task performance are comparable to naïve implementations, which demonstrate the method’s validity and eficiency. We hope that this work will inspire future improvements in privacy-preserving deep learning techniques and lead to more practical MPC applications.
This work is supported by the National Key R&D Program of China under grant (No. 2022YFB2703001).