## 3 Retrieving Private Data with Optimization Processes on Homomorphic Encryption Schemes
### The Windowing Process  
In HE operations, the addition and multiplication results between a ciphertext and a plaintext will be in the ciphertext domain. If the depth of multiplication between two ciphertexts is too high, it is easy to cause errors in the obtained results. Therefore, if the Server directly performs the item-by-item operation on \(F_{x}(y;r)\), it is equivalent to doing \(\left|\,\mathsf{X}\,\right|\) times of inter-ciphertext multiplications. When \(\left|\,\mathsf{X}\,\right|\) is a large number (e.g., \(\left|\,\mathsf{X}\,\right|>2^{20}\)), the Server is prone to miscalculate the result.  
Assuming that the Client wants to retrieve the labels corresponding to \(y\) on the Server, an optimization method to reduce the multiplication depth is to let the Client send the ciphertexts (\(\boldsymbol{y^{1}}\)) encrypted, (\(\boldsymbol{y^{2}}\)) encrypted, (\(\boldsymbol{y^{3}}\)) encrypted, \(\ldots\), (\(\boldsymbol{y^{1x1}}\)) encrypted to a Server. Next, the Server can expand \(F_{x}\) (\(y;r\)) into \(F_{x}\) (\(y;r\)) = \(\boldsymbol{\Delta}\boldsymbol{a}_{i}\,\boldsymbol{y^{i}}\), where \(0\leq i\leq\left|\,\mathsf{X}\,\right|\) and \(\boldsymbol{a}_{i}\) is the coefficient of the corresponding term of \(y\) raised to the power of \(i\). From the Server's perspective, \(\boldsymbol{a}_{i}\) is a plaintext, and \(\boldsymbol{y^{i}}\) is a ciphertext sent by the Client, so the Server only needs to multiply the plaintext and the ciphertext for each item and adds these items up to obtain the answer. The communication cost after this optimization is \(O\left(\left|\,\mathsf{Y}\,\right|\,\mathsf{X}\,\right|\)), and the multiplication depth of HE reduces to \(O\left(1\right)\). Although the multiplication depth of the Server becomes \(O\left(1\right)\), the Client must send the ciphertext's power of one to power of \(\left|\,\mathsf{X}\,\right|\) to the Server for each \(y\), which will increase the communication cost of the Client by \(\left|\,\mathsf{X}\,\right|\) times. In our case, \(\left|\,\mathsf{Y}\,\right|\) is much smaller than \(\left|\,\mathsf{X}\,\right|\), so this approach causes too much burden for the Client.  
Instead of having the Client send the ciphertext \(y\) (from the power of one to the power of \(\left|\,\mathsf{X}\,\right|\)) to the Server, the above-mentioned communication cost can be mitigated by having the Client only send the \(y^{\,i\,\mathsf{-2}}\,\mathsf{\forall}\,\ell\) to the Server, where \(\ell\) is the window size, for all \(1\leq i\leq 2^{\ell}-1\) and \(0\leq j\leq\left|\,\mathsf{log2}\,\left(\left|\,\mathsf{X}\,\right|/\ell \right)\right|\). After the Server receives these terms, we can calculate the ciphertexts corresponding to \(y\)'s power one to power \(\left|\,\mathsf{X}\,\right|\) efficiently and correctly. For example, if \(\ell\) is \(1\), the Client needs to send the encrypted \(y\), \(y^{2}\), \(y^{4}\), \(y^{8}\), \(\ldots\), \(y^{2^{\left\lfloor\mathsf{log2}\left(\left|\,\mathsf{X}\,\right|\right)\right\rfloor}}\) to the Server. This pre-computing process can significantly reduce the multiplication depth of HE operations on the Server, and the extra communication cost paid by the Client will not be too high. The complexity of the labeled PSI protocol after applying the windowing optimization is shown in Table 5.