Skip to main content
Top

2016 | OriginalPaper | Chapter

Deterministic Encoding into Twisted Edwards Curves

Authors : Wei Yu, Kunpeng Wang, Bao Li, Xiaoyang He, Song Tian

Published in: Information Security and Privacy

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper describes a deterministic encoding f from a finite field \(\mathbb {F}_{q}\) to a twisted Edwards curve E when \(q\equiv 2\pmod 3\). This encoding f satisfies all 3 properties of deterministic encoding in Boneh-Franklin’s identity-based scheme. We show that the construction f(h(m)) is a hash function if h(m) is a classical hash function. We present that for any nontrivial character \(\chi \) of \(E(\mathbb {F}_q)\), the character sum \(S_f(\chi )\) satisfies \( S_f(\chi )\leqslant 20\sqrt{q}+2 \). It follows that \(f(h_1(m))+f(h_2(m))\) is indifferentiable from a random oracle in the random oracle model for \(h_1\) and \(h_2\) by Farashahi, Fouque, Shparlinski, Tibouchi, and Voloch’s framework. This encoding saves 3 field inversions and 3 field multiplications compared with birational equivalence composed with Icart’s encoding; saves 2 field inversions and 2 field multiplications compared with Yu and Wang’s encoding at the cost of 2 field squarings; and saves 2 field inversions, 3 field multiplications and 3 field squarings compared with Alasha’s encoding. Practical implementations show that f is 46.1 %,35.7 %, and 38.9 % faster than the above encodings respectively.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44(170), 483–494 (1985)MathSciNetMATH Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44(170), 483–494 (1985)MathSciNetMATH
2.
go back to reference Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)CrossRef Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)CrossRef
3.
go back to reference Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003)CrossRef Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003)CrossRef
4.
go back to reference Boyen, X.: Multipurpose identity-based signcryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 383–399. Springer, Heidelberg (2003)CrossRef Boyen, X.: Multipurpose identity-based signcryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 383–399. Springer, Heidelberg (2003)CrossRef
5.
go back to reference Lindell, Y.: Highly-efficient universally-composable commitments based on the DDH assumption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 446–466. Springer, Heidelberg (2011)CrossRef Lindell, Y.: Highly-efficient universally-composable commitments based on the DDH assumption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 446–466. Springer, Heidelberg (2011)CrossRef
6.
go back to reference 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)CrossRef 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)CrossRef
7.
go back to reference Farashahi, R.R., Fouque, P.-A., Shparlinski, I.E., Tibouchi, M., Voloch, J.F.: Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Math. Comp. 82, 491–512 (2013)MathSciNetCrossRefMATH Farashahi, R.R., Fouque, P.-A., Shparlinski, I.E., Tibouchi, M., Voloch, J.F.: Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Math. Comp. 82, 491–512 (2013)MathSciNetCrossRefMATH
8.
go back to reference Shallue, A., van de Woestijne, C.E.: 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)CrossRef Shallue, A., van de Woestijne, C.E.: 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)CrossRef
10.
go back to reference Icart, T.: How to hash into elliptic curves. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 303–316. Springer, Heidelberg (2009)CrossRef Icart, T.: How to hash into elliptic curves. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 303–316. Springer, Heidelberg (2009)CrossRef
11.
go back to reference M, U.: Rational points on certain hyperelliptic curves over finite fields. Bull. Polish Acad. Sci. Math. 55, 97–104 (2007)MathSciNetCrossRef M, U.: Rational points on certain hyperelliptic curves over finite fields. Bull. Polish Acad. Sci. Math. 55, 97–104 (2007)MathSciNetCrossRef
12.
go back to reference 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)CrossRef 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)CrossRef
13.
go back to reference Farashahi, R.R.: Hashing into hessian curves. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 278–289. Springer, Heidelberg (2011)CrossRef Farashahi, R.R.: Hashing into hessian curves. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 278–289. Springer, Heidelberg (2011)CrossRef
14.
go back to reference Yu, W., Wang, K., Li, B., Tian, S.: About hash into montgomery form elliptic curves. In: Deng, R.H., Feng, T. (eds.) ISPEC 2013. LNCS, vol. 7863, pp. 147–159. Springer, Heidelberg (2013)CrossRef Yu, W., Wang, K., Li, B., Tian, S.: About hash into montgomery form elliptic curves. In: Deng, R.H., Feng, T. (eds.) ISPEC 2013. LNCS, vol. 7863, pp. 147–159. Springer, Heidelberg (2013)CrossRef
15.
go back to reference Yu, W., Wang, K., Li, B., He, X., Tian, S.: Hashing into jacobi quartic curves. In: López, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 355–375. Springer, Heidelberg (2015)CrossRef Yu, W., Wang, K., Li, B., He, X., Tian, S.: Hashing into jacobi quartic curves. In: López, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 355–375. Springer, Heidelberg (2015)CrossRef
17.
go back to reference Kocher, P.C.: Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996) Kocher, P.C.: Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
18.
go back to reference Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)CrossRef Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)CrossRef
19.
go back to reference Bernstein, D.J., Lange, T.: Inverted edwards coordinates. In: Boztaş, S., Lu, H.-F.F. (eds.) AAECC 2007. LNCS, vol. 4851, pp. 20–27. Springer, Heidelberg (2007)CrossRef Bernstein, D.J., Lange, T.: Inverted edwards coordinates. In: Boztaş, S., Lu, H.-F.F. (eds.) AAECC 2007. LNCS, vol. 4851, pp. 20–27. Springer, Heidelberg (2007)CrossRef
20.
go back to reference Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008)CrossRef Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008)CrossRef
21.
go back to reference Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008)CrossRef Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008)CrossRef
22.
go back to reference Blake, I.F., Murty, V.K., Xu, G.: Refinements of miller’s algorithm for computing the weil/tate pairing. J. Algorithms 58(2), 134–149 (2006)MathSciNetCrossRefMATH Blake, I.F., Murty, V.K., Xu, G.: Refinements of miller’s algorithm for computing the weil/tate pairing. J. Algorithms 58(2), 134–149 (2006)MathSciNetCrossRefMATH
23.
go back to reference Ionica, S., Joux, A.: Another approach to pairing computation in edwards coordinates. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 400–413. Springer, Heidelberg (2008)CrossRef Ionica, S., Joux, A.: Another approach to pairing computation in edwards coordinates. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 400–413. Springer, Heidelberg (2008)CrossRef
24.
go back to reference Arne, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster computation of the tate pairing. J. Number Theor. 131(5), 842–857 (2011)MathSciNetCrossRefMATH Arne, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster computation of the tate pairing. J. Number Theor. 131(5), 842–857 (2011)MathSciNetCrossRefMATH
25.
go back to reference Le, D., Tan, C.: Improved miller’s algorithm for computing pairings on edwards curves. IEEE Trans. Comput. 63(10), 2626–2632 (2014)MathSciNetCrossRef Le, D., Tan, C.: Improved miller’s algorithm for computing pairings on edwards curves. IEEE Trans. Comput. 63(10), 2626–2632 (2014)MathSciNetCrossRef
26.
go back to reference Yu, W., Wang, K.: How to hash into twisted edwards form elliptic curves. In: Information Security and Cryptology, Inscrypt 2010, pp. 35–43. Science press (2011) Yu, W., Wang, K.: How to hash into twisted edwards form elliptic curves. In: Information Security and Cryptology, Inscrypt 2010, pp. 35–43. Science press (2011)
28.
go back to reference 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)CrossRef 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)CrossRef
Metadata
Title
Deterministic Encoding into Twisted Edwards Curves
Authors
Wei Yu
Kunpeng Wang
Bao Li
Xiaoyang He
Song Tian
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-40367-0_18

Premium Partner