## 4 Analysis
### Security Analysis
Next, we show that our construction is secure against a key-recovery attack. Assume that a PPT adversary \(\mathcal{A}\) has access to the encryption oracle \(\mathcal{O}\) and wants to perform a key-recovery attack, i.e., to recover the key pool given the polynomial number of accesses to the oracle \(\mathcal{O}\). In Theorem 3, we show that the probability that the adversary succeeds in performing such an attack is negligible. For any PPT adversary \(\mathcal{A}\) with access to encryption oracle \(\mathcal{O}\), the probability of performing a successful key-recovery attack is  
\[Pr_{\mathit{KRA}}=\binom{\mathcal{Q}}{s}p^{s}(1-p)^{\mathcal{Q}-s}, \tag{4}\]  
which is negligible in terms of security parameter \(\lambda\), \(p=\frac{\mathbb{T}(s-1)!}{(s+T-1)! }\), where \(s\) denotes the number of secret keys, and \(T\) represents the number of keys used to generate the pad \(r\) for encryption. \(\mathcal{Q}=\mathit{poly}(\lambda)\) where \(\lambda\) is the security parameter. Proof. : By accessing the encryption \(\mathcal{O}\) for each query, \(\mathcal{A}\) can choose a message \(m\) from the given message space that it chooses, and the oracle will return its encryption \(\mathcal{C}=m+\mathbf{r}\), where \(\mathbf{r}\) is generated through the pad-generation algorithm. Thus, the adversary can easily recover the pad \(\mathbf{r}\) by \(\mathbf{r}=\mathcal{C}-m\). Recall that each pad is a combination of the secret key:  
\[Pr[\mathbf{r}_{i}>2^{\eta}-2^{\kappa}\cup\mathbf{r}_{i}<2^{\kappa}]=\frac{2\cdot 2^{ \kappa}}{2^{\eta}}=\frac{1}{2^{\eta-\kappa+1}}.\]0  
To successfully recover the key pool of size \(s\), the adversary is asked to give a unique solution of a linear system \(\mathbf{Ax}=\mathbf{b}\). The variable \(\mathbf{x}\) is an \(s\)-dimensional vector where each entry represents a secret key value in the key pool. The coefficient matrix \(A\) is a sparse matrix of dimension \(\mathcal{Q}\times s\), where \(\mathcal{Q}=\mathrm{poly}(\lambda)\) is the number of queries made by the adversary. The non-zero elements indicate the secret key value used for generating the pad \(\mathbf{r}\). The sparsity of the matrix ranges from \(\left[\frac{s}{\mathcal{Q}},\frac{sT}{\mathcal{Q}}\right]\). To launch the attack, adversary \(\mathcal{A}\) needs at least \(s\) equations to give a solution to the system. Consider the case that \(\mathcal{A}\) only retrieves \(k\) equations where \(k<s\); it is clear that the linear system would be an underdetermined system, which implies infinite solutions. Thus, to recover the key pool, the adversary shall have at least \(s\) equations. However, notice that, for each query, the attacker is only able to recover the pad \(r\) while the randomnesses \(\gamma_{1},\cdots,\gamma_{T}\) are kept secret on the user's end. Thus, to recover the secret key, \(\mathcal{A}\) has to first guess the randomnesses, i.e., to guess the coefficient matrix \(A\) for at least \(s\) times. For each query, the adversary needs to identify which key value is used in generating the pad. This problem can be described as a sampling problem with replacement. The possible combination of secret key values is given by \(\binom{s+T-1}{T}=\frac{(s+T-1)!}{T!(s-1)!}\). That is, the probability of a successful guess in one equation is \(p=\frac{T!(s-1)!}{(s+T-1)!}\). Here, we do not consider the trivial case \(T=1\) in which for each query adversary can reveal a secret key value since the pad is exactly equal to the secret key chosen. When \(T\geq 2\), to retrieve the secret key value, the adversary needs to recover at least \(s\) equations on \(\mathcal{Q}\) attempts. Thus, the overall probability of recovering \(s\) equations out of \(\mathcal{Q}\) attempts is given by \(Pr_{KRA}=\binom{\mathcal{Q}}{s}p^{s}(1-p)^{\mathcal{Q}-s}\). We require the probability to be negligible in terms of the security parameter \(\lambda\). That is, \(Pr_{KRA}=\binom{\mathcal{Q}}{s}p^{s}(1-p)^{\mathcal{Q}-s}=negl(\lambda)\).