Implementing optimized pairings with elliptic nets

详细信息    查看全文

• 作者：ChunMing Tang (1) (2) (4)
  DongMei Ni (2) (4)
  MaoZhi Xu (2) (4)
  BaoAn Guo (3)
  YanFeng Qi (2) (3) (4)
  
• 关键词：elliptic curves ; elliptic nets ; pairings ; Miller’s algorithm ; pairing ; based cryptography
• 刊名：SCIENCE CHINA Information Sciences
• 出版年：2014
• 出版时间：May 2014
• 年：2014
• 卷：57
• 期：5
• 页码：1-10
• 全文大小：
• 参考文献：1. Boneh D, Franklin M. Identity-based encryption from the Weil pairing. In: Kilian J, ed. Proceedings of CRYPTO2001, Vol. 2139 of Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2001. 213-29
  2. Joux A. A one round protocol for tripartite Diffie-Hellman. In: Proceedings of Algorithmic Number Theory Symposium on Algorithmic Number Theory. London: Springer-Verlag, 2000. 385-94 CrossRef
  3. Boneh D, Lynn B, Shacham H. Short signatures from the Weil pairing. In: Boyd C, ed. Proceedings of ASIACRYPT 2001, Vol. 2248 of Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2001. 514-32
  4. Boneh D, Crescenzo G D, Ostrovsky R, et al. Public-key encryption with keyword search. In: Proceedings of Eurocrypt 2004. Berlin: Springer-Verlag, 2004. 506-22 CrossRef
  5. Yao A C, Zhao Y. Computationally-Fair Group and Identity-Based Key-Exchange. In: Agrawal M, Cooper S B, Li A, eds. Vol. 7287 of Lecture Notes in Computer Science. Berlin/Heidelberg: Springer-Verlag, 2012. 237-47
  6. Eissa T, Razak S A, Ngadi M D A. Towards providing a new lightweight authentication and encryption scheme for MANET. Wirel Netw, 2011, 17: 833-42 CrossRef
  7. Cheng P Q, Gu Y, Lv Z H, et al. A performance analysis of identity-based encryption schemes. In: Chen L, Yung M, Zhu L, eds. INTRUST 2011, LNCS 7222. Berlin/Heidelberg: Springer-Verlag, 2012. 289-03
  8. Fujioka A, Suzuki K. Sufficient condition for identity-based authenticated key exchange resilient to leakage of secret keys. In: Kim H, ed. ICISC 2011, LNCS 7259. Berlin/Heidelberg: Springer-Verlag, 2012. 490-09
  9. Barreto P S L M, Kim H Y, Lynn B, et al. Efficient algorithms for pairing-based cryptosystems. In: Proceedings of Advances in Cryptology-CRYPTO 2002, LNCS 2442. Berlin/Heidelberg: Springer-Verlag, 2002. 354-69 CrossRef
  10. Aranha D F, Karabina K, Longa P, et al. Faster explicit formulas for computing pairings over ordinary curves. In: Advances in Cryptology-EUROCRYPT 2011, LNCS 6632. Berlin/Heidelberg: Springer-Verlag, 2011. 48-8 CrossRef
  11. Cheung R C C, Duquesne S, Fan J F, et al. FPGA implementation of pairings using residue number system and lazy reduction. In: Cryptographic Hardware and Embedded Systems-CHES 2011, LNCS 6917. Berlin/Heidelberg: Springer-Verlag, 2011. 421-41 CrossRef
  12. Stange K E. The Tate pairing via elliptic nets. In: Pairing-Based Cryptography-PAIRING 2007, LNCS 4575. Berlin: Springer, 2007. 329-48 CrossRef
  13. Everest G, van der Poorten A, Shparlinski I, et al. Recurrence Sequences. Vol. 104 of Mathematical Surveys and Monographs. American Mathematical Society, 2003. 163-75
  14. Shipsey R. Elliptic divibility sequences. Dissertation for the Doctoral Degree. University of London, 2001
  15. Ward M. Memoir on elliptic divisibility sequences. Amer J Math, 1948, 70: 31-4 CrossRef
  16. Stange K E. Elliptic nets and elliptic curves. Dissertation for the Doctoral Degree. Brown University, 2008
  17. Hess F. Pairing lattices. Galbraith S D, Paterson K G, eds. Pairing 2008, LNCS 5209. Berlin: Springer-Verlag, 2008. 211-24
  18. Hess F, Smart N, Vercauteren F. The Eta-pairing revisited. IEEE Trans Inform Theory, 2006, 52: 4595-602 CrossRef
  19. Matsuda S, Kanayama N, Hess F, et al. Optimised versions of the Ate and twisted Ate pairings. In: the 11th IMA International Conference on Cryptography and Coding, LNCS 4887. Berlin: Springer-Verlag, 2007. 302-12 CrossRef
  20. Hong H, Lee E, Lee H S, et al. Simple and exact formula for minimum loop length in Ate / i pairing based on Brezing-Weng curves. Designs Codes Cryptogr, 2013, 67: 271-92 CrossRef
  21. Barreto P S L M, Naehrig M. Pairing-friendly elliptic curves of prime order. In: Selected Areas in Cryptography-SAC 2005, LNCS 3897. Berlin: Springer, 2006. 319-31 CrossRef
  22. Freeman D, Scott M, Teske E. A taxonomy of pairing-friendly elliptic curves. J Cryptol, 2010, 23: 224-80 CrossRef
  23. Duquesne S, Frey G. Background on pairings. In: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Boca Raton: Chapman & Hall/CRC, 2006. 115-24
  24. Nogami Y, Akane M, Sakemi Y, et al. Integer variable / χ-based Ate pairing. In: Galbraith S D, Paterson K G, eds. Pairing 2008, LNCS 5209. Heidelberg: Springer, 2008. 178-91 CrossRef
  
• 作者单位：ChunMing Tang (1) (2) (4)
  DongMei Ni (2) (4)
  MaoZhi Xu (2) (4)
  BaoAn Guo (3)
  YanFeng Qi (2) (3) (4)
  
  1. School of Mathematics and Information, China West Normal University, Nanchong, 637002, China
  2. LMAM, Chinese Ministry of Education, Peking University, Beijing, 100871, China
  4. School of Mathematical Sciences, Peking University, Beijing, 100871, China
  3. Aisino Corporation Inc., Beijing, 100195, China
  
• ISSN：1869-1919

文摘

In this paper, we use elliptic nets to implement the optimized Ate pairings and optimal pairings on the Barreto-Naehrig curves with embedding degree 12. In order to do the arithmetic of elliptic curves over finite fields with elliptic nets, we first give some basic properties of elliptic nets associated to elliptic curves over finite fields and the expression of Miller function in terms of elliptic nets. Then we give formulae to compute some optimized pairings with elliptic nets, which is a new method to implement pairings. This method with elliptic nets has time complexity comparable to Miller’s algorithm and it can be optimized.