Multiple point compression on elliptic curves

Xinxin Fan, Adilet Otemissov, Francesco Sica, Andrey Sidorenko

    Research output: Contribution to journalArticle

    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 languageEnglish
    Pages (from-to)1-24
    Number of pages24
    JournalDesigns, Codes, and Cryptography
    DOIs
    Publication statusAccepted/In press - Jul 25 2016

    Fingerprint

    Linear algebra
    Elliptic Curves
    Compression
    Communication systems
    Polynomials
    Polynomial Roots
    Bandwidth
    Data storage equipment
    Root-finding
    Wireless Communication
    Communication Systems
    Inversion
    Multiplication
    Curve

    Keywords

    • Cryptography
    • Elliptic curves
    • Point compression

    ASJC Scopus subject areas

    • Applied Mathematics
    • Computer Science Applications

    Cite this

    Multiple point compression on elliptic curves. / Fan, Xinxin; Otemissov, Adilet; Sica, Francesco; Sidorenko, Andrey.

    In: Designs, Codes, and Cryptography, 25.07.2016, p. 1-24.

    Research output: Contribution to journalArticle

    Fan, Xinxin ; Otemissov, Adilet ; Sica, Francesco ; Sidorenko, Andrey. / Multiple point compression on elliptic curves. In: Designs, Codes, and Cryptography. 2016 ; pp. 1-24.
    @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 = "7",
    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

    SP - 1

    EP - 24

    JO - Designs, Codes, and Cryptography

    JF - Designs, Codes, and Cryptography

    SN - 0925-1022

    ER -