一个基于整数的全同态加密改进方案

An Improved Fully Homomorphic Encryption Scheme over the Integers

目前基于整数的全同态加密方案的效率较低,与实际应用仍有一定的距离.如何提高方案的效率和安全性是全同态加密技术研究的难点.本文首先分析了全同态加密方案的构造思想,总结了基于整数的全同态加密的研究现状以及相关技术.为了进一步提高方案的效率,本文在Dijk等人DGHV方案的基础上,通过利用Gentry的全同态加密构造基本思路,提出了一个具有较小公钥尺寸和更高效率的全同态加密新方案.新方案将明文空间由{0,1}扩展到{0,1}~l,并结合公钥元素的二次形式和密文压缩技术,有效地实现了DGHV方案的批量处理功能.再利用压缩解密电路的思路,引入SSSP假设,与加法或乘法门电路构造增强(扩展)解密电路,从而实现方案的全同态.本文对方案基于无错近似最大公约数问题(error-free GCD)的安全性规约做了较详细地分析,并从公、私钥尺寸等方面与DGHV、BDGHV方案进行了比较,新方案具有更短公钥尺寸等优点.

Currently the efficiency of the known fully homomorphic encryption(FHE) schemes over the integers are extremely low and far from practical applications. How to improve the efficiency and security of FHE becomes a rather difficult task. In this paper, the construction idea of FHE is recalled, and then the state of arts and the related techniques of FHE over the integers are further summarized. In order to improve the efficiency, based on Dijk's DGHV scheme, we propose a new improved FHE scheme by using the basic idea behind Gentry's construction of FHE, which has smaller public key size and higher efficiency than the previous DGHV scheme. In particular, the improved scheme expands plaintext space from {0,1} to {0,1}~l, and further implements a batch FHE function from the original DGHV scheme by combining with both the quadratic forms of public key elements and the cipertext compression technique. Moreover, to realize the fully homomorphic scheme, we design several new addition or multiplication gate circuit structures to augmented decryption circuit by using both the approach of squashing the decryption circuit and the assumption of the sparse-subset sum problem(SSSP). The security of the new scheme based on error-free approximate GCD problem is analyzed in detail. Compared with DGHV and BDGHV schemes with respect to the size of public key and secret key, this new scheme has some new advantages such as smaller public key size.