{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T01:58:41Z","timestamp":1783562321872,"version":"3.55.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T00:00:00Z","timestamp":1594684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T00:00:00Z","timestamp":1594684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2022,6]]},"abstract":"Abstract<\/jats:title>When a pairing $$e: {\\mathbb {G}}_1 \\times {\\mathbb {G}}_2 \\rightarrow {\\mathbb {G}}_{T}$$<\/jats:tex-math>\n \n e<\/mml:mi>\n :<\/mml:mo>\n \n G<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n \u00d7<\/mml:mo>\n \n G<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n \u2192<\/mml:mo>\n \n G<\/mml:mi>\n T<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, on an elliptic curve E<\/jats:italic> defined over a finite field $${\\mathbb {F}}_q$$<\/jats:tex-math>\n \n F<\/mml:mi>\n q<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, is exploited for an identity-based protocol, there is often the need to hash binary strings into $${\\mathbb {G}}_1$$<\/jats:tex-math>\n \n G<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $${\\mathbb {G}}_2$$<\/jats:tex-math>\n \n G<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Traditionally, if E<\/jats:italic> admits a twist $${\\tilde{E}}$$<\/jats:tex-math>\n \n E<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of order d<\/jats:italic>, then $${\\mathbb {G}}_1=E({\\mathbb {F}}_q) \\cap E[r]$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n =<\/mml:mo>\n E<\/mml:mi>\n \n (<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2229<\/mml:mo>\n E<\/mml:mi>\n \n [<\/mml:mo>\n r<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where r<\/jats:italic> is a prime integer, and $${\\mathbb {G}}_2={\\tilde{E}}({\\mathbb {F}}_{q^{k\/d}}) \\cap {\\tilde{E}}[r]$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n =<\/mml:mo>\n \n E<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n F<\/mml:mi>\n \n q<\/mml:mi>\n \n k<\/mml:mi>\n \/<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2229<\/mml:mo>\n \n E<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n [<\/mml:mo>\n r<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where k<\/jats:italic> is the embedding degree of E<\/jats:italic> w.r.t. r<\/jats:italic>. The standard approach for hashing into $${\\mathbb {G}}_2$$<\/jats:tex-math>\n \n G<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is to map to a general point $$P \\in {\\tilde{E}}({\\mathbb {F}}_{q^{k\/d}})$$<\/jats:tex-math>\n \n P<\/mml:mi>\n \u2208<\/mml:mo>\n \n E<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n F<\/mml:mi>\n \n q<\/mml:mi>\n \n k<\/mml:mi>\n \/<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and then multiply it by the cofactor $$c=\\#{\\tilde{E}}({\\mathbb {F}}_{q^{k\/d}})\/r$$<\/jats:tex-math>\n \n c<\/mml:mi>\n =<\/mml:mo>\n #<\/mml:mo>\n \n E<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n F<\/mml:mi>\n \n q<\/mml:mi>\n \n k<\/mml:mi>\n \/<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \/<\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Usually, the multiplication by c<\/jats:italic> is computationally expensive. In order to speed up such a computation, two different methods\u2014by Scott et al. (International conference on pairing-based cryptography. Springer, Berlin, pp 102\u2013113, 2009) and by Fuentes-Castaneda et al. (International workshop on selected areas in cryptography)\u2014have been proposed. In this paper we consider these two methods for BLS pairing-friendly curves having $$k \\in \\{12,24,30,42,48\\}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2208<\/mml:mo>\n {<\/mml:mo>\n 12<\/mml:mn>\n ,<\/mml:mo>\n 24<\/mml:mn>\n ,<\/mml:mo>\n 30<\/mml:mn>\n ,<\/mml:mo>\n 42<\/mml:mn>\n ,<\/mml:mo>\n 48<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, providing efficiency comparisons. When $$k=42,48$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 42<\/mml:mn>\n ,<\/mml:mo>\n 48<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the application of Fuentes et al. method requires expensive computations which were infeasible for the computational power at our disposal. For these cases, we propose hashing maps that we obtained following Fuentes et al. idea.<\/jats:p>","DOI":"10.1007\/s00200-020-00453-9","type":"journal-article","created":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T11:03:40Z","timestamp":1594724620000},"page":"261-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient hash maps to $${\\mathbb {G}}_2$$ on BLS curves"],"prefix":"10.1007","volume":"33","author":[{"given":"Alessandro","family":"Budroni","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Federico","family":"Pintore","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,7,14]]},"reference":[{"key":"453_CR1","unstructured":"Apache Milagro Crypto Library (AMCL): MIRACL Labs. https:\/\/github.com\/milagro-crypto\/milagro-crypto-c"},{"issue":"2","key":"453_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s001459900040","volume":"11","author":"R Balasubramanian","year":"1998","unstructured":"Balasubramanian, R., Koblitz, N.: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes\u2013Okamoto\u2013Vanstone algorithm. J. Cryptol. 11(2), 141\u2013145 (1998)","journal-title":"J. Cryptol."},{"issue":"4","key":"453_CR3","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1007\/s00145-018-9280-5","volume":"32","author":"R Barbulescu","year":"2019","unstructured":"Barbulescu, R., Duquesne, S.: Updating key size estimations for pairings. J. Cryptol. 32(4), 1298\u20131336 (2019)","journal-title":"J. Cryptol."},{"key":"453_CR4","doi-asserted-by":"crossref","unstructured":"Barbulescu, R., Gaudry, P., Kleinjung, T.: The tower number field sieve. In: Advances in Cryptology\u2014ASIACRYPT 2015, LCNS 9453, pp. 31\u201355 (2015)","DOI":"10.1007\/978-3-662-48800-3_2"},{"issue":"3","key":"453_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10623-006-9033-6","volume":"42","author":"PSLM Barreto","year":"2007","unstructured":"Barreto, P.S.L.M., Galbraith, S., \u00d3\u2019h\u00c9igeartaigh, C., Scott, M.: Efficient pairing computation on supersingular abelian varieties. Des. Codes Crypt. 42(3), 239\u2013271 (2007)","journal-title":"Des. Codes Crypt."},{"key":"453_CR6","doi-asserted-by":"crossref","unstructured":"Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In: International Conference on Security in Communication Networks. Springer, Berlin (2002)","DOI":"10.1007\/3-540-36413-7_19"},{"key":"453_CR7","doi-asserted-by":"crossref","unstructured":"Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: International Workshop on Selected Areas in Cryptography, pp. 319\u2013331. Springer, Berlin (2005)","DOI":"10.1007\/11693383_22"},{"key":"453_CR8","doi-asserted-by":"crossref","unstructured":"Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Advances in Cryptology\u2014CRYPTO 2001, pp. 213\u2013229. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44647-8_13"},{"issue":"4","key":"453_CR9","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00145-004-0314-9","volume":"17","author":"D Boneh","year":"2004","unstructured":"Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptol. 17(4), 297\u2013319 (2004)","journal-title":"J. Cryptol."},{"issue":"1","key":"453_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s10623-004-3808-4","volume":"37","author":"F Brezing","year":"2005","unstructured":"Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Crypt. 37(1), 133\u2013141 (2005)","journal-title":"Des. Codes Crypt."},{"key":"453_CR11","doi-asserted-by":"crossref","unstructured":"Brier, E., Coron, J.S., Icart, T., Madore, D., Randriam, H., Tibouchi, M.: Efficient indifferentiable hashing into ordinary elliptic curves. In: Annual Cryptology Conference, pp. 237\u2013254. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14623-7_13"},{"key":"453_CR12","doi-asserted-by":"publisher","DOI":"10.1201\/9781315370170","volume-title":"Guide to Pairing-Based Cryptography. Cryptography and Network Security","author":"N El Mrabet","year":"2017","unstructured":"El Mrabet, N., Joye, M.: Guide to Pairing-Based Cryptography. Cryptography and Network Security, 1st edn. Chapman and Hall, Boca Raton (2017)","edition":"1"},{"key":"453_CR13","doi-asserted-by":"crossref","unstructured":"Freeman, D.: Constructing pairing-friendly elliptic curves with embedding degree 10. In: Algorithmic Number Theory Symposium, pp. 452\u2013465. Springer, Berlin (2006)","DOI":"10.1007\/11792086_32"},{"issue":"2","key":"453_CR14","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00145-009-9048-z","volume":"23","author":"D Freeman","year":"2010","unstructured":"Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23(2), 224\u2013280 (2010)","journal-title":"J. Cryptol."},{"issue":"206","key":"453_CR15","first-page":"865","volume":"62","author":"G Frey","year":"1994","unstructured":"Frey, G., R\u00fcck, H.G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 62(206), 865\u2013874 (1994)","journal-title":"Math. Comput."},{"key":"453_CR16","unstructured":"Fuentes-Castaneda, L., Knapp, E., Rodriguez-Henriquez, F.: Faster hashing to $${\\mathbb{G}}_2$$. In: Selected Areas in Cryptography - 18th International Workshop, SAC 2011,\u00a0Toronto, ON, Canada, August 2011, Revised Selected Papers, pp. 412\u2013430 (2011)"},{"key":"453_CR17","doi-asserted-by":"crossref","unstructured":"Galbraith, S.D., Scott, M.: Exponentiation in pairing-friendly groups using homomorphisms. In: International Conference on Pairing-Based Cryptography, pp. 211\u2013224. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-85538-5_15"},{"key":"453_CR18","doi-asserted-by":"crossref","unstructured":"Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Annual International Cryptology Conference, pp. 190\u2013200. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44647-8_11"},{"key":"453_CR19","doi-asserted-by":"crossref","unstructured":"Hess, F.: Pairing lattices. In: International Conference on Pairing-Based Cryptography, pp. 18\u201338. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-85538-5_2"},{"issue":"10","key":"453_CR20","doi-asserted-by":"publisher","first-page":"4595","DOI":"10.1109\/TIT.2006.881709","volume":"52","author":"F Hess","year":"2006","unstructured":"Hess, F., Smart, N., Vercauteren, F.: The eta pairing revisited. IEEE Trans. Inf. Theory 52(10), 4595\u20134602 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"453_CR21","doi-asserted-by":"crossref","unstructured":"Joux, A.: A one round protocol for tripartite Diffie\u2013Hellman. In: International Algorithmic Number Theory Symposium, pp. 385\u2013393. Springer, Berlin (2000)","DOI":"10.1007\/10722028_23"},{"key":"453_CR22","doi-asserted-by":"crossref","unstructured":"Kachisa, E.J., Schaefer, E.F., Scott, M.: Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field. In: International Conference on Pairing-Based Cryptography, pp. 126\u2013135. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-85538-5_9"},{"key":"453_CR23","doi-asserted-by":"crossref","unstructured":"Kim, T., Barbulescu, R.: Extended tower number field sieve: a new complexity for medium prime case. In: Annual Cryptology Conference, LCNS 9814, pp. 543\u2013571. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53018-4_20"},{"key":"453_CR24","doi-asserted-by":"crossref","unstructured":"Kim, T., Jeong, J.: Extended tower number field sieve with application to finite fields of arbitrary composite extension degree. In: IACR International Workshop on Public Key Cryptography, pp. 388\u2013408. Springer, Berlin (2017)","DOI":"10.1007\/978-3-662-54365-8_16"},{"issue":"4","key":"453_CR25","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"issue":"3","key":"453_CR26","first-page":"1041","volume":"48","author":"F Luca","year":"2004","unstructured":"Luca, F., Mireles, D.J., Shparlinski, I.E.: MOV attack in various subgroups on elliptic curves. Ill. J. Math. 48(3), 1041\u20131052 (2004)","journal-title":"Ill. J. Math."},{"key":"453_CR27","doi-asserted-by":"crossref","unstructured":"Menezes, A., Sarkar, P., Singh, S.: Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography. In: Proceedings of Mycrypt (2016)","DOI":"10.1007\/978-3-319-61273-7_5"},{"issue":"5","key":"453_CR28","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1109\/18.259647","volume":"39","author":"A Menezes","year":"1993","unstructured":"Menezes, A., Vanstone, S., Okamoto, T.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39(5), 1639\u20131646 (1993)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"453_CR29","first-page":"1234","volume":"84","author":"A Miyaji","year":"2001","unstructured":"Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 84(5), 1234\u20131243 (2001)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"453_CR30","doi-asserted-by":"crossref","unstructured":"Paulus, S.: Lattice basis reduction in function fields. In: International Algorithmic Number Theory Symposium. Springer, Berlin (1998)","DOI":"10.1007\/BFb0054893"},{"issue":"269","key":"453_CR31","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1090\/S0025-5718-09-02266-2","volume":"79","author":"K Rubin","year":"2010","unstructured":"Rubin, K., Silverberg, A.: Choosing the correct elliptic curve in the CM method. Math. Comput. 79(269), 545\u2013561 (2010)","journal-title":"Math. Comput."},{"key":"453_CR32","unstructured":"Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: Symposium on Cryptography and Information Security. SCIS, Okinawa, Japan (2000)"},{"key":"453_CR33","doi-asserted-by":"crossref","unstructured":"Scott, M., Benger, N., Charlemagne, M., Perez, L.J.D., Kachisa, E.J.: Fast hashing to G2 on pairing friendly Curves. In: International Conference on Pairing-Based Cryptography, pp. 102\u2013113. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-03298-1_8"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-020-00453-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-020-00453-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-020-00453-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T12:17:20Z","timestamp":1652789840000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-020-00453-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,14]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["453"],"URL":"https:\/\/doi.org\/10.1007\/s00200-020-00453-9","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,14]]},"assertion":[{"value":"4 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}