北京大学学报（自然科学版）

实现k=18的Brezing-Weng曲线的最优配对

唐春明1,亓延峰1,徐茂智1,2   

  1. 1. 北京大学数学科学学院,北京 100871; 2.网络与软件安全保障教育部重点实验室,北京 100871;
  • 收稿日期:2010-05-14 出版日期:2010-09-20 发布日期:2010-09-20

Implementing Optimal Pairings over Brezing-Weng Elliptic Curves with k=18

TANG Chunming1, QI Yanfeng1, XU Maozhi1,2   

  1. 1. School of Mathematical Sciences, Peking University, Beijing 100871; 2. Key Laboratory of Network and Software Security Assurance, Beijing 100871;
  • Received:2010-05-14 Online:2010-09-20 Published:2010-09-20

PDF (翻译版)

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

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

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 log2r/φ(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 Fq or Fq3. 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

中图分类号: 

版权所有 © 《北京大学学报（自然科学版）》编辑部
技术支持：北京玛格泰克科技发展有限公司