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

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

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

Original language	English
Pages (from-to)	565-588
Number of pages	24
Journal	Designs, Codes, and Cryptography
Volume	83
Issue number	3
DOIs	https://doi.org/10.1007/s10623-016-0251-2
Publication status	Published - Jun 1 2017

Keywords

Cryptography
Elliptic curves
Point compression

ASJC Scopus subject areas

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

Access to Document

10.1007/s10623-016-0251-2

Cite this

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

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

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

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = jun,

day = "1",

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

language = "English",

volume = "83",

pages = "565--588",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Multiple point compression on elliptic curves

AU - Fan, Xinxin

AU - Otemissov, Adilet

AU - Sica, Francesco

AU - Sidorenko, Andrey

PY - 2017/6/1

Y1 - 2017/6/1

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

SN - 0925-1022

VL - 83

SP - 565

EP - 588

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

IS - 3

ER -

Multiple point compression on elliptic curves

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this