# An Efficient BGV-type Encryption Scheme for IoT Systems
## 3 Introduction of BGV  
In original BGV [17], public key and switch keys are matrices. ([18], Appendix D.2)  
indicates those keys can also be vectors over polynomial ring. Subsequently, the key size can be reduced. In this section, we describe BGV in vector form. As all the other encryption schemes, BGV includes four algorithms, Setup, Keygen, Encrypt, and Decrypt as the basic encryption-decryption part. Moreover, it includes Add and Multiply to perform homomorphic calculations. These algorithms are as follows. Setup: given a security parameter \(\lambda\) and level \(L\), the setup algorithm generates \(L\) large prime numbers \(q_{0}\), \(\cdots\), \(q_{L-1}\), where \(q_{0}<\cdots<q_{L-1}\) and selects the discrete Gaussian distribution \(\chi\) as the error distribution. It defines the plaintext space by selecting \(m\) and \(p\) and computing \(l\) and \(q_{0}\), \(\cdots\), \(q_{L-1}\), \(\chi\), \(p\), and \(l\) are public parameters. KeyGen: given the public parameters, first, the key generation algorithm selects a random vector \(s\) as the secret key. Then, it computes \(b=-(a\cdot s+p\cdot\epsilon)\) mod \(q_{L-1}\), where \(a\) is a random element in \(R_{q_{L-1}}\), \(\epsilon\) is sampled from \(\chi\), and \(p\) is the plaintext modulu, and let \((a,b)\) be the public key. Next, it computes\(b_{i}=-(a_{i}\cdot s+p\cdot e_{i}-t_{i}\cdot s^{2})\) mod \(t_{i}\cdot q_{i}\), where \(a_{i}\) a random element in \(R_{q_{i}}\), \(t_{i}\) is an integer, and \(e_{i}\) is sampled from \(\chi\), and finally let \((a_{0},b_{0},t_{0},0)\), \(\cdots\), \((a_{L-1},b_{L-1},t_{L-1},L-1)\) be the switch key. Encrypt: given a plaintext \(m\), the encryption algorithm randomly selects a vector \(v\), where each \(v_{i}\)\(\in\)\(\{0,\pm 1\}\) with probability \(\{\frac{1}{2},\frac{1}{4}\}\), samples \(e_{0}\) and \(e_{1}\) from \(\chi\), and computes \(c_{0}=b\cdot v+p\cdot e_{0}+m\) mod \(q_{L-1}\), \(c_{1}=a\cdot v+p\cdot e_{1}\) mod \(q_{L}\). \(ct=(c_{0},c_{1},\,L-1)\) is the initial ciphertext. Decrypt: given a ciphertext \(ct=(c_{0},c_{1},i)\) and the secret key \(s\), the decryption algorithm computes \(m\gets c_{0}+c_{1}\cdot s\) mod \(q_{i}\) mod \(p\). Mul: given two ciphertexts \(ct^{\prime}=(c^{\prime}_{0}\),\(c^{\prime}_{1}\),\(i\)) and \(ct^{\prime\prime}\)= \((c^{\prime\prime}_{0}\),\(c^{\prime\prime}_{1}\),\(i\)) under same secret key, the multiplication algorithm first computes \(d_{0}=c^{\prime}_{0}\),\(c^{\prime\prime}_{0}\), \(d_{1}=c^{\prime}_{0}\),\(c^{\prime\prime}_{1}+c^{\prime}_{1}\),\(c^{\prime\prime}_{0}\), and \(d_{2}=c^{\prime}_{1}\),\(c^{\prime\prime}_{1}\), Then it compresses \((d_{0},\,d_{1},\,d_{2})\) to \(ct^{*}=(c^{*}_{0},\,c^{*}_{1})\), where \(c^{*}_{0}=t_{i}d_{0}+b_{i}\cdot d_{2}\) mod \(t_{i}q_{i}\) and \(c^{*}_{1}=t_{i}d_{1}+a_{i}\cdot d_{2}\) mod \(t_{i}q_{i}\), with the switch key \((a_{i},b_{i},t_{i},i)\). Next, \(ct^{*}\)\(\in\)\(R_{t_{i}q_{i}}\) is first converted into \(ct^{*}\)\(\in\)\(R_{q_{i}}\) and then the output ciphertext \(ct\)\(\in\)\(R_{q_{i-1}}\) by SwitchModulu. Add: given two ciphertexts \(ct^{\prime}=(c^{\prime}_{0}\), \(c^{\prime}_{1}\), \(i\)) and \(ct^{\prime\prime}=(c^{\prime\prime}_{0}\), \(c^{\prime\prime}_{1}\), \(i\)), the addition algorithm computes the sum of the two ciphertext as \(ct^{*}=(c^{\prime}_{0}+c^{\prime\prime}_{0}\) mod \(q_{i}\), \(c^{\prime}_{1}+c^{\prime\prime}_{1}\) mod \(q_{i})\), and then converts \(ct^{*}\)\(\in\)\(R_{q_{i}}\) to \(ct\)\(\in\)\(R_{q_{i-1}}\) as the output. SwitchModulu: given a ciphertext \(\text{ct}=(c_{0},c_{1},i)\) mod \(q_{i}\), two modulus \(q_{i}\) and \(q_{j}\) where \(i>j\), the moduli switch algorithm computes the modulo inverse element \(rp_{j}=\frac{q_{j}}{q_{i}}\) in \(q_{j}\), and output the new ciphertext \(\text{ct}^{\prime}\)=\((c^{\prime}_{0}\), \(c^{\prime}_{1}\), \(j)\), where \(c^{\prime}_{1}=c_{1}\cdot rp_{j}\) mod \(q_{j}\) and \(c^{\prime}_{2}=c_{2}\cdot rp_{j}\) mod \(q_{j}\). Correctness.