# An Efficient BGV-type Encryption Scheme for IoT Systems
## 1 Introduction  
The Internet of Thing (IoT) systems have been widely used in people's daily life [1; 2]. In an IoT system, one can control his/her remote devices [3] to finish expected tasks. That requires the devices to have secure computing power [4]. Homomorphic encryption allows a device to perform arbitrary computations on encrypted data without user secret key. When compared with non-homomorphic encryptions, it removes the trust on the device and makes us ease to use the computing power of the device. Hence, homomorphic encryption has broad application prospects [5; 6; 7; 8; 9; 10; 11]. In a breakthrough work [12], [PERSON] demonstrated that fully homomorphic encryption was theoretically possible based on ideal lattices. In [PERSON]'s work, the ciphertext can be regarded as some \"noise\" attached to the plaintext, and the noise will increase along with evaluation times. When the noise exceeds a threshold value, which makes decryption fail, a bootstrapping program can refresh the noise introduced by evaluations and make the ciphertext as a new one generated by the encryption algorithm. However, the efficiency of the scheme is far from practical application.  
Following [PERSON]'s work, many researchers tried to improve the performance of homomorphic encryption. Based on the learning with error assumption [13; 14], [PERSON] and [PERSON] [15; 16] (BV) presented a dimension-modulus reduction technique and constructed a leveled homomorphic encryption without the requirement of a bootstrappable encryption. [PERSON], [PERSON], and [PERSON] [17] (BGV) then dramatically improved the performance of the BV-type homomorphic encryption. Moreover, [PERSON] and [PERSON] and [PERSON] reduced the size of public keys and ciphertexts [18] of the BGV-type scheme at the cost of increasing the probability of key recovery attack. Subsequently, they optimized the execution times of fast Fourier transform (FFT) and Chinese reminder theorem (CRT) by reducing thenumber of times to convert polynomials between coefficient and evaluation representations [16; 17; 19]. [PERSON] [20] further reduced the ciphertext noise growth rate of multiplication operations. [PERSON] and [PERSON] [21; 22; 23] continuously and roundly optimized BGV-type scheme in the algorithm implementation aspect. [PERSON], [PERSON], and [PERSON] [24] improved parallel performance to packet more data within one instruction. [PERSON], [PERSON], [PERSON] and [PERSON] [25] designed a custom hardware accelerator to improve the performance of polynomial multiplier. [PERSON], [PERSON], and [PERSON] [26] provided a compiler for homomorphic encryption and let the programmer with no special knowledge of homomorphic encryption easily use it. In addition, many efforts [22; 27; 28; 29; 30; 31; 32; 33; 34] have been paid for improving the performance of bootstrapping. As [PERSON], [PERSON], and [PERSON] [34] declared, the bootstrapping time per plaintext slot had been reduced to about 1 s.  
This paper primarily focuses on improving the storage and computation efficiency of BGV-type cryptosystem. In previous works, we find that only [19] mentioned this problem. However, the main goal of [19] is to reduce the representation transformation times of FFT and CRT, but not reduce the size of public key, simplify the multiplication algorithm, or further control the noise. Hence, the improvement directions presented in [19] are different from our work.  
Organization. In Section 2, we introduce the plaintext and ciphertext encoding manners and the principle of BGV. Afterwards, in Section 3, we briefly introduce a BGV-type scheme and then our modifications on BGV. In Section 4, our scheme is given and a proof of concept implementation with the C language and a performance test are provided in Section 5. Section 6 concludes the paper. At last, all of the source codes of our proof of concept implementation are given in Appendix A and the codes of benchmark implementations of Helib and RSA are given in Appendixes B and C. These appendices may help reviews.