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.
Similar content being viewed by others
Notes
\(\#\mathcal {W}\) is at most a positive constant multiple of l
Since we want to embed the function \(\sigma \) to Algorithm 3, everywhere that \(Cx+D=0\) we send the input to \({\mathcal {O}}\).
References
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.
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).
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).
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).
Boneh, D., Franklin, K.: Identity-based encryption from the weil pairing. In: CRYPTO 2001, LNCS, vol. 2139, pp. 213–229 Springer (2001).
Boneh, D., Lynn, B., Shacham, H.: Short signature from Weil pairing. In: ASIACRYPT 2001, LNCS, vol. 2248, pp. 514–532, Springer (2001).
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).
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).
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).
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).
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.
Farashahi, R.R.: Hashing into hessian curves, In: Nitaj, A., Pointcheval, D. (eds). AFRICACRYPT 2011, LNCS, vol. 6737, pp. 278–289. Springer (2011).
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).
Fouque, P.-A., Joux, A., Tibouchi, M.: Injective encodings to elliptic curves. In: ACISP 2013, LNCS, vol. 7959, pp. 203–218, Springer (2013).
Icart, T.: How to hash into elliptic curves. In: CRPYTO 2009, LNCS, vol. 5677, pp. 303–316, Springer (2009).
Jablon D.P.: Strong password-only authenticated key exchange. SIGCOMM Comput. Commun. 26(5), 5–26 (1996).
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).
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).
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).
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field, IEEE, pp. 1639–1647, (1993).
Schoof R.: Elliptic curves over finite fields and the computation of square roots mod p. Math. Comput. 44(170), 483–494 (1985).
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).
Silverman J.H.: The Arithmetic of Elliptic Curves. Springer, Berlin (1995).
Skalba M.: Points on elliptic curves over finite fields. Acta Arithmat. 117(3), 293–301 (2005).
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).
Tibouchi M., Kim T.: Improved elliptic curve hashing and point representation. Des. Codes Cryptogr. 82, 161–177 (2017).
Ulas M.: Rational points on certain hyperelliptic curves over finite fields. Bull. Polish Acad. Sci. Math. 55(2), 97–104 (2007).
Washington L.C.: Elliptic Curves: Number Theory and Cryptography. CRC Press, Boca Raton (2008).
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
Corresponding author
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
About this article
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
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-020-00753-8