Paper 2019/797

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

Douglas Martins, 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. Latincrypt 2019
Keywords
Side-channel AttackPost-quantum CryptographyCode-based CryptographyRoots findingConstant time
Contact author(s)
gustavo @ cryptme in
History
2019-07-14: received
Short URL
https://ia.cr/2019/797
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/797,
      author = {Douglas Martins and Gustavo Banegas and Ricardo Custodio},
      title = {Don't forget your roots: constant-time root finding over $\mathbb{F}_{2^m}$},
      howpublished = {Cryptology ePrint Archive, Paper 2019/797},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/797}},
      url = {https://eprint.iacr.org/2019/797}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.