有限域上乘法群离散对数问题的计算复杂性是密码学研究的重要问题之一。有限素数域Fq上乘法群离散对数问题已知最快的计算方法是NFS方法,其计算复杂性为亚指数时间:有限域上离散对数问题与基于椭圆曲线双线性对的密码算法有限扩域Fqk(k>1)上乘法群离散对数在Joux于2013年发表一系列重要工作后,最近几年取得了重大的进展。具体地讲:对于小特征有限域上的离散对数问题,已经可以构造拟多项式时间的启发式算法来求解。2015年后对中等大小和大素数q的有限扩域Fqk,根据q和k的特征不同,研究人员构造出不同计算复杂度的新算法。新算法的复杂性仍然是亚指数时间,但是渐进复杂性比以前的算法有所减少。

 

基于椭圆曲线双线性对的密码算法需使用双线性对友好的椭圆曲线实现高效的双线性对运算进而构造高效实用的密码算法。由于双线性对的存在,可以利用MOV方法将双线性对使用的两个输入群G1G2上的椭圆曲线离散问题转换为输出群GT上的离散对数问题,即有限域Fqk上乘法群中的离散对数问题。所以有限域上乘法群离散对数问题的进展对基于椭圆曲线双线性对的密码算法有一定影响。具体地讲:Joux等的工作使得特征为2或者3的超奇异曲线不再适合于构造安全的双线性对密码算法系统。对采用如BN曲线、Freeman曲线、BLS12曲线、KSS曲线、BLS24曲线等构造的密码系统,我们可能需要适当调整素域Fq的大小以达到相应的安全级别。最新的报告http://eprint.iacr.org/2016/1102.pdf详细总结了最近几年该领域的进展,特别是针对128和192位安全级别上相关算法的实际复杂性进行了系统的评估。该报告显示如果考虑最近提出的新算法涉及的所有开销,现在推荐使用的曲线参数的安全性并没有受到影响,如BN-256曲线仍然可以到达128位安全级别,BLS24-480曲线依然可以到达192位安全级别。

 

可以看到经过学术界多年广泛和深入的研究,目前没有发现明显影响双线性对密码系统应用的安全性风险。虽然有些双线对友好曲线因为其数学结构特殊导致其上的离散对数问题复杂性受到学术研究进步的显著影响,但是我们只需要规避使用这类曲线即可。经典椭圆曲线密码在发展过程中也碰到类似的问题。另外正如Chatterjee,Menezes等指出的,扩域Fqk上离散问题的进展可能用于基域Fq上离散对数问题的求解,特别是如果在Fq2上离散对数问题的复杂性小于有限域上离散对数问题与基于椭圆曲线双线性对的密码算法,那么将产生一个在Fq上比目前最快离散对数算法更加高效的算法,而这样的算法在过去20年一直都没有找到。只要有限域上乘法群离散对数问题的计算复杂性仍然维持在亚指数时间,我们总是可以通过适当增加素域Fq的大小来实现指定的安全级别。在满足安全性需求的情况下,当前CPU的计算能力足以快速实现双线性对的计算,进而使得我们可以构造高效实用的密码系统。

 

更多深圳奥联关于基于椭圆曲线双线性对的密码算法安全性的建议可详见http://www.myibc.net/downloads/Progress_in_DL_on_Pairing_Friendly_Curves_(short).pdf。该文件包括深圳奥联信息安全技术有限公司在综合考虑该领域学术进展、工程实现等因素后推荐使用的曲线参数以及其上的性能评估。对比该文件和http://eprint.iacr.org/2016/1102.pdf可以看到我们推荐选择的曲线参数比Alfred Menezes等推荐的最保守的曲线参数的安全性还要高。在这些曲线上,我们通过大量的算法优化工作实现了高安全、高效率的基于椭圆曲线双线性对的密码系统。