International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Faster Constant-Time Decoder for MDPC Codes and Applications to BIKE KEM

Authors:
Thales B. Paiva , University of Sao Paulo, Sao Paulo, Brazil
Routo Terada , University of Sao Paulo, Sao Paulo, Brazil
Download:
DOI: 10.46586/tches.v2022.i4.110-134
URL: https://tches.iacr.org/index.php/TCHES/article/view/9815
Search ePrint
Search Google
Presentation: Slides
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.
BibTeX
@article{tches-2022-32358,
  title={Faster Constant-Time Decoder for MDPC Codes and Applications to BIKE KEM},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 4},
  pages={110-134},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9815},
  doi={10.46586/tches.v2022.i4.110-134},
  author={Thales B. Paiva and Routo Terada},
  year=2022
}