- Tadanori Teruya18,
- Kazutaka Saito19,
- Naoki Kanayama20,
- Yuto Kawahara21,
- Tetsutaro Kobayashi21 &
- …
- Eiji Okamoto20
Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 8365))
Included in the following conference series:
924Accesses
11Citations
Abstract
In the present paper, we propose constructing symmetric pairings by applying the Ate pairing to supersingular elliptic curves over finite fields that have large characteristics with embedding degree three. We also propose an efficient algorithm of the Ate pairing on these curves. To construct the algorithm, we apply the denominator elimination technique and the signed-binary approach to the Miller’s algorithm, and improve the final exponentiation. We then show the efficiency of the proposed method through an experimental implementation.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adj, G., et al.: Weakness of\(\mathbb{F}_{3^{6.509}}\) for discrete logarithm cryptography. In: Cao, Z., Zhang, F. (eds.) Pairing 2013. LNCS, vol. 8365, pp. 19–43. Springer, Heidelberg (2014)
Adleman, L.M.: The function field sieve. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 108–121. Springer, Heidelberg (1994)
Barreto, P.S.L.M., Galbraith, S.D., ÓhÉigeartaigh, C., Scott, M.: Efficient pairing computation on supersingular abelian varieties. Des. Codes Cryptography 42(3), 239–271 (2007)
Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient algorithms for pairing-based cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002)
Beuchat, J.-L., González-Díaz, J.E., Mitsunari, S., Okamoto, E., Rodríguez-Henríquez, F., Teruya, T.: High-speed software implementation of the optimal ate pairing over barreto–naehrig curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 21–39. Springer, Heidelberg (2010)
Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. In: [19], pp. 213–229
Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)
Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24(3-4), 235–265 (1997); Computational algebra and number theory, London (1993)
Chatterjee, S., Hankerson, D., Knapp, E., Menezes, A.: Comparing two pairing-based aggregate signature schemes. Des. Codes Cryptography 55(2-3), 141–167 (2010)
Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptology 23(2), 224–280 (2010)
Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Applied Mathematics 156(16), 3113–3121 (2008)
Gallant, R., Lambert, R., Vanstone, S.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: [19], pp. 190–200 (2001)
Gaudry, P., Thomé, E., Thériault, N., Diem, C.: A double large prime variation for small genus hyperelliptic index calculus. Mathematics of Computation 76, 475–492 (2004)
Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc., Secaucus (2004)
Hayashi, T., et al.: Breaking pairing-based cryptosystems usingηT pairing overGF(397). In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 43–60. Springer, Heidelberg (2012)
Hess, F., Smart, N.P., Vercauteren, F.: The eta pairing revisited. IEEE Transactions on Information Theory 52(10), 4595–4602 (2006)
Joux, A.: Discrete logarithms in GF(26168) [ = GF((2257)24)]. NMBRTHRY list (May 21, 2013),https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;49bb494e.1305
Joux, A., Pierrot, C.: The special number field sieve in\(\mathbb{F}_{p^{n}}\), application to pairing-friendly constructions. In: Cao, Z., Zhang, F. (eds.) Pairing 2013. LNCS, vol. 8365, pp. 45–61. Springer, Heidelberg (2014)
Kilian, J. (ed.): CRYPTO 2001. LNCS, vol. 2139. Springer, Heidelberg (2001)
Lee, E., Lee, H.S., Park, C.M.: Efficient and generalized pairing computation on abelian varieties. IEEE Transactions on Information Theory 55(4), 1793–1803 (2009)
Lin, X., Zhao, C., Zhang, F., Wang, Y.: Computing the ate pairing on elliptic curves with embedding degreek = 9. IEICE Transactions 91-A(9), 2387–2393 (2008)
Miller, V.S.: The Weil pairing, and its efficient calculation. J. Cryptology 17(4), 235–261 (2004)
Momose, F., Chao, J.: Scholten forms and elliptic/hyperelliptic curves with weak Weil restrictions. Cryptology ePrint Archive, Report 2005/277 (2005),http://eprint.iacr.org/2005/277
Nagao, K.: Improvement of Thériault algorithm of index calculus for Jacobian of hyperelliptic curves of small genus. Cryptology ePrint Archive, Report 2004/161 (2004),http://eprint.iacr.org/2004/161
Ogura, N., Uchiyama, S., Kanayama, N., Okamoato, E.: A note on the pairing computation using normalized Miller functions. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E95-A(1), 196–203 (2012)
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: 2000 Symposium on Cryptography and Information Security (SCIS 2000), pp. 26–28 (January 2000) C20
Scholten, J.: Weil restriction of an elliptic curve over a quadratic extension (2003) (preprint),http://www.esat.kuleuven.ac.be/~jscholte/weilres.ps
Vercauteren, F.: Optimal pairings. IEEE Transactions on Information Theory 56(1), 455–461 (2010)
Verheul, E.R.: Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 195–210. Springer, Heidelberg (2001)
Verheul, E.R.: Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. J. Cryptology 17(4), 277–296 (2004)
Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)
Zhao, C., Zhang, F., Huang, J.: A note on the ate pairing. Int. J. Inf. Sec. 7(6), 379–382 (2008)
Author information
Authors and Affiliations
Research Institute for Secure Systems, National Institute of Advanced Industrial Science and Technology, 1-1-1 Umezono, Tsukuba-shi, Ibaraki-ken, 305-8568, Japan
Tadanori Teruya
Internet Initiative Japan Inc., Jinbocho Mitsui Bldg., 1-105 Kanda Jinbo-cho, Chiyoda-ku, Tokyo, 101-0051, Japan
Kazutaka Saito
Faculty of Systems and Information Engineering, University of Tsukuba, 1-1-1, Ten-nohdai, Tsukuba-shi, Ibaraki-ken, 305-8573, Japan
Naoki Kanayama & Eiji Okamoto
NTT Secure Platform Laboratories, 3-9-11, Midori-cho, Musashino-shi, Tokyo, 180-8585, Japan
Yuto Kawahara & Tetsutaro Kobayashi
- Tadanori Teruya
Search author on:PubMed Google Scholar
- Kazutaka Saito
Search author on:PubMed Google Scholar
- Naoki Kanayama
Search author on:PubMed Google Scholar
- Yuto Kawahara
Search author on:PubMed Google Scholar
- Tetsutaro Kobayashi
Search author on:PubMed Google Scholar
- Eiji Okamoto
Search author on:PubMed Google Scholar
Editor information
Editors and Affiliations
School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, No. 800, Dongchuan Road, 200240, Shanghai, China
Zhenfu Cao
School of Information Science and Technology, Sun Yat-sen University, No. 135, Xingang Xi Road, 510275, Guangzhou, China
Fangguo Zhang
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Teruya, T., Saito, K., Kanayama, N., Kawahara, Y., Kobayashi, T., Okamoto, E. (2014). Constructing Symmetric Pairings over Supersingular Elliptic Curves with Embedding Degree Three. In: Cao, Z., Zhang, F. (eds) Pairing-Based Cryptography – Pairing 2013. Pairing 2013. Lecture Notes in Computer Science, vol 8365. Springer, Cham. https://doi.org/10.1007/978-3-319-04873-4_6
Download citation
Publisher Name:Springer, Cham
Print ISBN:978-3-319-04872-7
Online ISBN:978-3-319-04873-4
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative