# Efficient Lattice-Based Cryptosystems with Key Dependent Message Security
## 5 Performance  
In this section, we give a detailed performance comparison between our RPKE1 scheme, RSKE2 scheme and the ACPS scheme [8]. For the same security parameter \(\lambda\), through the analysis of the ACPS scheme, it is easy to see the difference between the lattice problems on which these schemes are based. Firstly, our scheme has replaced LWE through RLWE, which improves its application efficiency. Secondly, about the noise distribution, in order to obtain the appropriate key-dependent ciphertexts, the ACPS scheme introduces the noise flooding technique (namely, \(e\leftarrow\Psi_{\sigma^{\prime}}\)), which leads to the growth of the modulo \(q\) and the decline of efficiency. Due to the problem of quantum reduction of the LWE problem, the standard deviation of the additional noise distribution is \(\sigma^{\prime}\approx n^{-1}\cdot\sigma^{-4}\), where \(\sigma=\omega\big{(}\sqrt{\log n}\big{)}\), and \(m=O(n\log n)\leq n\log n\approx n\cdot\sigma^{2}\), \(p=\widetilde{O}\big{(}\sqrt{mn}\big{)}\approx n\cdot\sigma^{3}\), \(q=p^{2}\approx n^{2}\cdot\sigma^{6}=\text{ploy}(n)\cdot\sigma^{6}\). As shown in Table 1, we have the same standard deviation \(\sigma=\omega\big{(}\sqrt{\log n}\big{)}\), but no extra noise distribution \(\Psi_{\sigma^{\prime}}\) in the ciphertext generation. The \(w\gets D_{Z^{n},\sigma^{\prime}}\) in the hybrid game is irrelevant, because this does not affect the efficiency of the scheme at all. In addition, we also greatly reduce the message space \(R_{t}\) and the modulo size \(q=t\cdot\text{ploy}(n)\cdot\sigma^{2}\), where \(t=\sigma\sqrt{n}\). Note the last line, adding the symmetry scheme; ACPS also gave a symmetric-key cryptosystem similar to it. Although different in types, as a variant of RPKE1 it also highlights its advantages.  
Finally, we estimate the concrete parameters for our scheme. Compared with ACPS, we have greatly improved its efficiency; the cost of encryption and decryption is only  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Schemes** & \(\sigma\) & \(\sigma^{{}^{\prime}}\) & **Message Space** & **Modulo \(q\)** & **Challenge \(\mathcal{F}\)** \\ \hline ACPS & \(\omega(\sqrt{\log n})\) & \(n^{-1}\cdot\sigma^{-4}\) & \(\mathbb{Z}_{p}\), \(p=n\cdot\sigma^{3}\) & \(\text{ploy}(n)\cdot\sigma^{6}\) & affine functions \\ RPKE1 & \(\omega(\sqrt{\log n})\) & / & \(R_{t},t=\sqrt{n}\cdot\sigma\) & \(\text{ploy}(n)\cdot\sigma^{3}\) & linear functions \\ RSKE2 & \(\omega(\sqrt{\log n})\) & / & \(R_{2},t=2\) & \(\sqrt{n}\cdot\sigma\) & linear functions \\ \hline \hline \end{tabular}
\end{table}
Table 1: Parameter setting of ACPS and our schemes.  
\(\mathrm{polylog}(n)\) bit operations per message symbol. By these parameters including modulus \(q\), degree \(n\) and error distribution \(\chi=D_{Z^{n}\sigma}\), we can obtain concrete secret key size, public key and ciphertext size. For example, the public key size of the ACPS scheme is \(m\cdot n\cdot\log q\approx n^{2}\cdot\log^{2}n=\widetilde{O}(n^{2})\), the ciphertext size is \(n\cdot\log q=\widetilde{O}(n)\) and the secret key for ACPS and RPKE1 are \(\sigma\cdot\sqrt{n}\) (both \(s\leftarrow\chi\)). Performance comparison of ACPS and our scheme are listed in Table 2. All sizes are in bits.  
There are many encryption schemes for KDM security, not only ACPS, but also many schemes based on traditional mathematical problems. However, in terms of computational efficiency, the lattice-based cryptosystems are still safer and more efficient. Additionally, the ciphertext operations mainly consist of encryption and decryption, but other schemes do not have compact ciphertexts. Hence, from the usability perspective, our schemes are superior to previous schemes.