Cryptology ePrint Archive: Report 2019/797

Don't forget your roots: constant-time root finding over $\mathbb{F}_{2^m}$

Douglas Martins and Gustavo Banegas and Ricardo Custodio

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.

Category / Keywords: implementation / Side-channel Attack, Post-quantum Cryptography, Code-based Cryptography, Roots finding, Constant time

Original Publication (with minor differences): Latincrypt 2019

Date: received 9 Jul 2019

Contact author: gustavo at cryptme in

Available format(s): PDF | BibTeX Citation

Version: 20190714:154706 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]