## 2 Preliminaries
### A Generic Transformation  
The binary LWE assumption given by [PERSON] et al. [30] is that the original dimension \(n\) is increased to \(n\log q\) to maintain the same security level when the key is selected from \(U(\mathbb{Z}_{2})\). In this section, we prove that the key \(s\) can be selected from \(R_{2}\), and it is safe without changing the dimensions of the key. In the following, we prove that through a transformation \(T\), the sample of distribution \(\mathrm{A}_{s,\chi}^{*}\) can be mapped to the distribution \(\mathrm{A}_{t,\chi}^{*}\). Therefore, \(s\) can be limited to be sampled from the error distribution \(\chi\) rather than uniformly sampled in \(\mathrm{R}_{q}\), without any security problems. **Lemma 1**. : _For the modulus \(q\), there is an arbitrary \(s\in R_{q}\) and error distribution \(\chi\). There is an absolute advantage of the polynomial time transformation \(T\), which maps \(A_{s,\chi}^{*}\) to \(A_{s,\chi}^{*}\), where \(\kappa\leftarrow\chi\), and maps \(U\Big{(}R_{q}^{*}\times R_{q}\Big{)}\) to itself._  
Proof. : The transformation \(T\) is allowed to access the distribution \(D\) over the set \(\mathrm{R}_{q}^{*}\times\mathrm{R}_{q}\), where the distribution \(D\) is \(\mathrm{A}_{s,\chi}^{*}\) or there is a uniform distribution \(\mathrm{U}\Big{(}\mathrm{R}_{q}^{*}\times\mathrm{R}_{q}\Big{)}\). The following involves two steps to prove the above lemma. 1. Transform \(T\) obtains the sample \(\left(\overline{\mathfrak{a}},\overline{\mathfrak{b}}\right)\in\mathrm{R}_{ \mathfrak{q}}^{*}\times\mathrm{R}_{\mathfrak{q}}\) by sampling at random from the distribution \(D\). When \(D\) is \(\mathrm{A}_{\mathrm{s}\times\mathrm{x}}^{*}\), the sample \(\left(\overline{\mathfrak{a}},\overline{\mathfrak{b}}\right)\) satisfies \(\overline{\mathfrak{b}}=\overline{\mathfrak{a}}\cdot\mathfrak{s}+\kappa\), where \(\kappa\leftarrow\chi\). 2. The samples selected from distribution \(D\) are transformed into a different distribution. The additional samples \(\left(\mathfrak{a},\mathfrak{b}\right)\in\mathrm{R}_{\mathfrak{q}}^{*}\times \mathrm{R}_{\mathfrak{q}}\) are selected from \(D\). The samples \(\left(\overline{\mathfrak{a}},\overline{\mathfrak{b}}\right)\) are transformed to \(\left(\mathfrak{a}^{\prime},\mathfrak{b}^{\prime}\right)\in\mathrm{R}_{ \mathfrak{q}}^{*}\times\mathrm{R}_{\mathfrak{q}}\) by transform \(T\), where \(\mathfrak{a}^{\prime}=\left(-\overline{\mathfrak{a}}\right)^{-1}\cdot \mathfrak{a}\), \(\mathfrak{b}^{\prime}=\mathfrak{b}+\mathfrak{a}^{\prime}\cdot\overline{ \mathfrak{b}}\). Since \(\overline{\mathfrak{a}}\in\mathrm{R}_{\mathfrak{q}}^{*}\) and \(\mathfrak{a}\in\mathrm{U}\left(\mathrm{R}_{\mathfrak{q}}^{*}\right)\), \(\mathfrak{a}^{\prime}\in\mathrm{R}_{\mathfrak{q}}^{*}\) is uniform. If the distribution \(D\) is uniformly distributed \(\mathrm{U}\left(\mathrm{R}_{\mathfrak{q}}^{*}\times\mathrm{R}_{\mathfrak{q}}\right)\), because \(b\) and \(\overline{b}\) are uniform, the sample \(\left(\mathfrak{a}^{\prime},\mathfrak{b}^{\prime}\right)\) belongs to \(\mathrm{U}\left(\mathrm{R}_{\mathfrak{q}}^{*}\times\mathrm{R}_{\mathfrak{q}}\right)\). It holds that the transformation maps the distribution \(\mathrm{U}\left(\mathrm{R}_{\mathfrak{q}}^{*}\times\mathrm{R}_{\mathfrak{q}}\right)\) to itself; if the distribution \(D\) is \(\mathrm{A}_{\mathrm{s}\times\mathrm{x}}^{*}\), then \(\mathfrak{b}=\mathfrak{a}\cdot\mathfrak{s}+\mathfrak{e}\in\mathrm{R}_{ \mathfrak{q}}\), \(\mathfrak{e}\leftarrow\chi\), so it holds that: \[\mathfrak{b}^{\prime} =\mathfrak{b}+\mathfrak{a}^{\prime}\cdot\overline{\mathfrak{b}}\] \[=\mathfrak{a}\cdot\mathfrak{s}+\mathfrak{e}+\mathfrak{a}^{\prime }\cdot\left(\overline{\mathfrak{a}}\cdot\mathfrak{s}+\kappa\right)\] \[=\mathfrak{a}^{\prime}\cdot\kappa+\mathfrak{e}.\] Therefore, \(\left(\mathfrak{a}^{\prime},\mathfrak{b}^{\prime}\right)\) is selected from distribution \(\mathrm{A}_{\mathrm{s}\times\mathrm{x}}^{*}\).