## 4 Analysis
### Security Analysis
Assume a PPT adversary \(\mathcal{A}\) has access to an encryption oracle \(\mathcal{O}\). When \(\mathcal{A}\) queries the oracle, it chooses a message \(m\) on its own and sends it to the oracle. The oracle will execute the protocol and output an encryption of message \(\mathcal{C}=m+\mathbf{r}\), where \(\mathbf{r}\) is sampled through our key-generation algorithm. Recall that, during pad generation, the client generates \(T\) random numbers to identify elements in key pool \(\mathcal{R}\). Thus, the total possible combination of the pad is given by \(s^{T}\). For security reasons, we assure the probability that the same pad is re-used is negligible regarding the security parameter \(\lambda\). That is, \((\frac{1}{s})^{T}=negl(\lambda)\), which can be achieved by choosing appropriate parameters. Specifically, we can formulate the security in Theorem 2. Theorem 2: _For every PPT adversary \(\mathcal{A}\), there exists a negligible function \(negl(\cdot)\) such that the probability of the CPA-indistinguishability experiment Exp to output \(1\) is only negligibly more than \(\frac{1}{2}\):_  
\[Pr[Exp_{\mathcal{A},PPSP}^{SS-CPA}(\lambda)=1]\leq\frac{1}{2}+negl(\lambda)\]  
Proof. : We first describe the CPA-indistinguishability experiment \(Exp_{\mathcal{A},PPSP}^{SS-CPA}(\lambda)\). The adversary is given input \(1^{\lambda}\) and access to the encryption oracle \(\mathcal{O}\). \(\mathcal{A}\) samples a pair of message \(m_{0},m_{1}\) from the message space and sends them to the challenger. Then, a random bit \(b\xleftarrow{\xi}\{0,1\}\) is selected by the challenger, who encrypts the message \(\mathcal{C}=m_{b}+\mathbf{r}\), where \(\mathbf{r}\) is generated through Algorithm 3. The challenger sends the ciphertext \(\mathcal{C}\) to the adversary. Here, we assume that the output of Algorithm 3 follows distribution \(\mathcal{D}\). In Theorem 1, we show that \(\mathcal{D}\) cannot be distinguished from a uniform distribution on \(\mathbb{Z}_{q}\) with non-negligible probability. The adversary can keep querying the oracle for polynomial times and then output a bit \(b^{\prime}\). The output of experiment \(Exp_{\mathcal{A},PPSP}^{SS-CPA}(\lambda)\) is defined as \(1\) if \(b^{\prime}=b\) and \(0\) otherwise. Then, we define a sequence of hybrid \(H_{i}\)  
\[H_{0} =\{\mathbf{r}\leftarrow\mathcal{D}:m_{0}+\mathbf{r}\}\] \[H_{1} =\{R\leftarrow\mathcal{U}_{l}:m_{0}+R\}\] \[H_{2} =\{R\leftarrow\mathcal{U}_{l}:m_{1}+R\}\] \[H_{3} =\{\mathbf{r}\leftarrow\mathcal{D}:m_{1}+\mathbf{r}\}\]  
By construction, if \(\mathcal{A}\) can win the CPA game with a non-negligible probability \(p\), i.e., the probability of \(\mathit{Exp}_{A,\mathit{PPSP}}^{\mathit{S}-CPA}(\lambda)\) to output 1 is larger than the experiment to output 0 with non-negligible probability, then \(\mathcal{A}\) can distinguish \(H_{0}\) and \(H_{3}\) with same probability \(p\). Therefore, from the hybrid lemma, which shows the transitivity of hybrids, we immediately know that \(\mathcal{A}\) can also distinguish between two consecutive hybrids with non-negligible probability \(1/4p\). We will proceed to show that this gives rise to a contradiction. Define a pair of nonuniform PPT machines \(M^{0},M^{1}\) by \(M^{i}(X_{l})=\{r\gets X_{l}:m_{i}+r\}\). It is clear that \(M^{i}\) is an efficient operator. Observe that \(H_{0}=M^{0}(\mathcal{D})\) and \(H_{1}=M^{0}(\mathcal{U}_{l})\). Guaranteed by our construction, with only negligible probability, the pad \(\mathbf{r}\) generated by our algorithm can be distinguished from a truly random number sampled from a uniform distribution \(\mathcal{U}_{l}\). Thus, from the efficient operation lemma, \(H_{0}\approx H_{1}\). Similarly, it is easy to show that \(H_{2}\approx H_{3}\). Then, to preserve the transitivity of hybrids, \(\mathcal{A}\) must be able to distinguish \(H_{1}\) and \(H_{2}\). Nonetheless, by the perfect secrecy of one time pad, we know that \(H_{1}\) and \(H_{2}\) are indistinguishable, which immediately introduces the contradiction.