Don’t forget your roots: Constant-time root finding over F2m

Douglas Martins; Gustavo Banegas; Ricardo Custódio

doi:10.1007/978-3-030-30530-7_6

Don’t forget your roots: Constant-time root finding over F_2^m

Douglas Martins
, Gustavo Banegas
, Ricardo Custódio

Universidade Federal de Santa Catarina
Technical University of Eindhoven
Chalmers University of Technology

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

Abstract

In the last few years, post-quantum cryptography has received much attention. NIST is running a competition to select some post-quantum schemes as standard. As a consequence, implementations of post-quantum schemes have become important and with them side-channel attacks. In this paper, we show a timing attack on a code-based scheme which was submitted to the NIST competition. This timing attack recovers secret information because of a timing variance in finding roots in a polynomial. We present four algorithms to find roots that are protected against remote timing exploitation.

Original language	English
Title of host publication	Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings
Editors	Peter Schwabe, Nicolas Thériault
Publisher	Springer Verlag
Pages	109-129
Number of pages	21
ISBN (Print)	9783030305291
DOIs	https://doi.org/10.1007/978-3-030-30530-7_6
Publication status	Published - 1 Jan 2019
Externally published	Yes
Event	6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019 - Santiago de Chile, Chile Duration: 2 Oct 2019 → 4 Oct 2019

Publication series

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

Conference

Conference	6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019
Country/Territory	Chile
City	Santiago de Chile
Period	2/10/19 → 4/10/19

Keywords

Code-based cryptography
Post-quantum cryptography
Roots finding
Side-channel attack

Access to Document

10.1007/978-3-030-30530-7_6

Cite this

Martins, D., Banegas, G., & Custódio, R. (2019). Don’t forget your roots: Constant-time root finding over F_2^m. In P. Schwabe, & N. Thériault (Eds.), Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings (pp. 109-129). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11774 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-30530-7_6

Martins, Douglas ; Banegas, Gustavo ; Custódio, Ricardo. / Don’t forget your roots : Constant-time root finding over F_2^m. Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings. editor / Peter Schwabe ; Nicolas Thériault. Springer Verlag, 2019. pp. 109-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{846d1c9abba94e09acc682653926065d,

title = "Don{\textquoteright}t forget your roots: Constant-time root finding over F2m",

abstract = "In the last few years, post-quantum cryptography has received much attention. NIST is running a competition to select some post-quantum schemes as standard. As a consequence, implementations of post-quantum schemes have become important and with them side-channel attacks. In this paper, we show a timing attack on a code-based scheme which was submitted to the NIST competition. This timing attack recovers secret information because of a timing variance in finding roots in a polynomial. We present four algorithms to find roots that are protected against remote timing exploitation.",

keywords = "Code-based cryptography, Post-quantum cryptography, Roots finding, Side-channel attack",

author = "Douglas Martins and Gustavo Banegas and Ricardo Cust{\'o}dio",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019 ; Conference date: 02-10-2019 Through 04-10-2019",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-30530-7\_6",

language = "English",

isbn = "9783030305291",

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

publisher = "Springer Verlag",

pages = "109--129",

editor = "Peter Schwabe and Nicolas Th{\'e}riault",

booktitle = "Progress in Cryptology {\textendash} LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings",

}

Martins, D, Banegas, G & Custódio, R 2019, Don’t forget your roots: Constant-time root finding over F_2^m. in P Schwabe & N Thériault (eds), Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11774 LNCS, Springer Verlag, pp. 109-129, 6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019, Santiago de Chile, Chile, 2/10/19. https://doi.org/10.1007/978-3-030-30530-7_6

Don’t forget your roots: Constant-time root finding over F_2^m. / Martins, Douglas; Banegas, Gustavo; Custódio, Ricardo.
Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings. ed. / Peter Schwabe; Nicolas Thériault. Springer Verlag, 2019. p. 109-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11774 LNCS).

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

TY - GEN

T1 - Don’t forget your roots

T2 - 6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019

AU - Martins, Douglas

AU - Banegas, Gustavo

AU - Custódio, Ricardo

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2019.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - In the last few years, post-quantum cryptography has received much attention. NIST is running a competition to select some post-quantum schemes as standard. As a consequence, implementations of post-quantum schemes have become important and with them side-channel attacks. In this paper, we show a timing attack on a code-based scheme which was submitted to the NIST competition. This timing attack recovers secret information because of a timing variance in finding roots in a polynomial. We present four algorithms to find roots that are protected against remote timing exploitation.

AB - In the last few years, post-quantum cryptography has received much attention. NIST is running a competition to select some post-quantum schemes as standard. As a consequence, implementations of post-quantum schemes have become important and with them side-channel attacks. In this paper, we show a timing attack on a code-based scheme which was submitted to the NIST competition. This timing attack recovers secret information because of a timing variance in finding roots in a polynomial. We present four algorithms to find roots that are protected against remote timing exploitation.

KW - Code-based cryptography

KW - Post-quantum cryptography

KW - Roots finding

KW - Side-channel attack

UR - https://www.scopus.com/pages/publications/85072855552

U2 - 10.1007/978-3-030-30530-7_6

DO - 10.1007/978-3-030-30530-7_6

M3 - Conference contribution

AN - SCOPUS:85072855552

SN - 9783030305291

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

SP - 109

EP - 129

BT - Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings

A2 - Schwabe, Peter

A2 - Thériault, Nicolas

PB - Springer Verlag

Y2 - 2 October 2019 through 4 October 2019

ER -

Martins D, Banegas G, Custódio R. Don’t forget your roots: Constant-time root finding over F_2^m. In Schwabe P, Thériault N, editors, Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings. Springer Verlag. 2019. p. 109-129. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-30530-7_6