## 3 Building Block  
### Basic RLWE-Based Encryption  
In Section 2.2, we proved that there is a transformation that means that the secret key \(s\) is selected from \(R_{2}\) rather than \(R_{q}\) with an overwhelming probability, which does not affect the security of the scheme. This will be our optimization approach to make the scheme have less initial noise. Because the evaluation key generated by the key switching contains the private key, it will be also reduced. Although the FV12 [13] scheme proposes that the private key can be selected from \(R_{2}\), the Hamming weight of the secret key is limited without further proof. The following describes our basic encryption scheme, which is a somewhat homomorphic encryption scheme. Here, \(q\) is a prime numberand \(\chi\) is the error distribution on \(R_{q}\). The basic encryption scheme is defined as follows:  
* RE.SecretKeyGen\(\left(1^{\lambda}\right):\) Sample \(s\gets R_{2}\). Output \(sk=s\).
* RE.PublicKeyGen\((sk):\) Input \(sk=s\). Sample \(a\in R_{q}\), \(e\leftarrow\chi\), and then compute \(b=-as+e\ mod\ q\). Output \(pk=(b,a)\in R_{q}\times R_{q}\).
* RE.Encrypt\((pk,m):\) To encrypt a message \(m\in R_{2}\). Set \(b=pk[0]\), \(a=pk[1]\), sample \(e_{1}\), \(e_{2}\leftarrow\chi\), \(u\gets R_{2}\). Compute \(c_{0}=bu+\left\lfloor\frac{q}{2}\right\rfloor\cdot m+e_{1}\ mod\ q\), \(c_{1}=au+e_{2}\ mod\ q\). Output \(\mathbf{c}=(c_{0},c_{1})\in R_{q}\times R_{q}\).
* RE.Decrypt\((sk,c):\) Input \(sk=s\). Compute \(m=\left\lfloor 2/q[\left\langle c,(1,s)\right\rangle]_{q}\right\rfloor\ mod\ 2\).  
**Security**. The semantic security of the cryptosystem follows from the RLWE assumption by noting that \((bu+e_{1},\,au+e_{2})\) is pseudorandom, meaning the ciphertext is indistinguishable from one that carries no information on the message.  
To prove that the decryption is correct for properly encrypted ciphertexts, we prove the following lemma.  
**Lemma 3**.: _Using the notation of the above encryption scheme \(RE\) and assuming that \(\|\chi\|<B\), it holds that:_  
\[\left[\left\langle\mathbf{c},(1,s)\right\rangle\right]_{q}=\left\lfloor\frac{q}{2 }\right\rfloor\cdot m+\widetilde{\mathbf{c}} \tag{1}\]  
_with \(\|\widetilde{\mathbf{c}}\|\leq B\cdot(2\cdot\delta_{R}+1)\). This means that for \(B\cdot(2\cdot\delta_{R}+1)<\lfloor q/2\rfloor/2\), the decryption work is correct._  
Proof.: By the definition of module \(q\):  
\[\left\langle\mathbf{c},(1,s)\right\rangle =c_{0}+c_{1}\cdot s=b\cdot u+e_{1}+\left\lfloor\frac{q}{2} \right\rfloor\cdot m+a\cdot u\cdot s+e_{2}\cdot s\text{ mod }q\] \[=\left\lfloor\frac{q}{2}\right\rfloor\cdot m+e\cdot u+e_{1}+e_{2} \cdot s\text{ mod }q.\]  
Since the error term \(\left\lfloor\frac{q}{2}\right\rfloor\cdot m+e\cdot u+e_{1}+e_{2}\cdot s\) is small enough, we get \(\widetilde{\mathbf{c}}=e\cdot u+e_{1}+e_{2}\cdot s\). Since \(e,e_{1},e_{2}\leftarrow\chi\) and \(u,s\gets R_{2}\), we get \(\|u\|=\|s\|=1\) and get the bound term above \(\|\widetilde{\mathbf{c}}\|\leq B\cdot(2\cdot\delta_{R}+1)\).  
According to the definition of module \(q,c_{0}+c_{1}\cdot s=\left\lfloor\frac{q}{2}\right\rfloor\cdot m+\widetilde{ \mathbf{c}}+q\cdot v\). Then, \(\frac{2}{q}\cdot(c_{0}+c_{1}\cdot s)=m+(2/q)\cdot(\widetilde{\mathbf{c}}-\mathbf{ \epsilon}\cdot m)+2\cdot v\), where \(\mathbf{\epsilon}=\frac{q}{2}-\left\lfloor\frac{q}{2}\right\rfloor<1\). To round correctly, we need \((2/q)\cdot\|\widetilde{\mathbf{c}}-\mathbf{\epsilon}\cdot m\|<1/2\). \(\square\)