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

Multiple point compression on elliptic curves

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

Abstract

Point compression is an essential technique to save bandwidth and memory when deploying elliptic curve based security solutions in wireless communication systems. In this contribution, we provide new linear algebra (LA) based compression algorithms for multiple points on elliptic curves, that are compression algorithms which only make use of LA (with a constant number of field multiplications and at most one inversion, with no quadratic or higher degree polynomial root finding). In particular, we extend the results of Khabbazian et al. (IEEE Trans Comput 56(3):305–313, 2007) to four (resp. five) points on elliptic curves by generically storing five (resp. six) field elements and provide an asymptotic generalization to any number n of points on a curve \(y^2=f(x)\) by generically storing \(n+1\) values.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. In fact, as noticed by a reviewer of a previous version of this work, since one inversion is roughly equivalent to one square root extraction, there is the easier compression method of always storing \((x_1, x_2, y_1, b)\), where b is a bit allowing to compute \(y_2\) from \(f(x_2)=y^2_2\). The decompression then simply costs 1 inversion.

  2. Meaning that the \(2^n\) sums \(\pm y_1 \pm \cdots \pm y_n\) are all distinct.

References

  1. Adj G., Rodríguez-Henríquez F.: Square root computation over even extension fields. IEEE Trans. Comput. 63(11), 2829–2841 (2014).

  2. Ahmadi O., Hankerson D., Menezes A.: Software implementation of arithmetic in \({\mathbb{F}}_{3^m}\). In: Carlet C., Sunar B. (eds.) Proceedings of WAIFI 2007. Lecture Notes in Computer Science, vol. 4876, pp. 85–102. Springer, Berlin (2007).

  3. ANSI X9.62 Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) (2005).

  4. ANSI X9.63. Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography (2001).

  5. Avanzi R.M., Cohen H., Doche D., Frey G., Lange T., Nguyen K., Vercauteren F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, Boca Raton (2006).

  6. Avanzi R.M.: Another look at square roots (and other less common operations) in fields of even characteristic. In: Adams C., Miri A., Wiener M. (eds.) Proceedings of SAC 2007. Lecture Notes in Computer Science, vol. 4876, pp. 138–154. Springer, Berlin (2007).

  7. Barretol P.S.L.M., Kim H.Y., Lynn B., Scott M.: Efficient algorithms for pairing-based cryptosystems. In: Yung M. (ed.) Proceedings of CRYPTO 2002. Lecture Notes in Computer Science, vol. 2442, pp. 354–369. Springer, Berlin (2002).

  8. Bellare M., Namprempre C., Neven G.: Security proofs for identity-based identification and signature schemes. In: Cachin C., Camenisch J. (eds.) Proceedings of EUROCRYPT 2004. Lecture Notes in Computer Science, vol. 3027, pp. 268–286. Springer, Berlin (2004).

  9. Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., Moeller, B.: Elliptic curve cryptography (ECC) cipher suites for transport layer security (TLS). IETF Internet Draft, May 2006. http://tools.ietf.org/html/rfc4492.

  10. Campagna, M., Zaverucha, G.: A cryptographic suite for embedded systems (suite E). IETF Internet Draft, October 2012. http://tools.ietf.org/html/draft-campagna-suitee-04.

  11. Cohen H.: A Course in Computational Algebraic Number Theory, vol. 138. Graduate Texts in Mathematics. Springer, Berlin (1996).

  12. Cox D.A., Little J., O’Shea D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, Secaucus (2007).

  13. Cox D.A., Little J., O’Shea D.: Using Algebraic Geometry. Springer, Secaucus (1998).

  14. Devegili A.J., Scott M., Dahab R.: Implementing cryptographic pairings over Barreto-Naehrig curves. In: Takagi T., Okamoto E., Okamoto T., Okamoto T. (eds.) Proceedings of Pairing 2007. Lecture Notes in Computer Science, vol. 4575, pp. 197–207. Springer, Berlin (2007).

  15. Fan X., Gong G.: Accelerating signature-based broadcast authentication for wireless sensor networks. Ad Hoc Netw. 10(4), 723–736 (2012).

  16. Fulton W.: Intersection Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin (1984).

  17. Galindo D., Garcia F.D.: A Schnorr-like lightweight identity-based signature scheme. In: Preneel B. (ed.) Proceedings of AFRICACRYPT 2009. Lecture Notes in Computer Science, vol. 5580, pp. 135–148. Springer, Berlin (2009).

  18. Hankerson D., Menezes A., Vanstone S.: Guide to Elliptic Curve Cryptography. Springer, Heidelberg (2003).

  19. IEEE Vehicular Technology Society. IEEE standard for wireless access in vehicular environments security services for applications and management messages (2013).

  20. Khabbazian M., Gulliver T.A., Bhargava V.K.: Double point compression with applications to speeding up random point multiplication. IEEE Trans. Comput. 56(3), 305–313 (2007).

  21. Koblitz N.: Elliptic curve cryptosystems. J. Math. Comput. 48, 203–209 (1987).

  22. Koo N., Cho G.H., Kwon S.: Square root algorithm in\(\mathbb{F} _q\) for \(q \equiv 2^s + 1 ~(\text{mod} \; 2^{s+1})\). https://eprint.iacr.org/2013/087.pdf.

  23. Lange T.: Explicit formulas database. http://hyperelliptic.org.

  24. Liu Z., Seo H., Groschädl J., Kim H.: Efficient implementation of NIST-compliant elliptic curve cryptography for sensor node. In: Qing S., Zhou J., Liu D. (eds.) Proceedings of ICICS 2013. Lecture Notes in Computer Science, vol. 8233, pp. 302–317. Springer, Berlin (2013).

  25. Lou W., Ren K., Yu S., Zhang Y.: Multi-user broadcast authentication in wireless sensor networks. IEEE Trans. Veh. Technol. 58(8), 4554–4564 (2009).

  26. National Highway Traffic Safety Administration. Vehicle safety communications project—task 3 final report, March 2005. http://www.its.dot.gov/research_docs/pdf/59vehicle-safety.pdf.

  27. NIST SP 800-90. Recommendation for Random Number Generation Using Deterministic Random Bit Generators (2012)

  28. NIST Removes Cryptography Algorithm from Random Number Generator Recommendations, April 2014. http://www.nist.gov/itl/csd/sp800-90-042114.cfm.

  29. Peterson W.W., Brown D.T.: Cyclic Codes for Error Detection. Proc. IRE 49(1), 228–235 (1961).

    Article  MathSciNet  Google Scholar 

  30. Rouillier F.: Solving zero-dimensional systems through the rational univariate representation. Appl. Algebra Eng. Commun. Comput. 9(5), 433–461 (1999).

  31. Vanstone S., Menezes A., van Oorschot P.: Handbook of Applied Cryptography. CRC Press, Boca Raton (2001).

  32. Wollinger T., Pelzl J., Paar C., Saldamli G., Koç Ç.K.: Elliptic and hyperelliptic curves on embedded \(\mu \)p. ACM Trans. Embed. Comput. Syst. 3(3), 509–533 (2004).

  33. Yen S.-M., Laih C.-S., Lenstra A.K.: Multi-exponentiation. Comput. Digit. Tech. 141(6), 325–326 (1994).

  34. Zhu S., Liu D., Ning P., Jajodia S.: Practical broadcast authentication in sensor networks. In: Proceedings of the Second Annual International Conference on Mobile and Ubiquitous System: Networking and Services (MobiQuitous 2005), pp. 118–129 (2005).

Download references

Acknowledgments

We would like to thank Changbo Chen for the discussion about Gröbner bases and specifically about pointing us to the Shape Lemma. The project is financially supported by the grant of the Corporate Fund “Fund of Social Development” to Adilet Otemissov and Francesco Sica.

Author information

Authors and Affiliations

  1. Robert Bosch LLC, Bosch Research and Technology Center, Pittsburgh, PA, 15222, USA

    Xinxin Fan

  2. University of Manchester, Manchester, UK

    Adilet Otemissov

  3. School of Science and Technology, Nazarbayev University, 53 Kabanbay Batyr Avenue, 010000, Astana, Kazakhstan

    Francesco Sica

  4. Brightsight, Delftechpark 1, 2628XJ, Delft, The Netherlands

    Andrey Sidorenko

Authors
  1. Xinxin Fan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adilet Otemissov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Francesco Sica
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andrey Sidorenko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francesco Sica.

Additional information

Communicated by C. Mitchell.

This work was done when Xinxin Fan was a research associate at the University of Waterloo.

Adilet Otemissov worked on part of this project as his capstone thesis at Nazarbayev University.

Appendices

Appendix 1: Expression of the polynomials \(g_i\) when \(n=4\)

$$\begin{aligned} g_1\left( a_1\right)= & {} a_{1}^{16} + \left( -8 p_{2}\right) a_{1}^{14} + \left( 20 p_{2}^{2} + 8 p_{4}\right) a_{1}^{12} + \left( -\frac{88}{3} p_{2}^{3} + 16 p_{2} p_{4} - \frac{128}{3} p_{6}\right) a_{1}^{10} \\&+\, \left( -\frac{94}{3} p_{2}^{4} + 360 p_{2}^{2} p_{4} - 248 p_{4}^{2} - \frac{1664}{3} p_{2} p_{6} + 544 p_{8}\right) a_{1}^{8} \\&+\, \left( 72 p_{2}^{5} - \frac{1696}{3} p_{2}^{3} p_{4} + 480 p_{2} p_{4}^{2} + 768 p_{2}^{2} p_{6} - \frac{512}{3} p_{4} p_{6} - 640 p_{2} p_{8}\right) a_{1}^{6} \\&+ \,\left( -\frac{428}{9} p_{2}^{6} + \frac{1192}{3} p_{2}^{4} p_{4} - 624 p_{2}^{2} p_{4}^{2} - \frac{4352}{9} p_{2}^{3} p_{6} + 480 p_{4}^{3} \right. \\&\left. \quad +\, \frac{512}{3} p_{2} p_{4} p_{6} + 576 p_{2}^{2} p_{8} + \frac{4096}{9}p_{6}^{2} - 896 p_{4} p_{8}\right) a_{1}^{4} \\&+ \,\left( -\frac{56}{9} p_{2}^{7} + \frac{304}{3} p_{2}^{5} p_{4} - 480 p_{2}^{3} p_{4}^{2} - \frac{896}{9} p_{2}^{4} p_{6} + 320 p_{2} p_{4}^{3}+ \frac{3584}{3} p_{2}^{2} p_{4} p_{6}\right. \\&\left. \quad -\, \frac{128}{3} p_{2}^{3} p_{8} - \,512 p_{4}^{2} p_{6} - \frac{8192}{9} p_{2} p_{6}^{2} - 256 p_{2} p_{4} p_{8} + \frac{2048}{3} p_{6} p_{8}\right) a_{1}^{2} \\&+ \,\frac{25}{9} p_{2}^{8} - 40 p_{2}^{6} p_{4} + \frac{472}{3} p_{2}^{4} p_{4}^{2} + \frac{640}{9} p_{2}^{5} p_{6} - 96 p_{2}^{2} p_{4}^{3}\\&-\, 512 p_{2}^{3} p_{4} p_{6} - \frac{160}{3} p_{2}^{4} p_{8} \\&+ \,16 p_{4}^{4} + \frac{512}{3} p_{2} p_{4}^{2} p_{6} + \frac{4096}{9} p_{2}^{2} p_{6}^{2} + 384 p_{2}^{2} p_{4} p_{8} - 128 p_{4}^{2} p_{8}\\&- \,\frac{2048}{3} p_{2} p_{6} p_{8} + 256 p_{8}^{2} ,\\ g_2(a_1) \,= & {} \, \left( -\frac{1}{2}\right) a_{1}^{2} + \frac{1}{2} p_{2}. \end{aligned}$$

Next, \(g_3(a_1)\) equals

$$\begin{aligned}&\quad (3141 p_{2}^{6} - 29916 p_{2}^{4} p_{4} + 73575 p_{2}^{2} p_{4}^{2} + 27288 p_{2}^{3} p_{6} - 22950 p_{4}^{3} \\&\quad -\, 107568 p_{2} p_{4} p_{6} - 9558 p_{2}^{2} p_{8} + 41472 p_{6}^{2} + 24300 p_{4} p_{8}) a_{1}^{15} \\&\quad +\, (-24228 p_{2}^{7} + 229068 p_{2}^{5} p_{4} - 559224 p_{2}^{3} p_{4}^{2} - 203544 p_{2}^{4} p_{6}\\&\quad + \,174528 p_{2} p_{4}^{3} + 788832 p_{2}^{2} p_{4} p_{6}\\&\quad + \,67824 p_{2}^{3} p_{8} + 7776 p_{4}^{2} p_{6} - 290304 p_{2} p_{6}^{2} - 158112 p_{2} p_{4} p_{8} - 31104 p_{6} p_{8}) a_{1}^{13} \\&\quad +\, (56205 p_{2}^{8} - 498654 p_{2}^{6} p_{4} + 1024839 p_{2}^{4} p_{4}^{2} + 438408 p_{2}^{5} p_{6} + 177660 p_{2}^{2} p_{4}^{3}\\&\quad -\, 1425312 p_{2}^{3} p_{4} p_{6} \\&\quad - \,130086 p_{2}^{4} p_{8} - 178092 p_{4}^{4} - 885600 p_{2} p_{4}^{2} p_{6} + 539136 p_{2}^{2} p_{6}^{2} \\&\quad +\, 168696 p_{2}^{2} p_{4} p_{8} + 331776 p_{4} p_{6}^{2} + 166536 p_{4}^{2} p_{8} + 186624 p_{2} p_{6} p_{8} + 23328 p_{8}^{2}) a_{1}^{11} \\&\quad + \,(-78726 p_{2}^{9} + 789120 p_{2}^{7} p_{4} - 2350998 p_{2}^{5} p_{4}^{2} - 722856 p_{2}^{6} p_{6} \\&\quad + \,2106360 p_{2}^{3} p_{4}^{3}+4069584 p_{2}^{4} p_{4} p_{6} \end{aligned}$$
$$\begin{aligned}&\quad + \,169452 p_{2}^{5} p_{8} - 486216 p_{2} p_{4}^{4} - 5601312 p_{2}^{2} p_{4}^{2} p_{6} - 1869312 p_{2}^{3} p_{6}^{2} - 589680 p_{2}^{3} p_{4} p_{8}\nonumber \\&\quad + \,1046592 p_{4}^{3} p_{6} \\&\quad +\, 5612544 p_{2} p_{4} p_{6}^{2} + 907632 p_{2} p_{4}^{2} p_{8} + 252288 p_{2}^{2} p_{6} p_{8} - 1769472 p_{6}^{3}\\&\quad -\, 1306368 p_{4} p_{6} p_{8} - 171072 p_{2} p_{8}^{2}) a_{1}^{9} \\&\quad + \,(-113973 p_{2}^{10} + 2247624 p_{2}^{8} p_{4} - 14414355 p_{2}^{6} p_{4}^{2} - 2873976 p_{2}^{7} p_{6} + 35073162 p_{2}^{4} p_{4}^{3}\\&\quad + \,31435920 p_{2}^{5} p_{4} p_{6} + 2121606 p_{2}^{6} p_{8} - 26740476 p_{2}^{2} p_{4}^{4} - 88583328 p_{2}^{3} p_{4}^{2} p_{6}\\&\quad -\, 17567232 p_{2}^{4} p_{6}^{2} \\&\quad - \,20887092 p_{2}^{4} p_{4} p_{8} + 5739336 p_{4}^{5} + 40201920 p_{2} p_{4}^{3} p_{6} \nonumber \\&\quad + \,78474240 p_{2}^{2} p_{4} p_{6}^{2}+ 51563304 p_{2}^{2} p_{4}^{2} p_{8} \\&\quad +\, 20431872 p_{2}^{3} p_{6} p_{8} - 10616832 p_{4}^{2} p_{6}^{2} - 24772608 p_{2} p_{6}^{3}\\&\quad -\, 18752688 p_{4}^{3} p_{8} - 74428416 p_{2} p_{4} p_{6} p_{8} \\&\quad -\, 4854816 p_{2}^{2} p_{8}^{2} + 23887872 p_{6}^{2} p_{8} + 13421376 p_{4} p_{8}^{2}) a_{1}^{7} \\&\quad +\, (183552 p_{2}^{11} - 3089004 p_{2}^{9} p_{4} + 18070524 p_{2}^{7} p_{4}^{2} + 3134904 p_{2}^{8} p_{6} - 43127352 p_{2}^{5} p_{4}^{3} \\&\quad - \,31349184 p_{2}^{6} p_{4} p_{6} - 1758456 p_{2}^{7} p_{8} + 37337904 p_{2}^{3} p_{4}^{4}\\&\quad +\, 86126976 p_{2}^{4} p_{4}^{2} p_{6} + 13088256 p_{2}^{5} p_{6}^{2} \\&\quad +\, 15252912 p_{2}^{5} p_{4} p_{8} - 8725536 p_{2} p_{4}^{5} - 54885888 p_{2}^{2} p_{4}^{3} p_{6}\\&\quad -\, 52205568 p_{2}^{3} p_{4} p_{6}^{2} - 32713632 p_{2}^{3} p_{4}^{2} p_{8} \end{aligned}$$
$$\begin{aligned}&\quad -\, 9452160 p_{2}^{4} p_{6} p_{8} + 1798272 p_{4}^{4} p_{6} + 22321152 p_{2} p_{4}^{2} p_{6}^{2}\\&\quad + \,7077888 p_{2}^{2} p_{6}^{3} + 12156480 p_{2} p_{4}^{3} p_{8} \\&\quad +\, 15422976 p_{2}^{2} p_{4} p_{6} p_{8} + 1019520 p_{2}^{3} p_{8}^{2} - 7077888 p_{4} p_{6}^{3} + 8805888 p_{4}^{2} p_{6} p_{8} \\&\quad +\, 15925248 p_{2} p_{6}^{2} p_{8} + 4582656 p_{2} p_{4} p_{8}^{2} - 17915904 p_{6} p_{8}^{2}) a_{1}^{5} \\&\quad +\, (-119357 p_{2}^{12} + 2165658 p_{2}^{10} p_{4} - 14673531 p_{2}^{8} p_{4}^{2}\\&\quad -\, 2088552 p_{2}^{9} p_{6} + 46760208 p_{2}^{6} p_{4}^{3} \\&\quad +\, 23773056 p_{2}^{7} p_{4} p_{6} + 1897398 p_{2}^{8} p_{8} - 73942056 p_{2}^{4} p_{4}^{4}\\&\quad -\, 86667456 p_{2}^{5} p_{4}^{2} p_{6} - 9014784 p_{2}^{6} p_{6}^{2} \\&\quad -\, 22437504 p_{2}^{6} p_{4} p_{8} + 57054240 p_{2}^{2} p_{4}^{5} + 117450240 p_{2}^{3} p_{4}^{3} p_{6}\\&\quad + \,43920384 p_{2}^{4} p_{4} p_{6}^{2} + 87558768 p_{2}^{4} p_{4}^{2} p_{8} \\&\quad +\, 17627904 p_{2}^{5} p_{6} p_{8} - 12932784 p_{4}^{6} - 68144256 p_{2} p_{4}^{4} p_{6}\\&\quad -\, 20305920 p_{2}^{2} p_{4}^{2} p_{6}^{2} - 3506176 p_{2}^{3} p_{6}^{3} \\&\quad -\, 124350336 p_{2}^{2} p_{4}^{3} p_{8} - 111430656 p_{2}^{3} p_{4} p_{6} p_{8} - 6348672 p_{2}^{4} p_{8}^{2}\\&\quad + \,8687616 p_{4}^{3} p_{6}^{2} - 46006272 p_{2} p_{4} p_{6}^{3} \\&\quad +\, 45537120 p_{4}^{4} p_{8} + 143926272 p_{2} p_{4}^{2} p_{6} p_{8} + 36790272 p_{2}^{2} p_{6}^{2} p_{8}\\&\quad +\, 41478912 p_{2}^{2} p_{4} p_{8}^{2} + 18874368 p_{6}^{4} \\&\quad - \,23003136 p_{4} p_{6}^{2} p_{8} - 48169728 p_{4}^{2} p_{8}^{2} - 35665920 p_{2} p_{6} p_{8}^{2} + 15303168 p_{8}^{3}) a_{1}^{3} \end{aligned}$$
$$\begin{aligned}&\quad +\, (5186 p_{2}^{13} - 10704 p_{2}^{11} p_{4} - 936990 p_{2}^{9} p_{4}^{2} + 105288 p_{2}^{10} p_{6}\\&\quad +\, 8434128 p_{2}^{7} p_{4}^{3} + 1229136 p_{2}^{8} p_{4} p_{6} \\&\quad -\, 370452 p_{2}^{9} p_{8} - 26146800 p_{2}^{5} p_{4}^{4} - 23498496 p_{2}^{6} p_{4}^{2} p_{6} - 907776 p_{2}^{7} p_{6}^{2}\\&\quad +\, 3779424 p_{2}^{7} p_{4} p_{8} + 28215360 p_{2}^{3} p_{4}^{5} \\&\quad + \,92255232 p_{2}^{4} p_{4}^{3} p_{6} + 26336256 p_{2}^{5} p_{4} p_{6}^{2} - 9767520 p_{2}^{5} p_{4}^{2} p_{8}\\&\quad - \,3057024 p_{2}^{6} p_{6} p_{8} - 7140960 p_{2} p_{4}^{6} \\&\quad -\, 90170496 p_{2}^{2} p_{4}^{4} p_{6} - 132544512 p_{2}^{3} p_{4}^{2} p_{6}^{2} - 8880128 p_{2}^{4} p_{6}^{3}\\&\quad - \,3844224 p_{2}^{3} p_{4}^{3} p_{8} + 9347328 p_{2}^{4} p_{4} p_{6} p_{8} \\&\quad +\, 2239488 p_{2}^{5} p_{8}^{2} + 13130496 p_{4}^{5} p_{6} + 87527424 p_{2} p_{4}^{3} p_{6}^{2}\\&\quad +\, 88473600 p_{2}^{2} p_{4} p_{6}^{3} + 11524032 p_{2} p_{4}^{4} p_{8} \\&\quad +\, 60120576 p_{2}^{2} p_{4}^{2} p_{6} p_{8} - 9338880 p_{2}^{3} p_{6}^{2} p_{8} - 15123456 p_{2}^{3} p_{4} p_{8}^{2}\\&\quad -\, 17694720 p_{4}^{2} p_{6}^{3} - 18874368 p_{2} p_{6}^{4} \\&\quad -\, 36615168 p_{4}^{3} p_{6} p_{8} - 85819392 p_{2} p_{4} p_{6}^{2} p_{8} + 2087424 p_{2} p_{4}^{2} p_{8}^{2}\\&\quad +\, 25436160 p_{2}^{2} p_{6} p_{8}^{2} + 14155776 p_{6}^{3} p_{8} \\&\quad + 28532736 p_{4} p_{6} p_{8}^{2} - 12192768 p_{2} p_{8}^{3}) a_{1} \end{aligned}$$

divided by

$$\begin{aligned}&82560 p_{2}^{12} - 1615872 p_{2}^{10} p_{4} + 11757312 p_{2}^{8} p_{4}^{2} + 1855488 p_{2}^{9} p_{6} - 38739456 p_{2}^{6} p_{4}^{3} \\&\quad -\, 24600576 p_{2}^{7} p_{4} p_{6} - 1230336 p_{2}^{8} p_{8} + 55052928 p_{2}^{4} p_{4}^{4} + 105615360 p_{2}^{5} p_{4}^{2} p_{6} \\&\quad +\, 12435456 p_{2}^{6} p_{6}^{2} + 16137216 p_{2}^{6} p_{4} p_{8} - 26417664 p_{2}^{2} p_{4}^{5} - 150552576 p_{2}^{3} p_{4}^{3} p_{6} \\&\quad - \,92061696 p_{2}^{4} p_{4} p_{6}^{2} - 67834368 p_{2}^{4} p_{4}^{2} p_{8} - 16588800 p_{2}^{5} p_{6} p_{8} + 3995136 p_{4}^{6} \\&\quad + \,41213952 p_{2} p_{4}^{4} p_{6} + 127401984 p_{2}^{2} p_{4}^{2} p_{6}^{2} + \,28311552 p_{2}^{3} p_{6}^{3} + 90740736 p_{2}^{2} p_{4}^{3} p_{8} \\&\quad +\, 120029184 p_{2}^{3} p_{4} p_{6} p_{8} + 6068736 p_{2}^{4} p_{8}^{2} - 5308416 p_{4}^{3} p_{6}^{2} - 28311552 p_{2} p_{4} p_{6}^{3} \\&\quad -\, 24440832 p_{4}^{4} p_{8} - 132710400 p_{2} p_{4}^{2} p_{6} p_{8} - 63700992 p_{2}^{2} p_{6}^{2} p_{8} - 43960320 p_{2}^{2} p_{4} p_{8}^{2} \\&\quad +\, 21233664 p_{4} p_{6}^{2} p_{8} + 38320128 p_{4}^{2} p_{8}^{2} + 55738368 p_{2} p_{6} p_{8}^{2} -\, 17915904 p_{8}^{3}. \end{aligned}$$

The formula for \(g_4(a_1)\) is

$$\begin{aligned}&(-180 p_{2}^{3} + 756 p_{2} p_{4} - 648 p_{6}) a_{1}^{14} \\&\quad +\, (1323 p_{2}^{4} - 5382 p_{2}^{2} p_{4} - 459 p_{4}^{2} + 4536 p_{2} p_{6} + 486 p_{8}) a_{1}^{12} \\&\quad + \,(-2682 p_{2}^{5} + 8424 p_{2}^{3} p_{4} + 9918 p_{2} p_{4}^{2} - 7992 p_{2}^{2} p_{6} - 5616 p_{4} p_{6} - 3564 p_{2} p_{8}) a_{1}^{10} \\&\quad +\, (3111 p_{2}^{6} - 13500 p_{2}^{4} p_{4} + 7389 p_{2}^{2} p_{4}^{2} + 15528 p_{2}^{3} p_{6} - 3978 p_{4}^{3} - 45072 p_{2} p_{4} p_{6} \\&\quad + \,7182 p_{2}^{2} p_{8} + 27648 p_{6}^{2} + 4212 p_{4} p_{8}) a_{1}^{8} \\&\quad +\, (8520 p_{2}^{7} - 106788 p_{2}^{5} p_{4} + 340092 p_{2}^{3} p_{4}^{2} + 139368 p_{2}^{4} p_{6} - 190872 p_{2} p_{4}^{3} \\&\quad - 696480 p_{2}^{2} p_{4} p_{6} - 106200 p_{2}^{3} p_{8} + 176544 p_{4}^{2} p_{6} \\&\quad +\, 387072 p_{2} p_{6}^{2} + 419472 p_{2} p_{4} p_{8} - 373248 p_{6} p_{8}) a_{1}^{6} \\&\quad + \,(-8067 p_{2}^{8} + 83322 p_{2}^{6} p_{4} - 209049 p_{2}^{4} p_{4}^{2} - 88728 p_{2}^{5} p_{6} + 11412 p_{2}^{2} p_{4}^{3} \\&\quad + \,347040 p_{2}^{3} p_{4} p_{6} + 26586 p_{2}^{4} p_{8} + 118116 p_{4}^{4} - 9696 p_{2} p_{4}^{2} p_{6} - 119808 p_{2}^{2} p_{6}^{2} \\&\quad +\, 75528 p_{2}^{2} p_{4} p_{8} + 119808 p_{4} p_{6}^{2} - 382104 p_{4}^{2} p_{8} - 235008 p_{2} p_{6} p_{8} + 272160 p_{8}^{2}) a_{1}^{4} \\&\quad +\, (-818 p_{2}^{9} + 16344 p_{2}^{7} p_{4} - 104490 p_{2}^{5} p_{4}^{2} - 14312 p_{2}^{6} p_{6} + 177288 p_{2}^{3} p_{4}^{3} \\&\quad +\, 244944 p_{2}^{4} p_{4} p_{6} - 10188 p_{2}^{5} p_{8} + 66312 p_{2} p_{4}^{4} - 618336 p_{2}^{2} p_{4}^{2} p_{6} - 180224 p_{2}^{3} p_{6}^{2} \\&\quad +\, 5040 p_{2}^{3} p_{4} p_{8} - 115008 p_{4}^{3} p_{6} + 645120 p_{2} p_{4} p_{6}^{2} - 66672 p_{2} p_{4}^{2} p_{8} + 161280 p_{2}^{2} p_{6} p_{8} \\&\quad -\, 294912 p_{6}^{3} + 248832 p_{4} p_{6} p_{8} - 160704 p_{2} p_{8}^{2}) a_{1}^{2} \\&\quad +\, 3809 p_{2}^{10} - 58848 p_{2}^{8} p_{4} + 320919 p_{2}^{6} p_{4}^{2} + 57464 p_{2}^{7} p_{6} - 707514 p_{2}^{4} p_{4}^{3} \\&\quad -\, 565968 p_{2}^{5} p_{4} p_{6} - 33006 p_{2}^{6} p_{8} + 532188 p_{2}^{2} p_{4}^{4} + 1485984 p_{2}^{3} p_{4}^{2} p_{6} + 272384 p_{2}^{4} p_{6}^{2} \\&\quad + \,312660 p_{2}^{4} p_{4} p_{8} - 113832 p_{4}^{5} - 721344 p_{2} p_{4}^{3} p_{6} - 1096704 p_{2}^{2} p_{4} p_{6}^{2} - 749448 p_{2}^{2} p_{4}^{2} p_{8} \\&\quad -\, 296448 p_{2}^{3} p_{6} p_{8} + 165888 p_{4}^{2} p_{6}^{2} + 294912 p_{2} p_{6}^{3} + 331056 p_{4}^{3} p_{8} + 912384 p_{2} p_{4} p_{6} p_{8} \\&\quad +\, 97632 p_{2}^{2} p_{8}^{2} - 221184 p_{6}^{2} p_{8} - 222912 p_{4} p_{8}^{2} \end{aligned}$$

divided by

$$\begin{aligned}&-\,16512 p_{2}^{8} + 204288 p_{2}^{6} p_{4} - 840960 p_{2}^{4} p_{4}^{2} - 159744 p_{2}^{5} p_{6} + 1202688 p_{2}^{2} p_{4}^{3} \\&\quad +\, 1155072 p_{2}^{3} p_{4} p_{6} + 87552 p_{2}^{4} p_{8} - 332928 p_{4}^{4} - 1658880 p_{2} p_{4}^{2} p_{6} - 442368 p_{2}^{2} p_{6}^{2} \\&\quad -\, 635904 p_{2}^{2} p_{4} p_{8} + 442368 p_{4} p_{6}^{2} + 705024 p_{4}^{2} p_{8} + 663552 p_{2} p_{6} p_{8} - 373248 p_{8}^{2} . \end{aligned}$$

These formulas were obtained by running the following commands in SAGE (www.sagemath.org):

figure a

Appendix 2: Computational complexity of the decompression for \(n = 4\)

1.1 All points are decompressed

The calculation of the complexity is based on the principles described in [23], which are as follows.

  • Only the square and multiply operations are counted; the computational cost of the addition and subtraction is neglected.

  • Multiplication by a constant is neglected as well.

It most cases inversion is computationally costly as compared to multiplication and square operations. For that reason, we will minimize the number of the inversions.

Denote

$$\begin{aligned} B= & {} a_1\big (A^2+a_4^2-a_1^2b_3\big ),\\ C= & {} 2a_1\big (a_1^2a_2-A\big ),\\ D= & {} 2a_1^2a_2A-A^2+a_4^2-a_1^2b_3,\\ E= & {} 2a_1^2\big (a_1^2a_2-A\big ).\\ \end{aligned}$$

Then Eq. (10) yields

$$\begin{aligned} y_i = \frac{B+C\big (a_2y_i^2+y_i^4\big )}{D+Ey_i^2}. \end{aligned}$$
(23)

The computation of \(y_1, y_2, y_3, y_4\) separately using the equation above ends up with 4 inversions. For the sake of efficiency, it makes sense to compute \(y_i\)’s in the following way:

$$\begin{aligned} y_1= & {} \frac{\Big (B+C\big (a_2y_1^2+y_1^4\big )\Big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )},\\ y_2= & {} \frac{\Big (B+C\big (a_2y_2^2+y_2^4\big )\Big )\big (D+Ey_1^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )},\\ y_3= & {} \frac{\Big (B+C\big (a_2y_3^2+y_3^4\big )\Big )\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_4^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )},\\ y_4= & {} \frac{\Big (B+C\big (a_2y_4^2+y_4^4\big )\Big )\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )}. \end{aligned}$$

Here all \(y_i\)’s are converted to the common denominator, which means that only one inversion is needed.

Table 1 shows how the computational complexity is calculated.

Overall, the decompression algorithm require \(55M + 11S + 1I\).

Table 1 Computational complexity of the decompression algorithm
Full size table

1.2 Only one point is decompressed

The complexity of the decompression can be reduced when one has to extract only one \(y_i, i \in \{1, 2, 3, 4\},\) and not all of them. Note that in many practical situations only one of the y-coordinates has to be extracted for the archive.

Without loss of generality, suppose we have to recover \(y_1\). We will compute \(y_1\) using Eq. (23).

Table 2 Computational complexity of the preparation step
Full size table

Then in Table 1 we can avoid the computation of the following values: \(D + E y_2^2\), \(D + E y_3^2\), \(D + E y_4^2\), \(\big (D + E y_1^2\big ) \big (D + E y_2^2\big ) \big (D + E y_3^2\big ) \big (D + E y_4^2\big )\), \(B + C\big (a_2 y_2^2 + y_2^4\big )\), \(B + C\big (a_2 y_3^2 + y_2^4\big )\), \(B + C\big (a_2 y_4^2 + y_2^4\big )\). This saves us \(1M + 1M + 1M + 3M + 2M + 2M + 2M = 12M\).

Table 3 Computational complexity of the final computation: all \(y_i\)’s are retrieved
Full size table
Table 4 Computational complexity of the final computation: only \(y_1\) is retrieved
Full size table

Instead of inverting \(\big (D + E y_1^2\big ) \big (D + E y_2^2\big ) \big (D + E y_3^2\big ) \big (D + E y_4^2\big )\) we will invert \(\big (D + E y_1^2\big )\) so we still need 1I.

In the end we needed extra 16M to compute \(y_1, y_2, y_3, y_4\) (see the very end of Sect. 1). And now we will need 1M instead: this is the multiplication \(\Big (B + C \big (a_2 y_1^2 + y_1^4\big )\Big ) \cdot \big (D + E y_1^2\big )^{-1}\). This saves us 15M.

In total we save \(12M + 15M = 27M\) and the overall complexity becomes \((55M + 11S + 1I) - 27M = 28M + 11S + 1I\).

Furthermore, in the case when the decompression algorithm may output the projective coordinates of the point (which is acceptable e.g. when the decompressed point is used for the point addition or point doubling) we can avoid the inversion.

Appendix 3: Computational complexity of the decompression for \(n = 5\)

1.1 Preparation step

Table 2 shows the cost of computing \(y_i^2, b_i\), \(i = 1, 2, 3, 4, 5\) as well as C, F, G, H, K, L.

1.2 Final computation of \(y_i\)

Table 3 demonstrates the cost of the computation of \(y_i\), \(i = 1, 2, 3, 4, 5\) in the case when the goal is to retrieve the y-coordinates of all five points. Table 4 shows the cost of the computational complexity can be reduced significantly when the goal is to retrieve only one \(y_i, i \in \{1, 2, 3, 4, 5\}\).

The overall computational complexity of the decompression algorithm is \(120 M + 12 S + I\) in the case when the goal is to retrieve the y-coordinates of all five points. If only one point has to be retrieved the complexity reduces to \(64 M + 12 S + I\). Furthermore, when the decompression algorithm may output the projective coordinates we can avoid the inversion.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fan, X., Otemissov, A., Sica, F. et al. Multiple point compression on elliptic curves. Des. Codes Cryptogr. 83, 565–588 (2017). https://doi.org/10.1007/s10623-016-0251-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-016-0251-2

Keywords

Mathematics Subject Classification

Search

Navigation