Multiple point compression on elliptic curves

Xinxin Fan; Adilet Otemissov; Francesco Sica; Andrey Sidorenko

doi:10.1007/s10623-016-0251-2

Multiple point compression on elliptic curves

Xinxin Fan, Adilet Otemissov, Francesco Sica, Andrey Sidorenko

Research output: Contribution to journal › Article

1 Citation (Scopus)

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 (Formula presented.) by generically storing (Formula presented.) values.

Original language	English
Pages (from-to)	1-24
Number of pages	24
Journal	Designs, Codes, and Cryptography
DOIs	https://doi.org/10.1007/s10623-016-0251-2
Publication status	Accepted/In press - Jul 25 2016

Keywords

Cryptography
Elliptic curves
Point compression

ASJC Scopus subject areas

Applied Mathematics
Computer Science Applications

Access to Document

10.1007/s10623-016-0251-2

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

Cite this

Fan, X., Otemissov, A., Sica, F., & Sidorenko, A. (Accepted/In press). Multiple point compression on elliptic curves. Designs, Codes, and Cryptography, 1-24. https://doi.org/10.1007/s10623-016-0251-2

@article{7c134b6cb3bf4caf9b53d506e8af838a,

title = "Multiple point compression on elliptic curves",

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 (Formula presented.) by generically storing (Formula presented.) values.",

keywords = "Cryptography, Elliptic curves, Point compression",

author = "Xinxin Fan and Adilet Otemissov and Francesco Sica and Andrey Sidorenko",

year = "2016",

month = jul,

day = "25",

doi = "10.1007/s10623-016-0251-2",

language = "English",

pages = "1--24",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

publisher = "Springer Netherlands",

}

TY - JOUR

T1 - Multiple point compression on elliptic curves

AU - Fan, Xinxin

AU - Otemissov, Adilet

AU - Sica, Francesco

AU - Sidorenko, Andrey

PY - 2016/7/25

Y1 - 2016/7/25

N2 - 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 (Formula presented.) by generically storing (Formula presented.) values.

AB - 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 (Formula presented.) by generically storing (Formula presented.) values.

KW - Cryptography

KW - Elliptic curves

KW - Point compression

UR - http://www.scopus.com/inward/record.url?scp=84979539143&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84979539143&partnerID=8YFLogxK

U2 - 10.1007/s10623-016-0251-2

DO - 10.1007/s10623-016-0251-2

M3 - Article

AN - SCOPUS:84979539143

SP - 1

EP - 24

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

SN - 0925-1022

ER -