Abstract: In the application of pairing based cryptosystems, especially the η_T pairing, the fast and effective implementation of the pairings depends on the effective multiplications in the extension fields. The authors propose the dual interpolation multiplication (DIM) algorithm in F_3^6m which takes asymptotically 11 multiplications in F3m ( m→∞) . This algorithm reaches the theoretical lower bound of the number multiplications in F_3^6m.

Key words: pairing based cryptosystems, multiplications in finite fields, Vandermonde matrix, interpolation of dual polynomials

摘要： 在基于配对的公钥密码学应用中, 配对的有效快速实现依赖于基域的扩域中乘法算法的有效快速的实现,特别是在η_T配对的实现中需要 F_3^6m中的快速乘法运算。作者提出了对偶插值算法, 其渐近复杂度为 11 次基域中 的乘法运算, 这达到了F_3^6m中乘法运算的理论下界。

关键词: 基于配对的密码学, 有限域乘法, Vandermonde矩阵, 对偶多项式插值