# Efficient Lattice-Based Cryptosystems with Key Dependent Message Security
## 4 Efficient Symmetric-Key Encryption Scheme
### The Variant of RLWE\({}^{*}\) Problem  
**Definition 4**.: (\(k\)-RLWE\({}^{*}\))_As in the previous Definition 2, the \(k\)-RLWE\({}^{*}\) problem is to distinguish the following two distributions with non-negligible advantage: In the first distribution, one samples \((a,b)\) uniformly from \(R_{q}\times R_{q}\). In the second distribution, one samples \((a,b)\in R_{q}^{*}\times R_{q}\) by sampling \(a,k\gets R_{q}^{*}\) uniformly, where \(s\in R_{q}\), \(e\leftarrow\chi\) and setting \(b=(a+k)\cdot s+e\), let this distribution be \(bA_{s,\chi}^{*}\)._Observe that the \(k\)-RLWE\({}^{*}\) problem, when \(k=0\), is a complete RLWE\({}^{*}\) problem. If \(k\
eq 0\in R_{q}\),we give a probability polynomial-time reduction to prove that the \(k\)-RLWE\({}^{*}\) problem remains hard, even when \(A^{*}_{s,\chi}\) is respectively replaced by \(bA^{*}_{s,\chi}\).  
For any \(n\geq 1\), \(q\geq 2\), and error distribution \(\chi\), there is a probability polynomial-time reduction from RLWE\({}^{*}\)to the \(k\)-RLWE\({}^{*}\)that reduces the advantage by at most \(2^{-n}\).  
Proof.: Given a sample \((a_{0},b_{0})\in R^{*}_{q}\times R_{q}\) and a sample \((k,b_{1})\in R^{*}_{q}\times R_{q}\) from the given RLWE\({}^{*}\) oracle, the reduction outputs a new instance \((a^{\prime}=a_{0},b^{\prime}=b_{0}+b_{1})\in R^{*}_{q}\times R_{q}\).  
If samples \((a_{0},b_{0})\) and \((k,b_{1})\) are chosen from \(U\!\left(R^{*}_{q}\times R_{q}\right)\), then \(b_{0}\,\) and \(b_{1}\) are uniform in \(R_{q}\), and \(b_{1}\) is pseudorandom by RLWE problem, the reduction outputs a uniform sample \((a^{\prime}=a_{0},b^{\prime}=b+b_{1})\in R^{*}_{q}\times R_{q}\), up to statistical distance \(2^{-n}\).  
If sample \((a_{0},b_{0})\) is chosen from \(U\!\left(R^{*}_{q}\times R_{q}\right)\) and the distribution of \((k,b_{1})\) is \(A^{*}_{s,\chi}\), then \(b_{0}\,\) is uniform in \(R_{q}\), and \(b_{1}=k\cdot s+e_{1}\) is pseudorandom, the reduction outputs a uniform sample \((a^{\prime}=a_{0},b^{\prime}=b+b_{1})\in R^{*}_{q}\times R_{q}\), up to statistical distance \(2^{-n}\). In addition, a sample \((a_{0},b_{0})\) from \(A^{*}_{s,\chi}\) and a sample \((k,b_{1})\) from \(U\!\left(R^{*}_{q}\times R_{q}\right)\) are the same as above.  
On the other hand, if given samples \((a_{0},b_{0})\) and \((k,b_{1})\) from the distribution \(A^{*}_{s,\chi}\), the equation \(b^{\prime}=b_{0}+b_{1}=a_{0}\cdot s+e_{0}+k\cdot s+e_{1}=(a_{0}+k)\cdot s+(e_{ 0}+e_{1})\). Let \(e^{\prime}=e_{0}+e_{1}\), we notice that \((a^{\prime},b^{\prime})\in R^{*}_{q}\times R_{q}\) is exactly a \(k\)-RLWE\({}^{*}\) instance, the reduction outputs a sample \((a^{\prime}=a_{0},b^{\prime}=(a+k)\cdot s+e^{\prime})\in R^{*}_{q}\times R_{q}\) from \(bA^{*}_{s,\chi}\), up to statistical distance \(2^{-n}\).  
To sum up, if the RLWE\({}^{*}\) problem is infeasible, then the \(k\)-RLWE\({}^{*}\) problem is also infeasible--namely, \(bA^{*}_{s,\chi}\) is indistinguishable from uniform, as desired.  
After that, we also give the Hermite normal form of the \(k\)-RLWE\({}^{*}\) problem, this modification makes the secret short and useful in the following symmetric-key scheme.  
For modulus \(q\), arbitrary \(s\in R_{q}\) and the error distribution \(\chi\), there is a deterministic polynomial-time transformation \(T\), which maps \(bA^{*}_{s,\chi}\) to \(bA^{*}_{\phi,\chi}\) where \(\phi\leftarrow\chi\), and maps \(U\!\left(R^{*}_{q}\times R_{q}\right)\) to itself.  
The proof will be showed in Appendix A.  
[The \(k\)-RLWE\({}^{*}\) assumption-Hermite normal form] As in the previous definition 4, for any \(\ell=\mathrm{poly}(\lambda)\), the \(k\)-RLWE\({}^{*}\) assumptionholds that,  
\[\{(a_{i},(a_{i}+1)\cdot s+e_{i})\}_{i\in[\ell]}\approx\{(a_{i},u_{i})\}_{i \in[\ell]}, \tag{15}\]  
where sampling \(s\leftarrow\chi\), other parameters remain unchanged.