Tower Building Technique on Elliptic Curve with Embedding Degree 18

Assoujaa, Ismail; Ezzouak, Siham; Mouanis, Hakima

doi:10.2478/tmmp-2023-0008

Abstract

Pairing based cryptography is one of the best security solution that devote a lot of attention. So, to make pairing practical, secure and computationally effcient, we choose to work with extension finite field of the form 𝔽_p^k with k ≥ 12. In this paper, we focus on the case of curves with embedding degree 18. We use the tower building technique, and study the case of degree 2 or 3 twist to carry out most arithmetics operations in 𝔽_p² , 𝔽_p³, 𝔽_p⁶, 𝔽_p⁹ and 𝔽_p¹⁸, thus we speed up the computation in optimal ate pairing.

References

[1] MILLER, V. S.: Use of elliptic curves in cryptography, In: Advances in Cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985), Lecture Notes in Comput. Sci. Vol. 218, Springer, Berlin, 1986. pp. 417–426.10.1007/3-540-39799-X_31
Search in Google Scholar Back to article
[2] KOBLITZ, N.: Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209.
Search in Google Scholar Back to article
[3] RIVEST, R. L.—SHAMIR, A.—ADLEMAN, L. M.: A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM, 21 (1978), no. 2, 120–126.10.21236/ADA606588
Search in Google Scholar Back to article
[4] WHELAN, C.—SCOTT, M.: The Importance of the Final Exponentiation in Pairings When Considering Fault Attacks. In: (T. Takagi, T.Okamoto, E. Okamoto, eds.) Pairing 2007. Lecture Notes in Comput. Sci. Vol. 4575, 2007, pp. 225–246.
Search in Google Scholar Back to article
[5] EL MRABET, N.—GUILLERMIN, N.—IONICA, S.: A study of pairing computation for curves with embedding degree 15, DBLP Vol. 2009.
Search in Google Scholar Back to article
[6] EL MRABET, N.—MARC JOYE, M.: Guide to Pairing-Based Cryptography. Cryptography and Network Security, Chapman and Hall/CRC Press, 2017.10.1201/9781315370170
Search in Google Scholar Back to article
[7] FOUOTSA, E.—EL MRABET, N.—PECHA, A.: Optimal Ate pairing on elliptic curves with embedding degree 9; 15 and 27, J. Groups Complex. Cryptol. 12 (2020), no. 1, Paper no. 3, 25 p.
Search in Google Scholar Back to article
[8] MBIANG, N. B.—DE FREITAS ARANHA, D.—FOUOTSA, E.: Computing the optimal ate pairing over elliptic curves with embedding degrees 54 and 48 at the 256-bit security level, Int. J. Appl. Cryptography, 4, (2020) no. 1, 45–59.
Search in Google Scholar Back to article
[9] KHANDAKER, M. A.-A—PARK, T.—NOGAMI, Y.—KIM, H.: A Comparative sdudy of Twist property in KSS curves of embedding degree 16 and 18 from the implementation perspective, J. Inf. Commun. Convergence Engnr. 15 (2017), no. (2), 97–103.
Search in Google Scholar Back to article
[10] KHANDAKER, M. A.-A—NOGAMI, Y.: Isomorphic mapping for ate-based pairing over KSS curve of embedding degree 18. In: Fourth International Symposium on Computing and Networking (CANDAR). IEEE, 2016, pp. 629–634, DOI: 10.1109/CANDAR.2016.0113.10.1109/CANDAR.2016.0113
Search in Google Scholar Back to article
[11] AFREEN, R.—MEHROTRA, S. C.: A review on elliptic curve cryptography for embedded systems, Int. J. Comput. Sci. & Information Technology (IJCSIT), 3, (2011) no. 3, arXiv preprint arXiv:1107.3631.
Search in Google Scholar Back to article
[12] KHANDAKER, M. A.-A—NOGAMI, Y.: A consideration of towering scheme for effcient arithmetic operation over extension field of degree 18. In: 19th International Conference on Computer and Information Technology, (ICCIT), Dhaka, Bangladesh, December 18– 20, 2016, North South University, Dhaka, Bangladesh, 2016, pp. 276–281, DOI: 10.1109/ ICCITECHN.2016.7860209.10.1109/ICCITECHN.2016.7860209
Search in Google Scholar Back to article
[13] EL MRABET, N.—GUILLEVIC, A.—IONICA, S.: Effcient multiplication in finite field extensions of degree 5, In: Progress in Cryptology—AFRICACRYPT 2011, Lecture Notes in Comput. Sci., Vol. 6737, Springer, Heidelberg, 2011, pp. 188–205. DBLP 10.1007/ 978-3-642-21969-6-1210.1007/978-3-642-21969-6_12
Search in Google Scholar Back to article
[14] SCOTT, M.—GUILLEVIC, A.: A new family of pairing-friendly elliptic curves, In: 7th International Workshop, WAIFI 2018, Bergen, Norway, June 14–16, 2018. Revised selected papers. (Lilya Budaghyan, ed. et al.) Arithmetic of finite fields. Lect. Notes Comput. Sci. Vol. 11321, Cham: Springer, 2018, pp. 43–57.
Search in Google Scholar Back to article
[15] SCOTT, M.: On the effcient implementation of pairing-based protocols, In: Cryptography and Coding, Springer-Verlag, Berlin, 2011. pp. 296–308,10.1007/978-3-642-25516-8_18
Search in Google Scholar Back to article
[16] SILVERMAN, J. H.: The Arithmetic of Elliptic Curves. 2nd ed. Graduate Texts in Mathematics Vol. 106, Springer, New York, 2009.10.1007/978-0-387-09494-6
Search in Google Scholar Back to article
[17] KACHISA, E. J.—SCHAEFER, E. F. —SCOTT, M.: Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field. In: Pairing-Based Cryptography–Pairing 2008: Second International Conference, Egham, UK, September 1–3, 2008. Proceedings 2. Springer-Verlag Berlin Heidelberg. pp. 126–135.10.1007/978-3-540-85538-5_9
Search in Google Scholar Back to article
[18] DEVEGILI, A. J.— Ó’HÉIGEARTAIGH, C.—SCOTT, M.—DAHAB, R.: Multiplication and squaring on pairing-friendly fields, ePrint, 471, 2006.
Search in Google Scholar Back to article
[19] BARBULESCU, R.—DUQUESNE, S.: Updating key size estimations for pairings, J. Cryptol. 32 (2019), 1298–1336.10.1007/s00145-018-9280-5
Search in Google Scholar Back to article

Tower Building Technique on Elliptic Curve with Embedding Degree 18

Abstract

Paradigm

My account