The Final Exponentiation in Pairing-Based Cryptography

Abstract

In recent years, there has been many work related to the pairing-based cryptosystems. These systems rely on bilinear nondegenerate maps called pairings, such as Tate pairing defined over elliptic curves. In these systems, there is always a powering of an element to compute. To do this, one can utilize compressed form of the element in the cyclotomic subgroup of the finite fields $\mathbb F^{*}_{q^{k}}$. Compressed form of field elements also gives rise to define new public key cryptosystems that play an important role in ensuring information security. In this paper, we review how to compute the final powering efficiently. Then we illustrate some algorithms to compute the power of an element in $\mathbb F^{*}_{q^{k}}$ with $k=2,3,4,6,10$ and propose new formulae for $k=14$. We also show how to define short signature scheme using compressed pairings.

Keywords

• —exponentiation, compression, pairing-based cryptography

References

1. P. S. L. M. Barreto, S. D. Galbraith, C. Eigeartaigh, and M. Scott. “Efficient pairing computation on supersingular abelian varieties”. Designs, Codes and Cryptography, 42(3), pages 239- 271, 2007.
2. P. S. L. M. Barreto, H. Y. Kim, B. Lynn, and M. Scott. “Efficient algorithms for pairing-based cryptosystems”. Advances in Cryptology - Crypto 2002, LNCS 2442, Springer-Verlag, pages 354-368, 2002.
3. P. S. L. M. Barreto, B. Lynn, and M. Scott. “On the selection of pairing-friendly groups”. Selected Areas in Cryptography - SAC 2003, LNCS 3006, pages 17-25, 2004.
4. I.F. Blake, G. Seroussi, and N.P. Smart. “Advances in Elliptic Curve Cryptography”. London Math. Soc. Lec. Note S., 317, Cambridge, 2005.
5. D. Boneh, and M. Franklin. “Identity-based encryption from the Weil pairing”. SIAM Journal of Computing, 32(3), pages 586- 615, 2003.
6. D. Boneh, B. Lynn, and H. Shacham. “Short signatures from the Weil pairing”. Advances in Cryptology - Asiacrypt 2001, LNCS 2248, Springer-Verlag, pages 514-532, 2002.
7. W. Bosma, J. Hutton, and E. Verheul. “Looking beyond XTR”. Advances in Cryptology - Asiacrypt 2002, LNCS 2501, Springer- Verlag, pages 46-63, 2002.
8. A. Brouwer, R. Pellikaan, and E. Verheul. “Doing more with fewer bits”. Advances in Cryptology - Asiacrypt 1999, LNCS 1716, pages 321-332, 1999.

9. C. M. Fiduccia. “An efficient formula for linear recurrences”. SIAM J. Comput., 14, pages 106-112, 1985.
10. S. Galbraith, K. Harrison, and D. Soldera. “Implementing the Tate pairing”. Algorithmic Number Theory Symposium - ANTS V, LNCS 2369, pages 324-337, 2002.
11. K. Giuliani, and G. Gong. “Efficient Key Agreement and Sig- nature Schemes Using Compact Representations in GF (p)”. IEEE International Symposium on Information Theory - ISIT 2004, pages 13-13, 2004.
12. K. Giuliani, and G. Gong. “A New Algorithm to Compute Remote Terms in Special Types of Characteristic Sequences”. Sequences and Their Applications - SETA 2006, LNCS 4086, pages 237-247, 2006.
13. G. Gong, and L. Harn. “Public-key cryptosystems based on cubic finite field extensions”. IEEE Transactions on Information Theory 45, no. 7, pages 2601-2605, 1999.
14. G. Gong, L. Harn, and H. Wu. “The GH Public-key Cryptosys- tems”. Selected Areas in Cryptography - SAC 2001, LNCS 2259, pages 284-300, 2001.
15. G. Gong, A. Hassan, H. Wu, and A. Youssef. “An Efficient Algorithm for Exponentiation in DH Key Exchange and DSA in Cubic Extension Fields”. Research report at Faculty of Math., University of Waterloo, 2002.
16. F. Hess, N. Smart, and F. Vercauteren. “The eta pairing revis- ited”. IEEE Transactions on Information Theory, 52(10), pages 4595-4602, 2006.
17. K. Hoffman, and R. Kunze. “Linear Algebra”. Prentice Hall, New Jersey, USA, 2nd edition, 1971.
18. K. Karabina. “Factor-4 and 6 compression of cyclotomic sub- 2groups of F*4m 2010.
19. B. B. Kırlar. “Elliptic Curve Pairing-Based Cryptography”, PhD Thesis, 2010.
20. E. Lee, H. Lee, and C. Park. “Efficient and generalized pairing computation on abelian varieties”. Cryptology ePrint Archive.
21. A. Lenstra, and E. Verheul. “The XTR public key system”. Advances in Cryptology - Crypto 2000, LNCS 1880, pages 1-19, 2000.
22. R. Lidl, and H. Niederreiter. “Finite Fields”. Cambridge Uni- versity Press, UK, 2nd edition, 1997.
23. B. Lynn. “On The Implementation of Pairing-Based Cryptosys- tems”, PhD Thesis, 2007.
24. V. Miller. “The Weil pairing, and its efficient calculation”. Journal of Cryptology, 17(4), pages 235-262, 2004.
25. A. Miyaji, M. Nakabayashi, and S. Takano. “New explicit conditions of elliptic curve traces for FR-reduction”. IEICE Trans. Fund. Electron. Comm. Comput. Sci., E84-A(5), pages 1234-1243, 2001.
26. L. Quoos, and S.-F. Mjİlsnes. “Public Key Systems Based on Finite Field Extensions of Degree Five”. Presented at Fq7 conference, 2003.
27. M. Shirase, D. Han, Y. Hibin, H. Kim, and T. Takagi. “A more compact representation of XTR cryptosystem”. IEICE Trans. Fund. Electron. Comm. Comput. Sci., E91-A(10), pages 2843- 2850, 2008.
28. M. Scott, and P. Barreto. “Compressed pairings”. Advances in Cryptology - Crypto 2004, LNCS 3152, Springer-Verlag, pages 140-156, 2004.
29. P. Smith, and M. Lennon. “LUC: A new public key system”. Proceedings of the 9th IFIP Symp. - IFIP/Sec 1993, pages 103- 117, 1993.
30. P. Smith, and C. Skinner. “A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms”. Advances in Cryptology - Asiacrypt 1994, LNCS 917, pages 357-364, 1994.
31. S.-M. Yen, and C.-S. Laih. “Fast algorithms for LUC digital signature computation”. IEE Proc.Comput. Tech. 142(2), pages 165-169, 1995.
32. C. Zhao, F. Zhang, and J. Huang. “A note on the ate pairing”. Cryptology ePrint Archive.