Paper 2018/232

Improved fully homomorphic public-key encryption with small ciphertext size

Masahiro Yagisawa

Abstract

A cryptosystem which supports both addition and multiplication (thereby preserving the ring structure of the plaintexts) is known as fully homomorphic encryption (FHE) and is very powerful. Using such a scheme, any circuit can be homomorphically evaluated, effectively allowing the construction of programs which may be run on ciphertexts of their inputs to produce a ciphertext of their output. Since such a program never decrypts its input, it can be run by an untrusted party without revealing its inputs and internal state. The existence of an efficient and fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing. In previous work I proposed the fully homomorphic public-key encryption scheme with the size of ciphertext which is not small enough. In this paper the size of ciphertext is one-eighth of the size in the previously proposed scheme. Because proposed scheme adopts the medium text with zero norm, it is immune from the the “p and -p attack”. As the proposed scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree, it is immune from the Gröbner basis attack, the differential attack, rank attack and so on.

Note: In previous report 2018/088 in Cryptology ePrint Archive, I proposed “Fully homomorphic public-key encryption with small ciphertext size” which has the ciphertext such that C(X,p)=(cij) (i,j=0,…,7)∈O[X] corresponding to a plaintext p. This time I propose the scheme which has the ciphertext such that C(p)= (c0,…,c7)∈O corresponding to a plaintext p. Then in this scheme the size of ciphertext is one-eighth of the size in the scheme proposed before (report 2018/088).