Double Point Compression with Applications to Speeding Up Random Point Multiplication

TitleDouble Point Compression with Applications to Speeding Up Random Point Multiplication
Publication TypeJournal Article
Year of Publication2007
AuthorsKhabbazian, M., T. A. Gulliver, and V. K. Bhargava
JournalComputers, IEEE Transactions on
Pagination305 -313
Date Publishedmar.
Keywordscryptography, data compression, digital arithmetic, double point compression, elliptic curve cryptography, lookup table, Moller algorithm, parallel processing, random point multiplication, table lookup

This paper presents two main results relating to elliptic curve cryptography. First, a double point compression scheme is proposed which allows a compact representation of elliptic curve points without the computational cost associated with ordinary single point compression. A triple point compression scheme is also proposed which can result in more savings in memory and/or bandwidth. Second, a new approach to speeding up random point multiplication is given for the case where the base point is variable but available in a certificate. In this approach, some redundant information (a few multiples of the base point) is added to the certificate. It is shown that a significant speed up can be obtained by optimizing the Moller's algorithm for the case where only a portion of the lookup table is available. It is also shown how to use redundant information to compute random point multiplication using parallel processors. The proposed point compression schemes can be employed to reduce the required bandwidth when single point compression is computationally expensive


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2020 The University of British Columbia