Efficient finite field multiplication for isogeny based post quantum cryptography

Angshuman Karmakar; Sujoy Sinha Roy; Frederik Vercauteren; Ingrid Verbauwhede

doi:10.1007/978-3-319-55227-9_14

Efficient finite field multiplication for isogeny based post quantum cryptography

Angshuman Karmakar^*, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid Verbauwhede

^*Corresponding author for this work

Computer Science

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

13 Citations (Scopus)

168 Downloads (Pure)

Abstract

Isogeny based post-quantum cryptography is one of the most recent addition to the family of quantum resistant cryptosystems. In this paper we propose an efficient modular multiplication algorithm for primes of the form p =2· 2^a3^b − 1withb even, typically used in such cryptosystem. Our modular multiplication algorithm exploits the special structure present in such primes. We compare the efficiency of our technique with Barrett reduction and Montgomery multiplication. Our C implementation shows that our algorithm is approximately 3 times faster than the normal Barrett reduction.

Original language	English
Title of host publication	Arithmetic of Finite Fields
Subtitle of host publication	6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers
Editors	Sylvain Duquesne, Svetla Petkova-Nikova
Publisher	Springer Verlag
Pages	193-207
Number of pages	15
ISBN (Electronic)	9783319552279
ISBN (Print)	9783319552262
DOIs	https://doi.org/10.1007/978-3-319-55227-9_14
Publication status	Published - 9 Mar 2017
Event	6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016 - Ghent, Belgium Duration: 13 Jul 2016 → 15 Jul 2016

Publication series

Name	Lecture Notes in Computer Science
Volume	10064
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016
Country/Territory	Belgium
City	Ghent
Period	13/07/16 → 15/07/16

Keywords

Isogeny
Modular multiplication
Post-quantum cryptography

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-55227-9_14Licence: None: All rights reserved

Karmakar_et_al_Efficient_finite_field_multiplication_for_isogeny_based_post_quantum_cryptography_Arithmetic_of_Finite_Fields_2017
The final authenticated version is available online at: https://doi.org/10.1007/978-3-319-55227-9_14
Accepted author manuscript, 119 KBLicence: None: All rights reserved

Cite this

Karmakar, A., Roy, S. S., Vercauteren, F., & Verbauwhede, I. (2017). Efficient finite field multiplication for isogeny based post quantum cryptography. In S. Duquesne, & S. Petkova-Nikova (Eds.), Arithmetic of Finite Fields: 6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers (pp. 193-207). (Lecture Notes in Computer Science; Vol. 10064 ). Springer Verlag. https://doi.org/10.1007/978-3-319-55227-9_14

Karmakar, Angshuman ; Roy, Sujoy Sinha ; Vercauteren, Frederik et al. / Efficient finite field multiplication for isogeny based post quantum cryptography. Arithmetic of Finite Fields: 6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers. editor / Sylvain Duquesne ; Svetla Petkova-Nikova. Springer Verlag, 2017. pp. 193-207 (Lecture Notes in Computer Science).

@inproceedings{ed5eaf6cb341499a8c13c69905afb97c,

title = "Efficient finite field multiplication for isogeny based post quantum cryptography",

abstract = "Isogeny based post-quantum cryptography is one of the most recent addition to the family of quantum resistant cryptosystems. In this paper we propose an efficient modular multiplication algorithm for primes of the form p =2· 2a3b − 1withb even, typically used in such cryptosystem. Our modular multiplication algorithm exploits the special structure present in such primes. We compare the efficiency of our technique with Barrett reduction and Montgomery multiplication. Our C implementation shows that our algorithm is approximately 3 times faster than the normal Barrett reduction.",

keywords = "Isogeny, Modular multiplication, Post-quantum cryptography",

author = "Angshuman Karmakar and Roy, {Sujoy Sinha} and Frederik Vercauteren and Ingrid Verbauwhede",

year = "2017",

month = mar,

day = "9",

doi = "10.1007/978-3-319-55227-9_14",

language = "English",

isbn = "9783319552262",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "193--207",

editor = "Sylvain Duquesne and Svetla Petkova-Nikova",

booktitle = "Arithmetic of Finite Fields",

note = "6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016 ; Conference date: 13-07-2016 Through 15-07-2016",

}

Karmakar, A, Roy, SS, Vercauteren, F & Verbauwhede, I 2017, Efficient finite field multiplication for isogeny based post quantum cryptography. in S Duquesne & S Petkova-Nikova (eds), Arithmetic of Finite Fields: 6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10064 , Springer Verlag, pp. 193-207, 6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016, Ghent, Belgium, 13/07/16. https://doi.org/10.1007/978-3-319-55227-9_14

Efficient finite field multiplication for isogeny based post quantum cryptography. / Karmakar, Angshuman; Roy, Sujoy Sinha; Vercauteren, Frederik et al.

Arithmetic of Finite Fields: 6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers. ed. / Sylvain Duquesne; Svetla Petkova-Nikova. Springer Verlag, 2017. p. 193-207 (Lecture Notes in Computer Science; Vol. 10064 ).

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

TY - GEN

T1 - Efficient finite field multiplication for isogeny based post quantum cryptography

AU - Karmakar, Angshuman

AU - Roy, Sujoy Sinha

AU - Vercauteren, Frederik

AU - Verbauwhede, Ingrid

PY - 2017/3/9

Y1 - 2017/3/9

N2 - Isogeny based post-quantum cryptography is one of the most recent addition to the family of quantum resistant cryptosystems. In this paper we propose an efficient modular multiplication algorithm for primes of the form p =2· 2a3b − 1withb even, typically used in such cryptosystem. Our modular multiplication algorithm exploits the special structure present in such primes. We compare the efficiency of our technique with Barrett reduction and Montgomery multiplication. Our C implementation shows that our algorithm is approximately 3 times faster than the normal Barrett reduction.

AB - Isogeny based post-quantum cryptography is one of the most recent addition to the family of quantum resistant cryptosystems. In this paper we propose an efficient modular multiplication algorithm for primes of the form p =2· 2a3b − 1withb even, typically used in such cryptosystem. Our modular multiplication algorithm exploits the special structure present in such primes. We compare the efficiency of our technique with Barrett reduction and Montgomery multiplication. Our C implementation shows that our algorithm is approximately 3 times faster than the normal Barrett reduction.

KW - Isogeny

KW - Modular multiplication

KW - Post-quantum cryptography

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

U2 - 10.1007/978-3-319-55227-9_14

DO - 10.1007/978-3-319-55227-9_14

M3 - Conference contribution

AN - SCOPUS:85015176101

SN - 9783319552262

T3 - Lecture Notes in Computer Science

SP - 193

EP - 207

BT - Arithmetic of Finite Fields

A2 - Duquesne, Sylvain

A2 - Petkova-Nikova, Svetla

PB - Springer Verlag

T2 - 6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016

Y2 - 13 July 2016 through 15 July 2016

ER -

Karmakar A, Roy SS, Vercauteren F, Verbauwhede I. Efficient finite field multiplication for isogeny based post quantum cryptography. In Duquesne S, Petkova-Nikova S, editors, Arithmetic of Finite Fields: 6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers. Springer Verlag. 2017. p. 193-207. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-55227-9_14

Efficient finite field multiplication for isogeny based post quantum cryptography

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this