# An Efficient BGV-type Encryption Scheme for IoT Systems
## 5 Implementation and Performance Analysis  
In this section, we instantiate the above scheme in the range of \"int\", which occupies 32 bits. \"int\" is the most intuitive data type in the C language. It expresses numbers between \(-2147483648\) and \(2147483647\). We remove the negative part and let all computation results within [0,2147483647]. Although \"int\" is too small to prevent attacks, the correctness and performance of above scheme can be verified. In practical applications, large number, like \"bigint\" in C++ or \"biginteger\" in Java can easily replace it. In our implementation, the depth \(L\) is set to 3. \(p=11\), \(m=5\), \(d=1\), and \(l=(\phi(5)=4)/(d=1)=4\). Moreover, \(p_{0}=11\), \(p_{1}=23(=2\times 11+1)\), and \(p_{2}=67(=6\times 11+1)\). Correspondingly, \(q_{0}=11\), \(q_{1}=253\) (=\(11\times 23\)), \(q_{2}=16951\) (=\(11\times 23\times 67\)). The modulu inverse \(rp_{1}=34\) can be computed such that \(p_{2}\cdot rp_{1}=67\times 34=1\) mod \(253\). Detailed implements to find it are given in Appendix A.2 The reason we set \(p=11\) is that the two smallest prime numbers those equal 1 modulu 11 are 23 and 67. Then \(16951^{2}=287336401<2147483647\) can ensure all of the intermediate computation results do not exceed the representation range of \"int\". If we set \(p=13\), the two smallest prime numbers are \(p_{1}=53\) and \(p_{2}=79\). Then we have \(q_{1}=689\), \(q_{2}=54431\). Because \(54431^{2}=2962733761>2147483647\), the decryption may fail at last. Of course, \(p\) can be set to smaller prime numbers than 11 in the toy implementation. The initial ciphertext generated by the encryption algorithm, the secret key, the public key, and the switch key generated by the key generation algorithms are all at level 2. To simplify the implementation, all of the random numbers are chosen from the random number generator in the C library but not \(\chi\). Without loss of generality, we simply select a four-dimension vector (1,2,3,4) as the initial plaintext and generate corresponding ciphertext \(\text{ct}_{0}\). Subsequently, we compute \(\text{ct}_{i+1}=\text{ct}_{i}\cdot\text{ct}_{0}\) and \(\text{ct}_{i+2}=\text{ct}_{i+1}+\text{ct}_{0}\) for \(i=0,2,4,6,8\). For example, \(\text{ct}_{1}\) should be (1,4,9,5) and \(\text{ct}_{2}\) should be (2,6,1,9), etc. The result of correctness validation is in Figure 1.  
The vectors, \(\text{pt}[0]\), \(\cdots\), \(\text{pt}[10]\), are plaintext multiplication and addition results. The vectors, \(\text{dpt}[0]\), \(\cdots\), \(\text{dpt}[10]\), are the decryption results of the ciphertext of corresponding plaintext. We can see that \(\text{dpt}[i]\)s are the same as corresponding \(\text{pt}[i]\)s.  
Next, we test the performance of our scheme. The source code of our implementation is given in Appendix A. It includes three files, stdafx.h, stdafx.cpp, and unlimited homomorphic encryption.cpp. \"stdafx.h\" defines all the data structures. \"stdafx.cpp\" defines all of the functions. The functions are invoked in \"unlimited homomorphic encryption.cpp\". Appendix B lists the source code of an implementation based on the Helib library. The implementation uses similar parameters as ours. Figure 2 lists their executing time. Our test machine is a ThinkPad X1 laptop with Intel(R) Core(TM)j7-8750H CPU @2.2 GHz 8 cores Visual Studio 2005, Microsoft, Redmond, WS, USA). Intuitively, the homomorphic calculation time grows linearly in our scheme, but sub-exponentially in the Helib-based scheme. Meanwhile, the execution time of our scheme is much less than the Helib-based one. We know that RSA is an encryption scheme only supporting multiplicative homomorphic and it has been applied into many security applications. As a further comparison, we list the Mul operation time of RSA. Since the ciphertext modulo of our scheme is \(q_{2}=16951\), we select \(p=127\) and \(p=131\) in  
Figure 1: Example of five Multiplications and five Additions. Figure 2: Efficiency Comparison. the toy RSA example, such that their product \(n=16637\) is very close to \(q_{2}\).