International Association for Cryptologic Research

International Association
for Cryptologic Research

Transactions on Cryptographic Hardware and Embedded Systems, Volume 2022

Faster constant-time decoder for MDPC codes and applications to BIKE KEM


Thales Paiva
University of Sao Paulo

Routo Terada
University of Sao Paulo


Keywords: Post-quantum Cryptography, BIKE, MDPC, LDPC, Constant-time Decoding


Abstract

BIKE is a code-based key encapsulation mechanism (KEM) that was recently selected as an alternate candidate by the NIST’s standardization process on post-quantum cryptography. This KEM is based on the Niederreiter scheme instantiated with QC-MDPC codes, and it uses the BGF decoder for key decapsulation. We discovered important limitations of BGF that we describe in detail, and then we propose a new decoding algorithm for QC-MDPC codes called PickyFix. Our decoder uses two auxiliary iterations that are significantly different from previous approaches and we show how they can be implemented efficiently. We analyze our decoder with respect to both its error correction capacity and its performance in practice. When compared to BGF, our constant-time implementation of PickyFix achieves speedups of 1.18, 1.29, and 1.47 for the security levels 128, 192 and 256, respectively.

Publication

Transactions of Cryptographic Hardware and Embedded Systems, Volume 2022, Issue 4

Paper

Artifact

Artifact number
tches/2022/a22

Artifact published
October 31, 2022

README

ZIP (8 MB)  

View on Github

License


BibTeX How to cite

Paiva, T. B., & Terada, R. (2022). Faster Constant-Time Decoder for MDPC Codes and Applications to BIKE KEM. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(4), 110–134. https://doi.org/10.46586/tches.v2022.i4.110-134. Artifact available at https://artifacts.iacr.org/tches/2022/a22