Generation of Elliptic Curve Points in Tandem

• Armando Faz-Hernández UNICAMP
• Julio López Cloudflare Inc.

DOI: https://doi.org/10.5753/sbseg.2020.19230

Resumo

A hash to curve function H, mapping bit strings to points on an elliptic curve, is often required in cryptographic schemes based on elliptic curves. Its construction is based on a deterministic encoding and a cryptographic hash function, which complementarily dominate its execution time. To improve the performance of H, we propose a parallel strategy where two units execute in tandem the internal operations of H. We instantiate this approach with a parallel software implementation of a hash to curve function that outputs points on a twisted Edwards curve. A performance benchmark on Haswell and Skylake micro-architectures shows that our parallel implementation is 1.4 times faster than its sequential implementation.

Referências

Aranha, D. F., Fouque, P.-A., Qian, C., Tibouchi, M., Zapalowicz, J.-C. (2014). Binary Elligator Squared. In A. Joux A. Youssef (Eds.), Selected Areas in Cryptography – SAC 2014 (Vol. 8781, pp. 20–37). Springer, Cham. doi: 10.1007/978-3-319-13051-4_2

ARM Limited. (2009, June). Introducing NEON TM development article (Computer software manual No. 1). Retrieved from http://infocenter.arm.com/help/topic/com.arm.doc.dht0002a

Bernstein, D. J., Hamburg, M., Krasnova, A., Lange, T. (2013). Elligator: Elliptic-curve points indistinguishable from uniform random strings. In Proceedings of the 2013 ACM SIGSAC conference on computer & communications security (pp. 967–980). New York, NY, USA: Association for Computing Machinery. doi: 10.1145/2508859.2516734

Bernstein, D. J., Lange, T. (2007). Faster addition and doubling on elliptic curves. In K. Kurosawa (Ed.), Advances in Cryptology – ASIACRYPT 2007 (Vol. 4833, pp. 29–50). Springer Berlin Heidelberg. doi: 10.1007/978-3-540-76900-2_3

Bernstein, D. J., Lange, T. (2020, March). ebacs: Ecrypt benchmarking of cryptographic systems. Accessed on March 2020. Retrieved from http://bench.cr.yp.to/supercop.html

Boneh, D., Franklin, M. (2001). Identity-based encryption from the Weil pairing. In J. Kilian (Ed.), Advances in Cryptology—CRYPTO 2001 (Vol. 2139, pp. 213–229).

Berlin, Heidelberg: Springer Berlin Heidelberg. doi: 10.1007/3-540-44647-8_13

Brier, E., Coron, J.-S., Icart, T., Madore, D., Randriam, H., Tibouchi, M. (2010). Efficient indifferentiable hashing into ordinary elliptic curves. In T. Rabin (Ed.), Advances in Cryptology – CRYPTO 2010 (Vol. 6223, pp. 237–254). Springer Berlin Heidelberg. doi: 10.1007/978-3-642-14623-7_13

Denis, F. (2019, May). Sodium (v1.0.18 ed.) [Computer software]. Retrieved from http://libsodium.org

Farashahi, R. R., Fouque, P.-A., Shparlinski, I. E., Tibouchi, M., Voloch, J. F. (2013). Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Mathemathics of Computation, 82(281), 491–512. doi: 10.1090/S0025-5718-2012-02606-8

Faz-Hernández, A., López, J., Dahab, R. (2019, July). High-performance implementation of elliptic curve cryptography using vector instructions. ACM Transactions on Mathematical Software (TOMS), 45(3), 1–35. doi: 10.1145/3309759

Faz-Hernández, A., Scott, S., Sullivan, N., Wahby, R. S., Wood, C. A. (2020, June 29).

Hashing to elliptic curves (Internet-Draft No. draft-irtf-cfrg-hash-to-curve-09). Internet Engineering Task Force. Retrieved from https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve (Work in Progress)

Fouque, P.-A., Tibouchi, M. (2012). Indifferentiable hashing to Barreto–Naehrig curves. In A. Hevia G. Neven (Eds.), Progress in Cryptology – LATINCRYPT 2012 (Vol. 7533, pp. 1–17). Springer Berlin Heidelberg. doi: 10.1007/978-3-642-33481-8_1

Freescale Semiconductor. (1999, June). AltiVec Technology Programming Interface Manual [Computer software manual]. Retrieved from https://www.nxp.com/docs/en/reference-manual/ALTIVECPIM.pdf

Granlund, T., the GMP development team. (2012). GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.) [Computer software]. Retrieved from http://gmplib.org/

Hisil, H.,Wong, K.-H., Carter, G., Dawson, E. (2008). Twisted Edwards curves revisited. In J. Pieprzyk (Ed.), Advances in Cryptology - ASIACRYPT 2008 (Vol. 5350, pp. 326–343). Springer Berlin Heidelberg. doi: 10.1007/978-3-540-89255-7_20

Icart, T. (2009). How to hash into elliptic curves. In S. Halevi (Ed.), Advances in Cryptology - CRYPTO 2009 (Vol. 5677, pp. 303–316). Springer Berlin Heidelberg. doi: 10.1007/978-3-642-03356-8_18

Intel Corporation. (2011, June). Intel Advanced Vector Extensions Programming Reference (Vol. 319433-011) [Computer software manual]. Retrieved from https://software.intel.com/sites/default/files/m/f/7/c/36945

Maurer, U., Renner, R., Holenstein, C. (2004). Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In M. Naor (Ed.), Theory of cryptography (Vol. 2951, pp. 21–39). Springer Berlin Heidelberg. doi: 10.1007/978-3-540-24638-1_2

National Institute of Standards and Technology. (2008). FIPS PUB 180-4, Secure Hash Standard, Federal Information Processing Standard (FIPS), Publication 180-4. Gaithersburg, MD, USA: National Institute for Standards and Technology. (Supersedes FIPS PUB 180-3 October 2008.) doi: 10.6028/NIST.FIPS.180-4

Oliveira, T., López, J., Hisil, H., Faz-Hernández, A., Rodríguez-Henríquez, F. (2018). How to (pre-)compute a ladder. In C. Adams J. Camenisch (Eds.), Selected Areas in Cryptography – SAC 2017 (Vol. 10719, pp. 172–191). Springer, Cham. doi: 10.1007/978-3-319-72565-9_9

Shallue, A., van de Woestijne, C. E. (2006). Construction of rational points on elliptic curves over finite fields. In F. Hess, S. Pauli, M. Pohst (Eds.), Algorithmic number theory (Vol. 4076, pp. 510–524). Springer Berlin Heidelberg. doi: 10.1007/11792086_36

Skalba, M. (2005). Points on elliptic curves over finite fields. Acta Arithmetica, 117(3), 293–301. Retrieved from http://eudml.org/doc/278782