# Efficient Lattice-Based Cryptosystems with Key Dependent Message Security
## 3 Compact Public-Key Cryptosystem with KDM Security
### Basic RLWE\({}^{*}\)-Based Encryption Scheme  
For security parameter \(\lambda\), let \(q=1\) mod \(2n\) and \(t\in\mathbb{Z}_{q}^{*}\) relatively prime, in which \(\{1,\ldots,q-1\}\supseteq\mathbb{Z}_{q}^{*}\). Let \(\chi=D_{\mathbb{Z}^{n},\sigma}\) be an error distribution with \(\sigma\geq\omega\big{(}\sqrt{\log n}\big{)}\) and \(\sigma\ll t\); we sampled \(s\) from error distribution \(\chi\), so all \(s\in R_{t}\) with overwhelming probability when the secret chooses from error distribution. Let \(R=\mathbb{Z}[x]/(f(x))\), \(R_{q}=\mathbb{Z}_{q}[x]/(f(x))\) where \(f(x)=x^{n}+1\) and \(n=n(\lambda)\) is a power of 2. * **RPKE1.KeyGen**\((1^{\lambda})\): Sample \(s\leftarrow\chi\). Output \(sk=s\). Sample \(a\leftarrow R_{q}^{*}\) uniformly, \(e\leftarrow\chi\) and set \(b=a\cdot s+t\cdot e\), where \(t\in\mathbb{Z}_{q}^{*}\) and \(R_{q}^{*}\) denote the set of invertible elements of \(R_{q}\). Output the public key \(pk=(a,b)\in R_{q}^{*}\times R_{q}\). * **RPKE1.Enc**\((pk,m)\): Notice that \(m\in R_{t}\), due to the lemma by the noise scaling. Sample \(r,e_{1},e_{2}\leftarrow\chi\). Compute \(c_{1}=a\cdot r+t\cdot e_{1}\), \(c_{2}=b\cdot r+t\cdot e_{2}+m\), output the ciphertext \(c=(c_{1},c_{2})\in R_{q}\times R_{q}\). * **RPKE1.Dec**\((sk,c)\): Input the corresponding secret key and ciphertext, then output \(m=(c_{2}-c_{1}\cdot s)\) mod \(q\) mod \(t\). The correctness of the scheme is obvious, compute \((c_{2}-c_{1}\cdot s)=m+te_{2}-te_{1}s+ter\), according to the Lemma 3, we have \[ \begin{split}\|te_{2}-te_{1}s&+ter\|_{\infty}=t \cdot\|e_{2}\|_{\infty}+t\cdot\|e_{1}s\|_{\infty}+t\cdot\|e\prime\|_{\infty}\\ &=t\cdot\sigma\sqrt{n}+2t\cdot n\big{(}\sigma\sqrt{n}\big{)}^{2}< q/2\end{split} \] (5) if \(q>t\cdot\text{poly}(n)\cdot\sigma^{2}\), where \(t=\sigma\sqrt{n}\), the ciphertext can be decrypted correctly. The KDM-CPA security follows from the RLWE\({}^{*}\) assumption by noting the pseudorandom distribution \(A_{s,\chi}^{*}\). Observe that \(f(sk)=k\cdot s+t\cdot w\in R_{t}\), where \(k,s,w\) all choose from error distribution. The ciphertext is indistinguishable from uniform even if \(m\) is replaced with any linear function of the scheme's own secret key. Let \(k\gets D_{\mathbb{Z}^{n},\sigma}\)and \(w\gets D_{\mathbb{Z}^{n},\sigma^{\prime}}\), where \(\sigma^{\prime}\geq 2^{\omega(\log n)}\cdot\sigma^{2}\), \(\sigma=\omega\big{(}\sqrt{\log n}\big{)}\). Under the RLWE\({}^{*}\)assumption, the above cryptosystem RPKE1 about \(f(sk)=k\cdot s+t\cdot w\) satisfies KDM-CPA security. For any probabilistic polynomial-time adversary \(\mathcal{A}\), we use a three-step hybrid game to prove that the ciphertext with key-dependent message \(f(sk)\) in the RPKE1 scheme is computationally indistinguishable from one that carries no information on the message. Therefore, the distinguishing advantage of the adversary \(\mathcal{A}\) is negligible. **Game \(H_{0}\)**: Let \(pk=(a,b)\leftarrow\textbf{RPK1.KeyGen}\big{(}1^{\lambda}\big{)}\), the remaining parameters are as above, and Hybrid game \(H_{0}\) is mainly used to generate the challenge ciphertexts. \[c=\left\{ \begin{array}{cc}(c_{1}=a\cdot r+t\cdot e_{1},\ c_{2}=b\cdot r+t \cdot e_{2}+k\cdot s+t\cdot w),&\mu=0\\ (c_{1}=a\cdot r+t\cdot e_{1},\ c_{2}=b\cdot r+t\cdot e_{2}+0\ ),&\mu=1\end{array} \right. \tag{6}\]  
**Game \(H_{1}\)** : Similar to the hybrid game \(H_{0}\), hybrid game \(H_{1}\) generates the challenge ciphertexts related to \(f(sk)\) in different ways. \[c=\left\{ \begin{array}{cc}\big{(}c_{1}^{*}=a^{\prime},\ c_{2}^{*}=a^{\prime }\cdot s+t\cdot w\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{7}\]  
where \(a^{\prime}=a\cdot r+k\), \(k\leftarrow\chi\) and \(w\gets D_{\mathbb{Z}^{n},\sigma^{\prime}}\). Observe that \(c_{1}=a\cdot r+t\cdot e_{1}\), \(r\) and \(e_{1}\) choose from the error distribution \(\chi\), just like the ciphertext \(c_{1}^{*}=a\cdot r+k\) without scaling the noise, hence \(c_{1}^{*}\) is indistinguishable from \(c^{\prime}\).