Cryptology ePrint Archive: Report 2016/050

Improved Fully Homomorphic Encryption with Composite Number Modulus

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 a fully homomorphic encryption with composite number modulus which avoids the weak point by adopting the plaintext including the random numbers in it. In this paper I propose another fully homomorphic encryption with composite number modulus where the complexity required for enciphering and deciphering is smaller than the same modulus RSA scheme. In the proposed scheme it is proved that if there exists the PPT algorithm that decrypts the plaintext from the any ciphertexts of the proposed scheme, there exists the PPT algorithm that factors the given composite number modulus. In addition it is said that the proposed fully homomorphic encryption scheme is immune from the “p and -p attack”. 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.

Category / Keywords: secret-key cryptography / fully homomorphic encryption, multivariate algebraic equation, Gröbner basis, octonion, factoring

Original Publication (with major differences): Masahiro, Y. (2015). Fully Homomorphic Encryption without bootstrapping which was published by LAP LAMBERT Academic Publishing, Saarbrücken/Germany .

Date: received 19 Jan 2016

Contact author: tfkt8398yagi at hb tp1 jp

Available format(s): PDF | BibTeX Citation

Note: In previous report 2015/1040 in Cryptology ePrint Archive, I proposed “Improved Fully Homomorphic Encryption with Composite Number Modulus”. In the proposed report I improve the scheme proposed in previous report 2015/1040. The proposed scheme requires the smaller complexity to encipher and decipher than the scheme in previous report 2015/1040.

Version: 20160119:132558 (All versions of this report)

Short URL: ia.cr/2016/050

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]