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

Departamento de Informática e Estatística
Universidade Federal de Santa Catarina
Technical University of Eindhoven
Chalmers University of Technology

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings
rédacteurs en chef	Peter Schwabe, Nicolas Thériault
Editeur	Springer Verlag
Pages	109-129
Nombre de pages	21
ISBN (imprimé)	9783030305291
Les DOIs	https://doi.org/10.1007/978-3-030-30530-7_6
état	Publié - 1 janv. 2019
Modification externe	Oui
Evénement	6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019 - Santiago de Chile, Chili Durée: 2 oct. 2019 → 4 oct. 2019

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11774 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019
Pays/Territoire	Chili
La ville	Santiago de Chile
période	2/10/19 → 4/10/19

Accès au document

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

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

Martins, D., Banegas, G., & Custódio, R. (2019). Don’t forget your roots: Constant-time root finding over F_2^m. Dans P. Schwabe, & N. Thériault (eds.), Progress in Cryptology – LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Proceedings (p. 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. Editeur / 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)).

@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. Dans 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, p. 109-129, 6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019, Santiago de Chile, Chili, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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. Dans Schwabe P, Thériault N, rédacteurs en chef, 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