对Gentry全同态加密方案中的密钥生成算法的改进

摘要

在2011年的EUROCRYPT会议上,Gentry和Halevi首次完全实现了Gentry在2009年提出的全同态加密方案.在他们的密钥生成算法中,最核心的思想是生成满足一些特殊性质的理想格.这类理想格的行列式为奇数,且Hermite标准型具有简单的形式.然而,他们没有对其给出的密钥生成算法的正确性给出严格的证明.文章给出一个更好的密钥生成算法,从如下两个方面改进了原来的算法:给出生成奇数行列式理想格的确定性算法,从而使得密钥生成的成功率接近于1;通过给出更加简单的判定条件,对新算法的正确性给出严格的证明.基于此,算法效率比原密钥生成算法提高了1.5倍.优化基于理想格的一些特殊性质,这些性质可能有其他的应用.