# An Efficient BGV-type Encryption Scheme for IoT Systems
## 4 Scheme Description
SwitchKey: given a three-dimension ciphertext \(d\) = \((d_{0},d_{1},d_{2},i)\) and a switch key EPK = \((a,b)\), the key switch algorithm computes \(c_{0}\) = \(p_{i}\cdot d_{0}-b\cdot d_{2}\bmod q_{i}\) and \(c_{1}\) = \(p_{i}\cdot d_{1}-a\cdot d_{2}\bmod q_{i}\) and outputs ct = \((c_{0},c_{1},i)\). Mul: 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 multiplication algorithm invokes \(\mathrm{ct_{1}}\) \(\leftarrow\) SwitchModulu(\(\mathrm{ct_{1}}\)) and \(\mathrm{ct_{2}}\) \(\leftarrow\) SwitchModulu(\(\mathrm{ct_{2}}\)), and then invokes \(d\)\(\leftarrow\) CTLinearization (\(\mathrm{ct_{1}}\), \(\mathrm{ct_{2}}\)). Finally, it invokes ct \(\leftarrow\) SwitchKey(\(d\)) and outputs ct.  
Add: 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 addition algorithm computes \(c_{0}\) = \(c_{0}^{(1)}\)+\(c_{0}^{(2)}\bmod q_{i}\) and \(c_{1}\) = \(c_{1}^{(1)}\)+\(c_{1}^{(2)}\bmod q_{i}\), and then outputs ct = \((c_{0},c_{1},i)\). Correctness. Above scheme is nearly same as BGV except that the switch key is fixed and the key switch algorithm does not switch ct to a lower level one at last. First, given a ciphertext ct = \((c_{0},c_{1},L-1)\) outputted by Encrypt, a secret key SK = \(s\), we have \(\langle ct,s\rangle\bmod p=c_{0}-s\cdot c_{1}\bmod p=(b\cdot v+p\cdot e_{0}+m-sa \cdot v-sp\cdot e_{1})\bmod q_{L-1}\bmod p=m+p(e_{0}+\epsilon-s\cdot e_{1})\bmod q _{L-1}\bmod p=m\). Second, given a secret key \(\text{SK}=s\), a ciphertext \(\text{ct}=(c_{0},c_{1},i)\) outputted by \(\text{Mul}\), where \(\text{ct}\) is the product of \(\text{ct}_{1}=(c_{0}^{(1)},c_{1}^{(1)},i)\) and \(\text{ct}_{2}=(c_{0}^{(2)},c_{1}^{(2)},i)\), we have \(\langle ct,s\rangle\) mod \(p=c_{0}-s\cdot c_{1}\) mod \(p\). As the observations in Section 3.1, \(c_{0}-s\cdot c_{1}\) mod \(p=(c_{0}^{(1)}-sc_{1}^{(1)})(c_{0}^{(2)}-sc_{1}^{(2)})-pec_{1}^{(1)}c_{1}^{( 2)}\) mod \(q_{i}\) mod \(p=(m_{1}+p(e_{0}^{(1)}+\epsilon-s\cdot e_{1}^{(1)}))\)\((m_{2}+p(e_{0}^{(2)}+\epsilon-s\cdot e_{1}^{(2)}))-pec_{1}^{(1)}c_{1}^{(2)}\) mod \(q_{i}\) mod \(p=m_{1}m_{2}\). Third, given a secret key \(\text{SK}=s\), a ciphertext \(\text{ct}=(c_{0},c_{1},i)\) outputted by \(\text{Add}\), where \(\text{ct}\) is the sum of \(\text{ct}_{1}=(c_{0}^{(1)},c_{1}^{(1)},i)\) and \(\text{ct}_{2}=(c_{0}^{(2)},c_{1}^{(2)},i)\), we have \(\langle ct,s\rangle\) mod \(p=c_{0}-s\cdot c_{1}\) mod \(p=(c_{0}^{(1)}+c_{0}^{(2)})-s(c_{1}^{(1)}+c_{1}^{(2)})\) mod \(q_{i}\) mod \(p=m_{1}+p(e_{0}^{(1)}+\epsilon-s\cdot e_{1}^{(1)})+m_{2}+p(e_{0}^{(2)}+ \epsilon-s\cdot e_{1}^{(2)})\) mod \(q_{i}\) mod \(p=m_{1}+m_{2}\). Security. All of our changes are on the homomorphic computation parts, including the switch key generation algorithm and the multiplication algorithm. The basic encryption-decryption function parts, including the secret key generation algorithm, the public key generation algorithm, the encryption algorithm, and the decryption algorithm are the same as known schemes [5,19]. As introduced in the background, the security of BGV-type cryptosystems is based on the RLWE assumption. In our scheme, the public key (_a,b_) where \(b=a\cdot s+p\cdot\epsilon\) mod \(q_{L-1}\) has similar form as that of the distribution (_a,a\(\cdot s+\epsilon\)_). The difference is \(p\) and \(q_{L-1}\) are exposed to the adversary in the setup algorithm. However, this does not reveal more information, because the error is provided by \(\epsilon\) but not \(p\). We may regard the distribution in RLWE assumption as (_a,a\(\cdot s+p\cdot\epsilon\)_) where \(p=1\). In our scheme, \(p\) is a prime number referencing the security parameter. Then the forms of the assumption are same. Logically, only modifying the multiplication algorithm will not affect the security of the basic encryption-decryption function. Thus, the security of our scheme does not need to be re-proved.