×

Hashing into Hessian curves. (English) Zbl 1280.94050

Nitaj, Abderrahmane (ed.) et al., Progress in cryptology – AFRICACRYPT 2011. 4th international conference on cryptology in Africa, Dakar, Senegal, July 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21968-9/pbk). Lecture Notes in Computer Science 6737, 278-289 (2011).
Summary: We describe a hashing function from the elements of the finite field \(\mathbb{F}_q\) into points on a Hessian curve. Our function features the uniform and smaller size for the cardinalities of almost all fibers compared with the other known hashing functions for elliptic curves. For ordinary Hessian curves, this function is \(2 : 1\) for almost all points. More precisely, for odd \(q\), the cardinality of the image set of the function is exactly given by \((q + i + 2)/2\) for some \(i = -1, \, 1\).
Next, we present an injective hashing function from the elements of \(\mathbb Z_{m }\) into points on a Hessian curve over \(\mathbb{F}_q\) with odd \(q\) and \(m = (q + i)/2\) for some \(i = -1, \, 1, \, 3\).
For the entire collection see [Zbl 1216.94004].

MSC:

94A60 Cryptography
14G50 Applications to coding theory and cryptography of arithmetic geometry
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Software:

EFD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boneh, D., Franklin, M.K.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001) · Zbl 1002.94023 · doi:10.1007/3-540-44647-8_13
[2] Bernstein, D.J., Lange, T.: Explicit-formulas database, http://www.hyperelliptic.org/EFD/
[3] Boyko, V., MacKenzie, P.D., Patel, S.: Provably secure password-authenticated key exchange using diffie-hellman. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 156–171. Springer, Heidelberg (2000) · Zbl 1082.94535 · doi:10.1007/3-540-45539-6_12
[4] Brier, E., Coron, J.-S., Icart, T., Madore, D., Randriam, H., Tibouchi, M.: Efficient indifferentiable hashing into ordinary elliptic curves. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 237–254. Springer, Heidelberg (2010) · Zbl 1261.94025 · doi:10.1007/978-3-642-14623-7_13
[5] Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Advances in Applied Mathematics 7(4), 385–434 (1986) · Zbl 0614.10004 · doi:10.1016/0196-8858(86)90023-0
[6] Dalen, K.: On a theorem of Stickelberger. Math. Scand. 3, 124–126 (1955) · Zbl 0068.03102 · doi:10.7146/math.scand.a-10433
[7] Farashahi, R.R., Fouque, P.-A., Shparlinski, I., Tibouchi, M., Voloch, F.: Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Cryptology ePrint Archive, Report 2010/539 (2010), http://eprint.iacr.org/2010/539 · Zbl 1312.94048
[8] Farashahi, R.R., Joye, M.: Efficient Arithmetic on Hessian Curves. In: Nguyen, P., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 243–260. Springer, Heidelberg (2010) · Zbl 1279.94072 · doi:10.1007/978-3-642-13013-7_15
[9] Farashahi, R.R., Shparlinski, I., Voloch, F.: On hashing into elliptic curves. J. Math. Cryptology 3, 353–360 (2009) · Zbl 1200.94043 · doi:10.1515/JMC.2009.022
[10] Fouque, P.-A., Tibouchi, M.: Estimating the size of the image of deterministic hash functions to elliptic curves. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 81–91. Springer, Heidelberg (2010) · Zbl 1285.94060 · doi:10.1007/978-3-642-14712-8_5
[11] Fouque, P.-A., Tibouchi, M.: Deterministic encoding and hashing to odd hyperelliptic curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 265–277. Springer, Heidelberg (2010) · Zbl 1290.94073 · doi:10.1007/978-3-642-17455-1_17
[12] Hesse, O.: Über die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln. Journal Für Die Reine und Angewandte Mathematik 10, 68–96 (1844) · ERAM 028.0817cj · doi:10.1515/crll.1844.28.68
[13] Hisil, H., Carter, G., Dawson, E.: New formulæ for efficient elliptic curve arithmetic. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 138–151. Springer, Heidelberg (2007) · Zbl 1153.94390 · doi:10.1007/978-3-540-77026-8_11
[14] Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Faster group operations on elliptic curves. In: Brankovic, L., Susilo, W. (eds.) AISC 2009, vol. 98, pp. 7–19 (2009)
[15] Icart, T.: How to hash into elliptic curves. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 303–316. Springer, Heidelberg (2009) · Zbl 1252.94075 · doi:10.1007/978-3-642-03356-8_18
[16] Jablon, D.P.: Strong password-only authenticated key exchange. SIGCOMM Comput. Commun. Rev. 26(5), 5–26 (1996) · doi:10.1145/242896.242897
[17] Joye, M., Quisquater, J.-J.: Hessian elliptic curves and side-channel attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 402–410. Springer, Heidelberg (2001) · Zbl 1012.94547 · doi:10.1007/3-540-44709-1_33
[18] Kammerer, J.-G., Lercier, R., Renault, G.: Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 278–297. Springer, Heidelberg (2010) · Zbl 1290.94100 · doi:10.1007/978-3-642-17455-1_18
[19] Lidl, R., Niederreiter, H.: Finite fields. Cambridge University Press, Cambridge (1997) · Zbl 1139.11053
[20] Shallue, A., van de Woestijne, C.: Construction of rational points on elliptic curves over finite fields. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 510–524. Springer, Heidelberg (2006) · Zbl 1143.11331 · doi:10.1007/11792086_36
[21] Smart, N.P.: The hessian form of an elliptic curve. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 118–125. Springer, Heidelberg (2001) · Zbl 1021.94522 · doi:10.1007/3-540-44709-1_11
[22] Stickelberger, L.: Über eine neue Eigenschaft der Diskriminanten algebraischer Zahlkörper. In: Verh. 1 Internat. Math. Kongresses, Zürich, Leipzig, pp. 182–193 (1897) · JFM 29.0172.03
[23] Swan, R.G.: Factorization of Polynomials over Finite Fields. Pac. J. Math. 19, 1099–1106 (1962) · Zbl 0113.01701 · doi:10.2140/pjm.1962.12.1099
[24] Ulas, M.: Rational points on certain hyperelliptic curves over finite fields. Bull. Polish Acad. Sci. Math. 55(2), 97–104 (2007) · Zbl 1131.11039 · doi:10.4064/ba55-2-1
[25] Vishne, U.: Factorization of Trinomials over Galois Fields of Characteristic 2. Finite Fields and Their Applications 3, 370–377 (1997) · Zbl 0922.11101 · doi:10.1006/ffta.1997.0191
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.