# Efficient Lattice-Based Cryptosystems with Key Dependent Message Security
## 3 Compact Public-Key Cryptosystem with KDM Security
### Basic RLWE\({}^{*}\)-Based Encryption Scheme
In addition, observe \(c_{2}=b\cdot r+t\cdot e_{2}+k\cdot s+t\cdot w\), compute  
\[c_{2}=(a\cdot s+t\cdot e)\cdot r+t\cdot e_{2}+k\cdot s+t\cdot w=(a\cdot r+k) \cdot s+t\cdot(w+e_{2}+er) \tag{8}\]define \(a^{\prime}=a\cdot r+k\), then \(c_{2}=a^{\prime}\cdot s+t\cdot(w+e_{2}+er)\). By Lemma 1 and Lemma 2, we have  
\[\|e_{2}+er\|\leq\|e_{2}\|+\sqrt{n}\cdot\|e\|\cdot\|r\|\leq\sigma\sqrt{n}+\sqrt{ n}\cdot\big{(}\sigma\sqrt{n}\big{)}^{2}=n^{0.5}\cdot\sigma+n^{1.5}\cdot\sigma^{2} \tag{9}\]  
Let \(\Delta=n^{0.5}\cdot\sigma+n^{1.5}\cdot\sigma^{2}\), \(\sigma^{\prime}\geq 2^{\omega(\log n)}\cdot\sigma^{2}\), compute \(\frac{\Delta}{\sigma^{\prime}}\leq\frac{n^{0.5}\cdot\sigma+n^{1.5}\cdot\sigma^ {2}}{2^{\omega(\log n)}\cdot\sigma^{2}}=2^{-\omega(\log n)}\). By Lemma 3, \(D_{Z^{2},\sigma^{\prime}}\) is statistically indistinguishable from \(D_{Z^{2},\sigma^{\prime},\Delta}\), it holds that \(c_{2}\approx a^{\prime}\cdot s+t\cdot w\), and therefore, the challenge ciphertext \(c_{2}^{*}=a^{\prime}\cdot s+t\cdot w\) is indistinguishable from \(c_{2}\). To sum up, the distinguishing advantage between the \(\mathbf{H}_{1}\) and \(\mathbf{H}_{0}\) is negligible, namely  
\[|adv(\mathcal{A},\mathbf{H}_{0})-adv(\mathcal{A},\mathbf{H}_{1})|\leq\text{negl}(n). \tag{10}\]  
**Game \(\mathbf{H}_{2}\)**: Hybrid game \(\mathbf{H}_{2}\) generates the challenge ciphertext from \(U\big{(}R_{q}\times R_{q}\big{)}\) when \(\mu=0\). Everything else is exactly the same. \[c=\left\{ \begin{array}{rl}\big{(}c_{1}^{*}=u_{1},\ c_{2}^{*}=u_{2}\big{)},\ \mu=0\\ (c_{1}=a\cdot r+t\cdot e_{1},\ c_{2}=b\cdot r+t\cdot e_{2}),\ \mu=1\end{array} \right. \tag{11}\]  
where \(u_{i}\ (i=1,2)\) chooses from \(U\big{(}R_{q}\big{)}\). Observe the hybrid game \(\mathbf{H}_{1}\), \(a^{\prime}=a\cdot r+k\) is indistinguishable from uniform, \(\big{(}c_{1}^{*}=a^{\prime},\ c_{2}^{*}=a^{\prime}\cdot s+t\cdot w\big{)}\in R _{q}\times R_{q}\) just happens to be an instance of the RLWE problem. Therefore, \(\big{(}c_{1}^{*},\ c_{2}^{*}\big{)}\) is pseudorandom, and then  
\[|adv(\mathcal{A},\mathbf{H}_{1})-adv(\mathcal{A},\mathbf{H}_{2})|\leq\text{negl}(n). \tag{12}\]  
Since the challenge ciphertext \((u_{1},\ u_{2})\in U\big{(}R_{q}\times R_{q}\big{)}\), thus we have  
\[adv(\mathcal{A},\mathbf{H}_{2})=\text{negl}(n). \tag{13}\]  
Finally, we conclude that  
\[ \begin{array}{rl}adv(\mathcal{A},\mathbf{H}_{0})=(adv(\mathcal{A},\mathbf{H}_{0})- adv(\mathcal{A},\mathbf{H}_{1}))+adv(\mathcal{A},\mathbf{H}_{1})\\ \qquad\qquad\qquad\qquad\qquad\qquad\leq|adv(\mathcal{A},\mathbf{H}_{0})-adv( \mathcal{A},\mathbf{H}_{1})|+adv(\mathcal{A},\mathbf{H}_{1})\\ \qquad\qquad\qquad\qquad\qquad\qquad\leq|adv(\mathcal{A},\mathbf{H}_{0})-adv( \mathcal{A},\mathbf{H}_{1})|+|adv(\mathcal{A},\mathbf{H}_{1})-adv(\mathcal{A},\mathbf{H} _{2})|\\ \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+adv( \mathcal{A},\mathbf{H}_{2})=\text{negl}(n).\end{array}  \tag{14}\]  
This proves the KDM-CPA security of the RPKE1 scheme. \(\square\)