Abstract: In order to improve the efficiency of the fully homomorphic encryption scheme, based on partially approximate common divisor problem, a fully homomorphic encryption scheme over the integer is presented. Compared with the Dijk et al’s scheme, this scheme has these advantages of a smaller public key size and faster computation. Under this condition of allowing for a negligible probability of decryption error, this paper further reduces the complexity of the decryption algorithm, thus the given scheme is more efficient. Finally, it is proved that the scheme is semantically secure.

Key words: fully homomorphic encryption, public key size, efficiency, security

摘要： 为了提高全同态加密的效率，基于部分近似最大公因子问题，提出了一个整数上的全同态加密方案。与Dijk等人的方案比较，具有较小的公钥尺寸，计算较快速的特点。在允许可忽略概率解密错误的条件下，进一步降低了方案的解密算法复杂度，提高了方案的效率，并证明了该方案具有语义安全。

关键词: 全同态加密, 公钥尺寸, 效率, 安全性