新的格上基于身份的全同态加密方案

Novel identity-based fully homomorphic encryption scheme from lattice

分析以往格上基于身份的全同态加密方案,指出方案效率低的根本原因在于陷门生成和原像采样过程的复杂度过高,为此提出一种新的解决方案。先将新型陷门函数与对偶容错学习(LWE,learning with errors)算法有机结合,构造一种新的格上基于身份的加密方案;再利用特征向量方法转化为格上基于身份的全同态加密方案。对比分析表明,所提方案的陷门生成复杂度显著降低,原像采样复杂度约降低为以往方案的1/3,SIVP近似因子缩小为以往方案的1/m^(1/2)。在标准模型下,方案安全性归约至判定性LWE的难解性,并包含严格的安全性证明。

The previous identity-based homomorphic encryption schemes from lattice was analyzed. That the high com- plexity in previous schemes was mainly caused by trapdoor generation and preimage sampling was pointed out. A new solution was proposed. A novel identity-based encryption scheme from lattice by combining new trapdoor function and dual-LWE algorithm organically was constructed, and it was transformed to an identity-based fully homomorphic encryp- tion scheme from lattice by employing the idea of eigenvector. Comparative analysis shows that the scheme＇s complexity of trapdoor generation has a significant reduction, the complexity of preimage sampling has a nearly three-fold reduction, and the SIVP approximation factor has a a√m times reduction. The security of the proposed scheme strictly reduces to the hardness of decisional learning with errors problem in the standard model.