*小康 代 (中科院重庆绿色智能技术研究院)
皓勇 王 (中科院重庆绿色智能技术研究院)
文渊 吴 (中科院重庆绿色智能技术研究院)
勇 冯 (中科院重庆绿色智能技术研究院)
One of the difficulties in designing homomorphic encryption is how to maintain the ciphertext structure. This is because the ciphertexts of current lattice-based encryption schemes are polynomial vectors or matrices. For example, in schemes such as CKKS and BGV, the ciphertext is a two-dimensional polynomial vector. After homomorphic multiplication (tensor multiplication of vectors), the dimension of the ciphertext becomes the original square. Therefore, in order to maintain the original ciphertext structure after each homomorphic multiplication, an operation called relinearization is performed. There are currently two mainstream relinearization technologies, one based on bit decomposition and the other based on module exchange. In order to convert the ciphertext to the original dimension, these two techniques need to perform $4+\log q$ and 6 polynomial multiplication respectively. This greatly slows down homomorphic evaluation. Homomorphic encryption based on NTRU is in a very delicate state. This is mainly based on two points. First of all, since it was proposed, the security of the earliest scheme NTRU-prime [ Hoffstein,Joseph \& Silverman 97] and the homomorphic scheme [Bonte et al ASIACRYPT21] has not been strictly proven, unlike LWE or RLWE, which are both based on the hardness problem of lattice or ideal lattice. Therefore, some NTRU-based homomorphic encryption schemes are generally based on some heuristic assumptions. Such as the homomorphic scheme YASHE [Bos et al IMA13] and the multi-key homomorphic scheme [L\'{o}pez-Alt, Tromer \& Vaikuntanathan STOC13] both need to rely on an assumption called the decisional small polynomial ratio assumption (DSPR). However, the DSPR assumption that the key is taken from the $\{0, 1\}$ distribution and the discreted gaussian distribution with small variance does not hold. In particular,the work [Ducas \& Woerden ASIACRYPT21] showd that when $q$ exceeds $O(n^{2.48})$, the sub-lattice attack will be very effective on solving NTRU problem. On the plus side, because NTRU’s public key and ciphertext are both a single polynomial, the ciphertext structure does not change when performing homomorphic evaluation. This therefore seems to avoid ciphertext relinearization operations. Notice that the decryption key becomes the square of the original. This is because the degree of the public key in the ciphertext becomes 2 after a homomorphic multiplication. Therefore, for initial NTRU ciphertext , after performing multiplication operations, as long as the degree of public keys in the resulting ciphertext is recorded, the corresponding decryption key can be determined. In order to control the noise, a large scaling factor can be multiplied when encoding the plaintext. Based on the above observations, we construct a homomorphic encryption scheme based on NTRU that does not require linearization. Complexity analysis and experimental results show that at the same level of homomorphic evaluation capabilities, the homomorphic multiplication speed of our scheme is $5-6$ times faster than CKKS and BFV.
Math formula preview: