Paper 2016/653

Fully Homomorphic Encryption with Zero Norm Cipher Text

Masahiro Yagisawa

Abstract

Gentry’s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In previous work I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the plaintext. I also proposed fully homomorphic encryptions with composite number modulus which avoid the weak point by adopting the plaintext including the random numbers in it. In this paper I propose another fully homomorphic encryption with zero norm cipher text where zero norm medium text is generated and enciphered by using composite number modulus. In the proposed scheme it is proved that if there exists the PPT algorithm that generates the cipher text of the plaintext -p from the cipher text of any plaintext p, there exists the PPT algorithm that factors the given composite number modulus. That is, we include the random parameter in the plaintext so that if the random parameter and the plaintext are separated, then the composite number to be the modulus is factored. Since the scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on.

Note: I revised line 17 of page 23 as follows. =( y1+ z1)( y2+ z2) mod q