Abstract: The authors consider the construction and implementation of optimal pairings over Brezing-Weng elliptic curves with embedding degree 18. The loop length in the optimal pairing is log₂r/φ(18), which is the theoretical lower bound. A twisted map of degree 6 is used to realize the point compression and reduce the division operations in Miller algorithm, then most of operations can be implemented in F_q or F_q³. An efficient algorithm for the optimal pairing is given accordingly. Frobenius map in finite fields is used to reduce the computation in the final power operation of the optimal pairing computation.

Key words: Brezing-Weng elliptic curves, pairing friendly elliptic curves, Tate pairing, Ate pairing, pairing-based cryptography

摘要： 研究了嵌入次数为 18 的Brezing-Weng 椭圆曲线上的最优配对的构造与实现。给出配对的Miller 算法的循环长度为log₂r/6, 达到了Miller 算法循环长度的猜想下界log₂r/φ(18) 。使用 6 次扭转映射实现了点的压缩表示, 并减少了Miller 算法中的除法运算, 从而使得配对中的大多数计算只需要在F_q或F_q³上进行。给出了一个有效计算最优配对的算法。最后使用有限域上的Frobenius 映射简化了配对算法中最终的幂运算。

关键词: Brezing-Weng椭圆曲线, 配对友好曲线, Tate配对, Ate配对, 配对的密码学