Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves

Srinivasa Rao Subramanya Rao

doi:10.1007/978-3-319-31517-1_5

Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves

Srinivasa Rao Subramanya Rao^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Citations (Scopus)

Abstract

Elliptic Curve Cryptography is an important alternative to traditional public key schemes such as RSA. This paper presents (i) a simultaneous triple scalar multiplication algorithm to compute the x-coordinate of kP + lQ + uR on a Montgomery Curve E_m defined over (image found)_p which is about 15 to 22% faster than the straight forward method of doing the same. The algorithm, motivated by Bernstein’s paper on Differential Addition Chains, where the author proposes various 2-dimensional differential addition chains and asks for 3- dimensional versions to be constructed, can be generalized to other elliptic curve forms with differential addition formula, (ii) a formula for Differential point tripling on Montgomery Curves which is slightly better than computing 3P as 2P + P and relevant in the implementation of Montgomery’s PRAC and (iii) an improvement in Mishra and Dimitrov’s point Quintupling algorithm for Weierstrass’ curves and an efficient Quintupling algorithm for Edwards Curves.

Original language	English
Title of host publication	Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings
Editors	David Pointcheval, Tajjeeddine Rachidi, Abderrahmane Nitaj
Publisher	Springer Verlag
Pages	84-106
Number of pages	23
ISBN (Print)	9783319315164
DOIs	https://doi.org/10.1007/978-3-319-31517-1_5
Publication status	Published - 2016
Event	8th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2016 - Fes, Morocco Duration: 13 Apr 2016 → 15 Apr 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9646
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2016
Country/Territory	Morocco
City	Fes
Period	13/04/16 → 15/04/16

Access to Document

10.1007/978-3-319-31517-1_5

Cite this

Subramanya Rao, S. R. (2016). Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves. In D. Pointcheval, T. Rachidi, & A. Nitaj (Eds.), Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings (pp. 84-106). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9646). Springer Verlag. https://doi.org/10.1007/978-3-319-31517-1_5

Subramanya Rao, Srinivasa Rao. / Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves. Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings. editor / David Pointcheval ; Tajjeeddine Rachidi ; Abderrahmane Nitaj. Springer Verlag, 2016. pp. 84-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{36b63c30f3854d95af75a2247ea690d4,

title = "Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass{\textquoteright} and Edwards curves",

abstract = "Elliptic Curve Cryptography is an important alternative to traditional public key schemes such as RSA. This paper presents (i) a simultaneous triple scalar multiplication algorithm to compute the x-coordinate of kP + lQ + uR on a Montgomery Curve Em defined over (image found)p which is about 15 to 22% faster than the straight forward method of doing the same. The algorithm, motivated by Bernstein{\textquoteright}s paper on Differential Addition Chains, where the author proposes various 2-dimensional differential addition chains and asks for 3- dimensional versions to be constructed, can be generalized to other elliptic curve forms with differential addition formula, (ii) a formula for Differential point tripling on Montgomery Curves which is slightly better than computing 3P as 2P + P and relevant in the implementation of Montgomery{\textquoteright}s PRAC and (iii) an improvement in Mishra and Dimitrov{\textquoteright}s point Quintupling algorithm for Weierstrass{\textquoteright} curves and an efficient Quintupling algorithm for Edwards Curves.",

keywords = "Akishita{\textquoteright}s algorithm, Bernstein{\textquoteright}s algorithm, Differential addition chains, Differential point tripling, Double scalar multiplication, Edwards curves, Lucas chains, Montgomery curves, Multiexponentiation, Point quintupling, Schoenmakers{\textquoteright} algorithm, Triple scalar multiplication",

author = "{Subramanya Rao}, {Srinivasa Rao}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 8th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2016 ; Conference date: 13-04-2016 Through 15-04-2016",

year = "2016",

doi = "10.1007/978-3-319-31517-1_5",

language = "English",

isbn = "9783319315164",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "84--106",

editor = "David Pointcheval and Tajjeeddine Rachidi and Abderrahmane Nitaj",

booktitle = "Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings",

address = "Germany",

}

Subramanya Rao, SR 2016, Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves. in D Pointcheval, T Rachidi & A Nitaj (eds), Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9646, Springer Verlag, pp. 84-106, 8th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2016, Fes, Morocco, 13/04/16. https://doi.org/10.1007/978-3-319-31517-1_5

Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves. / Subramanya Rao, Srinivasa Rao.
Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings. ed. / David Pointcheval; Tajjeeddine Rachidi; Abderrahmane Nitaj. Springer Verlag, 2016. p. 84-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9646).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves

AU - Subramanya Rao, Srinivasa Rao

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - Elliptic Curve Cryptography is an important alternative to traditional public key schemes such as RSA. This paper presents (i) a simultaneous triple scalar multiplication algorithm to compute the x-coordinate of kP + lQ + uR on a Montgomery Curve Em defined over (image found)p which is about 15 to 22% faster than the straight forward method of doing the same. The algorithm, motivated by Bernstein’s paper on Differential Addition Chains, where the author proposes various 2-dimensional differential addition chains and asks for 3- dimensional versions to be constructed, can be generalized to other elliptic curve forms with differential addition formula, (ii) a formula for Differential point tripling on Montgomery Curves which is slightly better than computing 3P as 2P + P and relevant in the implementation of Montgomery’s PRAC and (iii) an improvement in Mishra and Dimitrov’s point Quintupling algorithm for Weierstrass’ curves and an efficient Quintupling algorithm for Edwards Curves.

AB - Elliptic Curve Cryptography is an important alternative to traditional public key schemes such as RSA. This paper presents (i) a simultaneous triple scalar multiplication algorithm to compute the x-coordinate of kP + lQ + uR on a Montgomery Curve Em defined over (image found)p which is about 15 to 22% faster than the straight forward method of doing the same. The algorithm, motivated by Bernstein’s paper on Differential Addition Chains, where the author proposes various 2-dimensional differential addition chains and asks for 3- dimensional versions to be constructed, can be generalized to other elliptic curve forms with differential addition formula, (ii) a formula for Differential point tripling on Montgomery Curves which is slightly better than computing 3P as 2P + P and relevant in the implementation of Montgomery’s PRAC and (iii) an improvement in Mishra and Dimitrov’s point Quintupling algorithm for Weierstrass’ curves and an efficient Quintupling algorithm for Edwards Curves.

KW - Akishita’s algorithm

KW - Bernstein’s algorithm

KW - Differential addition chains

KW - Differential point tripling

KW - Double scalar multiplication

KW - Edwards curves

KW - Lucas chains

KW - Montgomery curves

KW - Multiexponentiation

KW - Point quintupling

KW - Schoenmakers’ algorithm

KW - Triple scalar multiplication

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

U2 - 10.1007/978-3-319-31517-1_5

DO - 10.1007/978-3-319-31517-1_5

M3 - Conference contribution

SN - 9783319315164

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 84

EP - 106

BT - Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings

A2 - Pointcheval, David

A2 - Rachidi, Tajjeeddine

A2 - Nitaj, Abderrahmane

PB - Springer Verlag

T2 - 8th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2016

Y2 - 13 April 2016 through 15 April 2016

ER -

Subramanya Rao SR. Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves. In Pointcheval D, Rachidi T, Nitaj A, editors, Progress in Cryptology – AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Proceedings. Springer Verlag. 2016. p. 84-106. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-31517-1_5

Three dimensional Montgomery ladder, differential point tripling on Montgomery curves and point quintupling on Weierstrass’ and Edwards curves

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this