# An Efficient BGV-type Encryption Scheme for IoT Systems
## 4 Scheme Description  
In this section, we describe a variant BGV-type scheme under our modifications. Because the scheme is to optimize the ciphertext evaluation processes. The description of encoding a message to a vector as plaintext is ignored. Moreover, the basic secret key generation, public key encryption, encryption, and decryption algorithms are the same as known schemes [5; 19]. The details are as follows:  
Setup: given a security parameter \(\lambda\), the setup algorithm selects a prime number \(p(\lambda)\) and a number \(m(\lambda)\) and computes corresponding parameters \(d\) and \(l\) to define the plaintext space. Afterwards, it selects a series of prime number \(p_{0}(\lambda)\), \(\cdots\), \(p_{L-1}(\lambda)\), where \(p_{0}=p\), \(p_{1}(\lambda)=\cdots=p_{L-1}(\lambda)=1\bmod p(\lambda)\), and computes \(q_{i}=\prod_{j=0}^{i}p_{j}\), for \(i=0\), \(\cdots,L-1\). All of the ciphertexts and keys are defined in \(R_{q_{L-1}}\). The public parameters include all above parameters. SecretKeyGen: given the public parameters, the secret key generation algorithm selects an \(l\)-dimension vector \(s\). Each element in \(s\) is chosen from a noise distribution \(\chi\). Output SK = \(s\). PublicKeyGen: given the public parameters and an \(l\)-dimension vector \(s\), the public key generation algorithm selects an \(l\)-dimension vector \(a\) from \(R_{q_{L-1}}\), an \(l\)-dimension error vector \(\epsilon\) from distribution \(\chi\), and computes an \(l\)-dimension vector \(b=a\cdot s+p\cdot\epsilon\bmod q_{L-1}\). Output PK = \((a,b)\). SwitchKeyGen: given the public parameters and an \(l\)-dimension vector \(s\), the switch key generation algorithm selects an \(l\)-dimension vector \(a\) uniformly from \(R_{q_{L-1}}\), an \(l\)-dimension error vector \(\epsilon\) from distribution \(\chi\), and computes an \(l\)-dimension vector \(b=a\cdot s+p\cdot\epsilon-s^{2}\cdot(p\cdot r+1)\bmod q_{L-1}\), where \(r\) is a random number. Output EPK = \((a,b)\). Encrypt: given the public parameters, a public key PK = \((a,b)\) and a message \(m{\in}R_{p}^{l}\), the encryption algorithm selects an \(l\)-dimension vector \(v\). Each of its element is chosen from \(\{-1,0,1\}\) with probability of \((\frac{1}{4},\frac{1}{2},\frac{1}{4})\). Then it selects two \(l\)-dimension error vectors \(e_{0}\) and \(e_{1}\), which their elements are sampled from the discrete Gaussian distribution with variance \(\sigma\). The ciphertext ct consists of two elements \(c_{0}\), \(c_{1}{\in}R_{q_{L-1}}\) and the depth is \(L-1\). \(c_{0}=b\cdot v+p\cdot e_{0}+m\bmod q_{L-1}\) and \(c_{1}=a\cdot v\)\(+p\cdot e_{1}\bmod q_{L-1}\). ct = \((c_{0},c_{1},L-1)\) is outputted. Decrypt: given the public parameters, a secret key SK = \(s\) and a ciphertext ct = \((c_{0},c_{1},i)\), the decryption algorithm computes \(m\leftarrow((c_{0}-s\cdot c_{1})\bmod q_{i})\bmod p\). SwitchModulu: given a ciphertext ct = \((c_{0},c_{1},i)\bmod q_{i}\), two modulus \((i,q_{i})\) and \((j,q_{j})\) where \(i>j\), the modulo switch algorithm computes the modulo inverse element \(rp_{j}=\frac{q_{j}}{q_{i}}\) in \(q_{j}\), and output the new ciphertext ct\({}^{\prime}\)=\((c_{0}^{\prime},c_{1}^{\prime},j)\), where \(c_{1}^{\prime}=c_{1}\cdot rp_{j}\bmod q_{j}\) and \(c_{2}^{\prime}=c_{2}\cdot rp_{j}\bmod q_{j}\). Usually, \(i=j+1\) is enough if \(L\) is just fit for security requirements. The modulo inverse element \(rp_{j}\) can be computed by the extended Euclid algorithm (see ex_gcd in Appendix A.2). CTLinearization: given two ciphertexts \(\mathrm{ct_{1}}\) = \((c_{0}^{(1)},c_{1}^{(1)},i)\) and \(\mathrm{ct_{2}}\) = \((c_{0}^{(2)},c_{1}^{(2)},i)\), the ciphertext relinearization algorithm outputs the three-dimension ciphertext \(d\) = \((d_{0},d_{1},d_{2},i+1)\) = \((\mathrm{ct_{1}}{\otimes}\mathrm{ct_{2}},i+1)\) = \(\{(c_{0}^{(1)},c_{0}^{(2)}),\)\((c_{0}^{(1)}{\cdot}c_{1}^{(2)}+c_{0}^{(2)}{\cdot}c_{1}^{(1)}),\)\((c_{1}^{(1)}c_{1}^{(2)}),i+1\}\).