×

zbMATH — the first resource for mathematics

Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. (English) Zbl 1312.94048
Summary: At Crypto 2010 [Lect. Notes Comput. Sci. 6223, 237–254 (2010; Zbl 1261.94025], E. Brier et al. proposed the first construction of a hash function into ordinary elliptic curves that was indifferentiable from a random oracle, based on T. Icart’s deterministic encoding from Crypto 2009 [Lect. Notes Comput. Sci. 5677, 303–316 (2009; Zbl 1252.94075)]. Such a hash function can be plugged into essentially any cryptosystem that requires hashing into elliptic curves, while not compromising proofs of security in the random oracle model. However, the proof relied on relatively involved tools from algebraic geometry, and only applied to Icart’s deterministic encoding from Crypto 2009. In this paper, we present a new, simpler technique based on bounds of character sums to prove the indifferentiability of similar hash function constructions based on any of the known deterministic encodings to elliptic curves or curves of higher genus, such as the algorithms by Shallue, van de Woestijne and Ulas, or the Icart-like encodings recently presented by Kammerer, Lercier and Renault. In particular, we get the first constructions of well-behaved hash functions to Jacobians of hyperelliptic curves. Our technique also provides more precise estimates on the statistical behavior of those deterministic encodings and the hash function constructions based on them. Additionally, we can derive pseudorandomness results for partial bit patterns of such encodings.

MSC:
94A60 Cryptography
14G50 Applications to coding theory and cryptography of arithmetic geometry
11T23 Exponential sums
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] [DBLP:conf/pkc/BaekZ04] J. Baek and Y. Zheng. \newblock Identity-based threshold decryption. \newblock In F. Bao, R. H. Deng, and J. Zhou, editors. PKC 2004, volume 2947 of Lecture Notes in Computer Science, pages 262-276. Springer, 2004. · Zbl 1198.94079
[2] [DBLP:conf/sacrypt/BarretoN05] P. S. L. M. Barreto and M. Naehrig. \newblock Pairing-friendly elliptic curves of prime order. \newblock In B. Preneel and S. E. Tavares, editors, Selected Areas in Cryptography, volume 3897 of Lecture Notes in Computer Science, pages 319-331. Springer, 2005. · Zbl 1151.94479
[3] [DBLP:conf/pkc/Boldyreva03] A. Boldyreva. \newblock Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. \newblock In Y. Desmedt, editor, PKC 2003, volume 2567 of Lecture Notes in Computer Science, pages 31-46. Springer, 2002. · Zbl 1033.94552
[4] [Bomb] E. Bombieri. \newblock On exponential sums in finite fields. \newblock In Les Tendances G\'eom. en Alg\`“ebre et Th\'”eorie des Nombres, pages 37-41. \'Editions du Centre National de la Recherche Scientifique, Paris, 1966.
[5] [DBLP:conf/crypto/BonehF01] D. Boneh and M. K. Franklin. \newblock Identity-based encryption from the Weil pairing. \newblock In J. Kilian, editor, CRYPTO, volume 2139 of Lecture Notes in Computer Science, pages 213-229. Springer, 2001. · Zbl 1002.94023
[6] [DBLP:conf/eurocrypt/BonehGLS03] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. \newblock Aggregate and verifiably encrypted signatures from bilinear maps. \newblock In E. Biham, editor, EUROCRYPT, volume 2656 of Lecture Notes in Computer Science, pages 416-432. Springer, 2003 · Zbl 1038.94553
[7] [DBLP:conf/asiacrypt/BonehLS01] D. Boneh, B. Lynn, and H. Shacham. \newblock Short signatures from the Weil pairing. \newblock In C. Boyd, editor, ASIACRYPT, volume 2248 of Lecture Notes in Computer Science, pages 514-532. Springer, 2001. · Zbl 1064.94554
[8] [DBLP:conf/acisp/BoydMN01] C. Boyd, P. Montague and K.Q. Nguyen. \newblock Elliptic Curve Based Password Authenticated Key Exchange Protocols. \newblock In ACISP 2001, volume 2119 of Lecture Notes in Computer Science, pages 487-501. Springer, 2001. · Zbl 1007.94542
[9] [DBLP:conf/crypto/Boyen03] X. Boyen. \newblock Multipurpose identity-based signcryption (a swiss army knife for identity-based cryptography). \newblock In D. Boneh, editor, CRYPTO, volume 2729 of Lecture Notes in Computer Science, pages 383-399. Springer, 2003. · Zbl 1122.94356
[10] [brier] E. Brier, J.-S. Coron, T. Icart, D. Madore, H. Randriam, and M. Tibouchi. \newblock Efficient indifferentiable hashing into ordinary elliptic curves. \newblock In T. Rabin, editor, CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 237-254. Springer, 2010. · Zbl 1261.94025
[11] [DBLP:conf/pkc/ChaC03] J. C. Cha and J. H. Cheon. \newblock An identity-based signature from gap Diffie-Hellman groups. \newblock Y. Desmedt, editor. PKC 2003, volume 2567 of Lecture Notes in Computer Science, pages 18-30. Springer, 2002. · Zbl 1033.94554
[12] [DBLP:journals/ieeesp/ChabanneT11] H. Chabanne and M. Tibouchi. \newblock Securing e-passports with elliptic curves. \newblockIEEE Security & Privacy, 9(2):75-78, 2011.
[13] [cryptoeprint:2011:033] J.-M. Couveignes and J.-G. Kammerer. \newblock The geometry of flex tangents to a cubic curve and its parameterizations. \newblockCryptology ePrint Archive, Report 2011/033, 2011. \newblock\urlhttp://eprint.iacr.org/.
[14] [DrTi] M. Drmota and R. Tichy. \newblock Sequences, discrepancies and applications. \newblock Springer-Verlag, Berlin, 1997. · Zbl 0877.11043
[15] [Fa] R. R. Farashahi. \newblock Hashing into Hessian curves. \newblock In A. Nitaj and D. Pointcheval, editors, AFRICACRYPT, volume 6737 of Lecture Notes in Computer Science, pages 278-289. Springer, 2011. · Zbl 1280.94050
[16] [shparlinski-voloch] R. R. Farashahi, I. E. Shparlinski and J. F. Voloch. \newblock On hashing into elliptic curves. \newblockJ. Math. Cryptology, 3(4):353-360, 2009. · Zbl 1200.94043
[17] [DBLP:conf/pairing/FouqueT10] P.-A. Fouque and M. Tibouchi. \newblock Deterministic encoding and hashing to odd hyperelliptic curves. \newblock In M. Joye, A. Miyaji and A. Otsuka, editors, Pairing 2010, volume 6487 of Lecture Notes in Computer Science, pages 265-277. Springer, 2010. · Zbl 1290.94073
[18] [fouque-tibouchi] P.-A. Fouque and M. Tibouchi. \newblock Estimating the size of the image of deterministic hash functions to elliptic curves. \newblock In M. Abdalla and P. Baretto, editors, LATINCRYPT, volume 6212 of Lecture Notes in Computer Science, pages 81-91. Springer, 2010. · Zbl 1285.94060
[19] [DBLP:conf/asiacrypt/GentryS02] C. Gentry and A. Silverberg. \newblock Hierarchical ID-based cryptography. \newblock In Y. Zheng, editor. Advances in Cryptology - ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 548-566. Springer, 2002. · Zbl 1065.94547
[20] [DBLP:conf/eurocrypt/HorwitzL02] J. Horwitz and B. Lynn. \newblock Toward hierarchical identity-based encryption. \newblock In L. R. Knudsen, editor, EUROCRYPT, volume 2332 of Lecture Notes in Computer Science, pages 466-481. Springer, 2002. · Zbl 1056.94514
[21] [icart] T. Icart. \newblock How to hash into elliptic curves. \newblock In S. Halevi, editor, CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 303-316. Springer, 2009. · Zbl 1252.94075
[22] [IwKow] H. Iwaniec and E. Kowalski. \newblockAnalytic number theory. \newblock Amer. Math. Soc., Providence, RI, 2004.
[23] [KLR] J.-G. Kammerer, R. Lercier, and G. Renault. \newblock Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time. \newblock In M. Joye, A. Miyaji and A. Otsuka, editors, Pairing 2010, volume 6487 of Lecture Notes in Computer Science, pages 278-297. Springer, 2010. · Zbl 1290.94100
[24] [DBLP:conf/ants/KohelS00] D. R. Kohel and I. Shparlinski. \newblock On exponential sums and group generators for elliptic curves over finite fields. \newblock In W. Bosma, editor, ANTS, volume 1838 of Lecture Notes in Computer Science, pages 395-404. Springer, 2000.
[25] [DBLP:conf/pkc/LibertQ04] B. Libert and J.-J. Quisquater. \newblock Efficient signcryption with key privacy from gap Diffie-Hellman groups. \newblock In F. Bao, R. H. Deng, and J. Zhou, editors. PKC 2004, volume 2947 of Lecture Notes in Computer Science, pages 187-200. Springer, 2004. · Zbl 1198.94106
[26] [LN] R. Lidl and H. Niederreiter. \newblockFinite fields. \newblock Cambridge Univ. Press, Cambridge, 1997.
[27] [DBLP:conf/tcc/MaurerRH04] U. M. Maurer, R. Renner, and C. Holenstein. \newblock Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. \newblock In M. Naor, editor, TCC, volume 2951 of Lecture Notes in Computer Science, pages 21-39. Springer, 2004. · Zbl 1197.94196
[28] [DBLP:conf/eurocrypt/RistenpartSS11] T. Ristenpart, H. Shacham, and T. Shrimpton. \newblock Careful with composition: Limitations of the indifferentiability framework. \newblock In K. G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 487-506. Springer, 2011. · Zbl 1290.94155
[29] [rosen] M. Rosen. \newblockNumber Theory in Function Fields, volume 210 of Graduate Texts in Mathematics. \newblock Springer, 2002. · Zbl 1043.11079
[30] [ANTS06] A. Shallue and C. van de Woestijne. \newblock Construction of rational points on elliptic curves over finite fields. \newblock In F. Hess, S. Pauli, and M. E. Pohst, editors, ANTS, volume 4076 of Lecture Notes in Computer Science, pages 510-524. Springer, 2006. · Zbl 1143.11331
[31] [Skalba] M. Ska\lba. \newblock Points on elliptic curves over finite fields. \newblockActa Arith., 117(3):293-301, 2005. · Zbl 1078.11044
[32] [ulas-2007] M. Ulas. \newblock Rational points on certain hyperelliptic curves over finite fields. \newblockBull. Polish Acad. Sci. Math., 55(2):97-104, 2007. · Zbl 1131.11039
[33] [Weil] A. Weil. \newblockBasic number theory. \newblock Classics in Mathematics. Springer-Verlag, Berlin, 1995.
[34] [DBLP:conf/asiacrypt/ZhangK02] F. Zhang and K. Kim. \newblock ID-based blind signature and ring signature from pairings. \newblock In Y. Zheng, editor. Advances in Cryptology - ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 533-547. Springer, 2002. · Zbl 1065.94566
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.