## 4 Building Blocks
### Replicated Secret Sharing Technique  
The 2-out-of-3 replicated secret sharing (RSS) was proposed by [PERSON] et al [33] with high throughput and low latency. Let \(l\) be a general modulus, the method can work for arithmetic circuits over the ring modulo \(2^{l}\) and Boolean circuits with \(l=1\). \(\langle\cdot\rangle_{i}\) represents arithmetic sharing obtained by server \(P_{i}\). \(\llbracket\cdot\rrbracket_{i}\) represents boolean sharing in \(\mathbb{Z}_{2}\) obtained by server \(P_{i}\). The replicated secret sharing for three parties is described as follows:  
* \(\langle x\rangle\leftarrow\mathit{share}(x)\): For the secret value \(x\in\mathbb{Z}_{2^{l}}\), the protocol samples three random values \(x_{1},x_{2},x_{3}\) under the constraint that \(x\equiv x_{1}+x_{2}+x_{3}\bmod 2^{l}\). Each participant owns a portion. \(P_{i}\in{0,1,2}\) gets \((x_{i},x_{i+1})\). And it can be written as \(\langle x\rangle:=(x_{1},x_{2},x_{3})\).
* \(x\leftarrow\mathit{reconstruct}(\langle x\rangle)\): To reconstruct and reveal \(x\), \(P_{i}\) sends \(x_{i}\) to \(P_{i+1}\), each party can compute sum of \(x_{1},x_{2},x_{3}\in\mathbb{Z}_{2^{l}}\) locally, which means the secret value \(x\) is revealed to each party.  
We also describe the addition and multiplication operations as follows:  
The addition and subtraction operations between two shares can be computed locally with their linearity properties, which means we can get secret values \(\langle x+y\rangle\) with two shares \(\langle x\rangle=(x_{1},x_{2},x_{3})\), \(\langle y\rangle=(y_{1},y_{2},y_{3})\). The secret value \((\langle x\rangle+c)\) is summed with the constant value \(c\), it can obtain with \((\langle x\rangle+c:=(x_{1}+c,x_{2}),(x_{2},x_{3}),(x_{3},x_{1}+c))\). Similarly, \(\langle ax\pm by\pm c\rangle\) can be computed as \((ax_{1}\pm y_{1}\pm c,ax_{2}\pm y_{2},ax_{3}\pm byy_{3})\) on the local side.  
For the operation of multiplying two secret values \(\langle xy\rangle\), \(P_{1},P_{2},P_{3}\) first hold correlated randomness \(a,\beta,\gamma\), respectively, whose detailed generation process can be seen in [33]. The correlate randomness meets \(\alpha+\beta+\gamma=0\). \(P_{0}\) computes \(z_{0}=x_{0}y_{0}+x_{0}y_{1}+x_{1}y_{0}+\alpha\) and sends it to \(P_{1}\); \(P_{1}\) computes \(z_{1}=x_{1}y_{1}+x_{1}y_{2}+x_{2}y_{1}+\beta\) and sends it to \(P_{2}\); \(P_{2}\) computes \(z_{2}=x_{2}y_{2}+x_{2}y_{0}+x_{0}y_{2}+\gamma\) and sends \(z_{2}\) to \(P_{1}\). The resharing process is performed for 2-out-of-3 sharing. \(P_{i}\) then sends \(z_{i}\) to \(P_{i+1}\).  
Figure 2: System Model.  
The protocol has very low communication: addition operation can be computed locally. For each multiplication gate, although parties need to interact to complete, RSS reduces half of the communication overhead compared with traditional ASS in the 3 PC setting.  
Note that decimals in the computation are unavoidable in the computation of a privacy-preserving outsourcing convolutional neural network, the truncation of the decimal fraction is necessary while secret sharing works on the integer values. The real data in the whole process of a neural network is rounded and scaled into \(\mathbb{Z}_{2l}\). For the real number \(x,y\), assuming that the number of decimal places is \(q\) when the real numbers are multiplied, the length of the decimal part of the result is \(2q\), which will exceed the length of \(l\) bits. We simply truncate the last \(q\) bits to ensure the numerical representation of length. This process will inevitably cause accuracy loss, but it is proven that the accuracy loss is within the reasonable range. The truncation technique of the decimal fraction is also introduced in [24].