# Efficient Lattice-Based Cryptosystems with Key Dependent Message Security
## 4 Efficient Symmetric-Key Encryption Scheme
### Symmetric-Key Scheme with KDM Security  
As in the previous section, given the security parameter \(\lambda\), let \(q=q(\lambda)\,\geq 2\), and an error distribution \(\chi=\chi(\lambda)\). 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. We demonstrate a symmetric-key scheme based on the \(k\)-RLWE\({}^{*}\) problem. In order to reduce the norm of ciphertext noise, [25] uses a binary secret \(s\in R_{2}\), which shows that the scheme is secure under this optimization, as long as the Hamming weight \(h\) is small enough and \(\left(\begin{array}{c}n\\ h\end{array}\right)\) is large enough. In the final results, they construct a somewhat homomorphic encryption scheme by setting \(t=2\), \(h=63\) and \(f(x)=x^{n}+1\), where \(m\in R_{t}\). Therefore, as a symmetric-key scheme, the security is not affected when the results for the RLWE setting continue to the \(k\)-RLWE\({}^{*}\) setting.  
\(\bullet\)**: **RSKE2.KeyGen\(\left(1^{\lambda}\right)\)**: Sample \(s\gets R_{2}\). Output \(sk=s\) as the secret key.  
* **RSKE2.Enc\((sk,m)\)**: To encrypt a message \(m\in R_{2}\), sample uniformly, \(e\leftarrow\chi\) and set \(b=(a+1)\cdot s+2e\). Output the ciphertext \(c=(c_{1}=a+1,c_{2}=b+m)\in R_{q}\times R_{q}\).
* **RSKE2.Dec\((sk,c)\)**: Compute \(c_{2}-c_{1}\cdot s\), then output \(m=(c_{2}-c_{1}\cdot s)\) mod \(q\) mod 2.  
According to the encryption algorithm, \(c_{2}-c_{1}\cdot s=m+2e\), compared with the previous public-key encryption scheme, the ciphertext noise is small, that is \(\|2e_{\infty}\|<q/2\), namely \(q>4\sigma\sqrt{n}\), then the ciphertext can be decrypted correctly.  
The KDM-CPA security is similar to that of Section 3.3, except that there is no public key. Although the message space is reduced to \(R_{2}\), there still exists a linear function \(f(sk)=k\cdot s+2w\ \in R_{2}\) to realize KDM security.  
**Theorem 3**: _Sample \(k\gets R_{q}\) uniformly and \(w\gets D_{Z^{n},\sigma}\), where \(\sigma\geq\omega\big{(}\sqrt{\log n}\big{)}\). There exists a linear function \(f(sk)=k\cdot s+2w\ \in R_{2}\) that makes the RSKE2 scheme satisfy KDM-CPA security, assuming that \(k\)-RLWE\({}^{*}\) is hard._  
Proof.: The proof of Theorem 2 is similar to RPK1. Therefore, this section gives a brief narrative. First, by \(f(sk)\) replacing \(m\), we generate the challenge ciphertext \(c=(c_{1}=a+1,c_{2}=(a+1)\cdot s+2e+k\cdot s+2w)\), where \(k\stackrel{{\shuffle}}{{\leftarrow}}R_{q}\) and \(w\gets D_{Z^{n},\sigma}\). Observe that \(c_{2}=(a+1+k)\cdot s+2(e+w)\), defining \(a^{\prime}=a+1\) and \(e^{\prime}=w+e\), then we have the challenge ciphertext \(c=(a^{\prime},(a^{\prime}+k)\cdot s+2e^{\prime},)\), which is exactly an instance of the \(k\)-RLWE\({}^{*}\) problem. It means that the challenge ciphertext \(c\) is pseudorandom, namely the adversary \(\mathcal{A}\) cannot distinguish it from the ciphertext that is encrypted by the message 0. Therefore, the above RSK2 scheme is KDM-CPA under the \(k\)-RLWE\({}^{*}\) problem. \(\square\)