基于矩阵变换的NTRUSign密钥生成算法

Algorithm of keys generation for NTRUSign based on matrix transformation

首次提出将矩阵变换应用于NTRUSign签名算法中,在NTRUSign签名算法中公开密钥和私有密钥的生成算法是最关键的部分,其实现时所花的时间占整个签名算法实现约一半以上的时间,直接影响NTRUSign的工作性能。矩阵是处理数学问题的重要工具,给出一种新的矩阵变换,并将之应用于求多项式的最大公因式问题中,且给出相应的求两个多项式最大公因式算法,并以该算法应用于NTRUSign中,得出NTRUSign密钥生成的优化算法。实验结果表明,该算法在寻找小多项式F和G比由JeffreyHoffstein给出的NTRUSign密钥生成算法的计算量和所占用的系统资源较少,该算法在生成密钥速度略快,为较有效的算法。

The algorithm of keys generation for NTRUSign is the most crucial section, it should take more half time of implement of the NTURSign algorithm, affect the performance of NTRUSign operation directly. Matrix is a important tool to deal with some mathematic problems. A new matrix transformation is proposed to find the great common formula of two polynomials. Furthermore, this transformation is used in generating the keys for the NTRUSign, a improved algorithm of keys generation for NTRUSign is obtained. Experimental analysis indicate that the algorithm to find the two short polynomials F and G is faster than the algorithm presented by Jeffrey Hoffstein described. And it takes less complexity of the computation, is the more efficient algorithm of keys generation for NTURSign.