|||
我们从噪音、参数及性能、安全性三个方面对DGHV方案进行分析。
噪音问题:噪音问题直接影响方案的同态计算能力。上述方案中,两个密文之和的噪音等于噪音之和,两个密文之积的噪音等于噪音之积,所以噪音的增长主要来自于乘法。假设DGHV方案中的初始密文噪音为xi,且|xi|<B,那么方案能对密文执行多少次同态计算呢?令f (x1,…, xt )是次数为d的初等对称多项式,则当 |f (x1,…, xt )| < p/2时方案能够正确执行该函数,显然有 |f (x1,…, xt )|< td • Bd,令td • Bd < p/2,则有d < (log p)∕(log tB)。而解密电路的运算次数主要取决于c·p-1,然而p-1是一个小数,为了保证c·p-1取整之后的精确度,p-1要取log c位。由于两个t位数的乘积次数最多为2t1.71t=2t2.71,所以c· p-1的运算次数至少为2(log p)2.71(具体解释参见[49,50]),显然大于方案所能执行的次数d,因此需要压缩解密电路。而压缩解密电路的目的是为了通过启动技术获得全同态加密方案。由于计算次数与深度是对数关系,所以DGHV方案的部分同态计算电路深度是logd,非常浅。
参数及性能:通过上述噪音分析可以看到,要想提高同态计算能力,可以增大模p的取值,但是为了抵抗各种格的攻击,要求log qi要远远大于log p2,所以提高p的值将会导致密文变得很大。一个比较合适的参数选择是:,
,
,
,
。部分同态方案中有
个公钥,每个公钥xi的长度为
,则整个公钥的长度达到了
。在实践中为了抵抗格的攻击,每个公钥尺寸至少应该为223位,那么公钥大小就可达246位,对于实践应用来说太大了!。
根据上述参数选择,两个密文乘积的计算复杂度是O(),由于方案是利用启动技术,而启动的计算复杂度是
,所以方案的门电路计算复杂度是O(
)。整数上的全同态加密方案最大优势就是易于理解。随后Coron 等人对DGHV方案进行了优化[29,30],公钥尺寸下降到
。
安全性:方案的安全性依赖于两个问题:一个是近似GCD问题,另一个是稀疏子集和问题。前者在部分同态加密方案中使用,后者是在压缩电路时使用。近似GCD问题已经有比较深入的研究[52]。目前稀疏子集和问题还没有被深入研究,在构造全同态加密方案中,只是假设该问题是安全的,这方面值得进一步深入研究。但是在第二代全同态加密方案中,已经无需使用该假设了。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2025-3-19 03:41
Powered by ScienceNet.cn
Copyright © 2007-2025 中国科学报社