[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Uniform encodings to elliptic curves and indistinguishable point representation

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Many cryptographic protocols which are based on elliptic curves require to efficiently encode bit-strings into the points of a given elliptic curve such that the encoding function satisfies computability, regularity, and samplability, or generally admissibility. All the admissible encoding functions from the finite field \(\mathbb {F}_q\) are restricted to the class of elliptic curves with a non-trivial l-torsion \(\mathbb {F}_q\)-rational point, where \(l\in \{2,3\}\). Therefore, there is no admissible encoding function to the class of many cryptographically interesting elliptic curves of prime order. In this paper, we present an admissible 2:1 encoding function from the set \(\{0,1,\ldots , \frac{q-1}{2}\}\) to the \(\mathbb {F}_q\)-rational points of arbitrary elliptic curves. We also propose an injective encoding function to elliptic curves with a non-trivial \(\mathbb {F}_q\)-rational point of order two, that acts the same as the Bernstein et al.’s injective encoding function. Conversely, occasionally we have to transmit points of a known curve through an insecure channel. Traditional methods for transferring points enable an adversary to recognize patterns in the transmitted data. Consequently, one finds valuable information to attack the cryptosystem using the network traffic. By the help of the inverse of the injective encoding functions, Bernstein et al. introduced an interesting solution to this problem, namely Elligator. In this paper, we present an indistinguishable elliptic curve point representation using our given encoding function, which unlike the previous well-known encoding functions is not injective but covers almost all of elliptic curves over odd characteristic finite fields. Indeed, since we proposed a 2:1 encoding function to elliptic curves in short Weierstrass form, we have to select one pre-image randomly and transmit its corresponding bit-string instead of the point.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

Notes

  1. \(\#\mathcal {W}\) is at most a positive constant multiple of l

  2. Since we want to embed the function \(\sigma \) to Algorithm 3, everywhere that \(Cx+D=0\) we send the input to \({\mathcal {O}}\).

References

  1. Aranha, D.F., Fouque, P.-A., Qian, C., Tibouchi, M., Zapalowicz, J.-C.: Binary elligator squared. In: Selected Areas in Cryptography, SAC 2014, LNCS, pp. 20–37, Springer.

  2. Avanzi R., Cohen H., Doche C., Frey G., Lange T., Nguyen K., Vercauteren F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005).

    MATH  Google Scholar 

  3. Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: Elliptic-curve points indistinguishable from uniform random strings. In: Sadeghi A.R., Gligor V.D., Yung M. (eds.) ACM Conference on Computer and Communications Security. pp. 967–980. ACM (2013).

  4. Bernstein, D.J., Lange, T., Martindale, C., Panny, L.: Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. Ishai, Y. et al. (ed.) Advances in cryptology–EUROCRYPT 2019. In: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, LNCS, vol. 11477, pp. 409–441 (2019).

  5. Boneh, D., Franklin, K.: Identity-based encryption from the weil pairing. In: CRYPTO 2001, LNCS, vol. 2139, pp. 213–229 Springer (2001).

  6. Boneh, D., Lynn, B., Shacham, H.: Short signature from Weil pairing. In: ASIACRYPT 2001, LNCS, vol. 2248, pp. 514–532, Springer (2001).

  7. Boyko, V., MacKenzie, P.D., Patel, S.: Provably secure password-authenticated key exchange using Diffie–Hellman. In: EUROCRYPT 2000, LNCS, vol. 1807, pp. 156–171, Springer (2000).

  8. Brier, E., Coro,n 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).

  9. Castryck, W., Lang,e T., Martindale, C., Panny, L., Renes, J.: CSIDH: An efficient post-quantum commutative group action. In: Peyrin T., Galbraith S.D. (eds.) Advances in Cryptology-ASIACRYPT 2018, LNCS, pp. 395–427. Springer International Publishing, (2018).

  10. Coron, J., Dodis, Y., Malinaud, C., Puniya, P.: How to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005, LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005).

  11. Fadavi, M., Farashahi, R.R., Sabbaghian S.: Injective Encodings to Binary Ordinary Elliptic Curves. In: Cid, C., Jacobson, Jr. M. (eds.) Selected Areas in Cryptography, SAC 2018, LNCS, vol. 11349, pp. 434–449, Springer.

  12. Farashahi, R.R.: Hashing into hessian curves, In: Nitaj, A., Pointcheval, D. (eds). AFRICACRYPT 2011, LNCS, vol. 6737, pp. 278–289. Springer (2011).

  13. Farashahi R.R., Fouque P.-A., Shparlinski I., Tibouchi M., Voloch F.: Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Math. Comput. 82, 491–512 (2013).

    Article  MathSciNet  Google Scholar 

  14. Fouque, P.-A., Joux, A., Tibouchi, M.: Injective encodings to elliptic curves. In: ACISP 2013, LNCS, vol. 7959, pp. 203–218, Springer (2013).

  15. Icart, T.: How to hash into elliptic curves. In: CRPYTO 2009, LNCS, vol. 5677, pp. 303–316, Springer (2009).

  16. Jablon D.P.: Strong password-only authenticated key exchange. SIGCOMM Comput. Commun. 26(5), 5–26 (1996).

    Article  Google Scholar 

  17. Joye, M., Tibouchi, M., Vergnaud, D.: Huff’s model for elliptic curves. In: Hanrot, G., Morain, F., Thomé, E. (eds.) Algorithmic Number Theory (ANTS-IX). LNCS, vol. 6197, pp. 234–250. Springer (2010).

  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, vol. 6487 LNCS, pp. 278–297. Springer (2010).

  19. Maurer, U.M., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC, LNCS, vol. 2951, pp 21–39, Springer (2004).

  20. Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field, IEEE, pp. 1639–1647, (1993).

  21. Schoof R.: Elliptic curves over finite fields and the computation of square roots mod p. Math. Comput. 44(170), 483–494 (1985).

    MathSciNet  MATH  Google Scholar 

  22. 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).

  23. Silverman J.H.: The Arithmetic of Elliptic Curves. Springer, Berlin (1995).

    Google Scholar 

  24. Skalba M.: Points on elliptic curves over finite fields. Acta Arithmat. 117(3), 293–301 (2005).

    Article  MathSciNet  Google Scholar 

  25. Tibouchi, M.: Elligator squared: uniform points on elliptic curves of prime order as uniform random strings. In: Christin, N., Safavi-Naini, R. (eds.) Financial Cryptography 2014, LNCS, vol. 8437, pp. 139–156. Springer, Berlin (2014).

  26. Tibouchi M., Kim T.: Improved elliptic curve hashing and point representation. Des. Codes Cryptogr. 82, 161–177 (2017).

    Article  MathSciNet  Google Scholar 

  27. Ulas M.: Rational points on certain hyperelliptic curves over finite fields. Bull. Polish Acad. Sci. Math. 55(2), 97–104 (2007).

    Article  MathSciNet  Google Scholar 

  28. Washington L.C.: Elliptic Curves: Number Theory and Cryptography. CRC Press, Boca Raton (2008).

    Book  Google Scholar 

Download references

Acknowledgements

The authors thank Anonymous reviewers for their useful comments to the manuscript. This research was in part supported by a grant from IPM (No. 99110425).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Reza Rezaeian Farashahi.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Codes, Cryptology and Curves”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fadavi, M., Rezaeian Farashahi, R. Uniform encodings to elliptic curves and indistinguishable point representation. Des. Codes Cryptogr. 88, 1479–1502 (2020). https://doi.org/10.1007/s10623-020-00753-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-020-00753-8

Keywords

Mathematics Subject Classification

Navigation