## 3 Construction
### Construction of iPPSP  
Now, we elaborate on the construction of our iPPSP protocol. Important notation and parameters of our protocol are presented in Table 1. \begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Meaning** \\ \hline \(\lambda\) & Security Parameter \\ \hline \(C\) & Client. The IoT devices \\ \hline \(S\) & Server. The edge computing devices \\ \hline \(n\) & The length of input vector \\ \hline \(\mathbf{W}\) & \(n\times m\) dimensional weight matrix \\ \hline \(\mathcal{R}\) & Secret key pool \\ \hline \(s\) & Secret key pool size \\ \hline \(T\) & Pad Generation Parameter \\ \hline \(\tau_{i}\) & Random Indices \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of notation and parameters. Figure 3: High-level workflow of iPPSP primitive. **Interactive Privacy-Preserving Scalar Product (iPPSP)**: As described in Algorithm 2, in iPPSP the client \(C\) has an input vector \(\mathbf{x}=(x_{1},x_{2},\cdots,x_{n})\) and wants to compute the scalar product with weight matrix \(\mathbf{W}=(\mathbf{W}_{1},\mathbf{W}_{2},\cdots,\mathbf{W}_{n})^{\intercal}\), where each \(\mathbf{W}_{i}\) is a vector of dimension \(m\). After an edge device responds to the outsourcing request from the IoT device, they will interactively execute Algorithm 2. ```
Data:\(n\)-dimensional input vector \(\mathbf{x}\), Weights matrix \(\mathbf{W}_{n\times m}\) Result:\(m\) dimensional vector \(\mathbf{A}=\mathbf{x}\cdot\mathbf{W}\) Initialization: \(C\) generates a \(s\)-tuple \(\mathcal{R}=(r^{(0)},r^{(1)},\cdots,r^{(s-1)})\); \(C\) computes tensor product \(\mathcal{R}\otimes\mathbf{W}_{i}\) for \(i=1,2,\cdots n\) and stores the result; for\(i=1\to n\)do Encryption: \(C\) executes Algorithm 3 to generate an encryption pad \(\mathbf{r}\); \(C\) computes \(\mathcal{C}=\mathbf{x}+\mathbf{r}\) and sends \(\mathcal{C}\) to server \(S\); Report: \(S\) computes and sends to \(C\): \(\mathbf{a}_{i}=\mathcal{C}\cdot\mathbf{W}_{i}\); \(C\) decrypts the message with pre-computation table: \(\mathbf{A}_{i}=\mathbf{a}_{i}-\mathbf{r}\cdot\mathbf{W}_{i}\); \(i=i+1\);  end for
```  
**Algorithm 2**Interactive Privacy-Preserving Scalar Product (iPPSP)  
**Initialization:** For an input vector \(\mathbf{x}\), each entry \(x_{i},\ i=1,2,\cdots,n\) is a \(\kappa\)-bit number. The client first generates a sequence of random numbers \(r^{(0)},r^{(1)},\cdots,r^{(s-1)}\) from \(\mathbb{Z}_{q}\), where \(q=2^{l}\), and these random numbers form the secret key pool \(\mathcal{R}\). Notice that each element \(r^{(j)}\) is \(l\)-bit (\(l>\kappa\)) and is generated by a _pseudo-random generator_ (PRG). During the Initialization phase, the client computes \(n\) tensor products \(\mathcal{R}\otimes\mathbf{W}_{i}\) for \(i=1,2\cdots,n\) and stores the result in a pre-computation table which will be used in decryption. The pre-computation table for a single tensor product \(\mathcal{R}\otimes\mathbf{W}_{1}\) is shown in Table 2.  
Moreover, in this phase, a system parameter \(T\in\mathbb{Z}_{s}\) is also generated. **Pad Generation:** Each time the client needs to outsource a scalar product calculation for input vector \(\mathbf{x}\) of dimension \(n\), it executes Algorithm 3 to generate a pad of the same dimension to be used for encryption. Notice that, during the initialization phase, \(C\) generates a sequence of random numbers \(r^{(0)},r^{(1)},\cdots,r^{(s-1)}\) as master secrets stored in the key pool \(\mathcal{R}\). To generate an encryption pad \(\mathbf{r}_{i}\), \(C\) randomly selects \(T\) (a system parameter determined in the Initialization phase) indices \(\gamma_{1},\cdots,\gamma_{T}\in\mathbb{Z}_{s}\) and computes the following:  
\[\mathbf{r}_{i}=r^{(\gamma_{1})}+r^{(\gamma_{2})}+\cdots+r^{(\gamma_{T})}. \tag{1}\]  
An \(n\)-dimensional pad \(\mathbf{r}=(\mathbf{r}_{1},\mathbf{r}_{2},\cdots,\mathbf{r}_{n})\) is generated for an \(n\)-dimensional input \(\mathbf{x}\).