Multiple point compression on elliptic curves

Xinxin Fan, Adilet Otemissov, Francesco Sica, Andrey Sidorenko

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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 y2= f(x) by generically storing n+ 1 values.

Original languageEnglish
Pages (from-to)565-588
Number of pages24
JournalDesigns, Codes, and Cryptography
Issue number3
Publication statusPublished - Jun 1 2017


  • Cryptography
  • Elliptic curves
  • Point compression

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Multiple point compression on elliptic curves'. Together they form a unique fingerprint.

Cite this