# Introducing Arithmetic Failures to Accelerate QC-MDPC Code-Based Cryptography

**Antonio Guimarães**, Edson Borin, Diego F. Aranha

*Code-Based Cryptography Workshop (CBC 2019), Darmstadt. Springer LNCS, pp. 44–68* (workshop, 2019).

Links: [DOI](https://doi.org/10.1007/978-3-030-25922-8_3) · [Code](https://github.com/antoniocgj/Optimized-implementation-of-QC-MDPC-code-based-cryptography) · [BibTeX](https://antonioguimaraes.org/publications/qc-mdpc-arithmetic-failures/cite.bib)

Canonical page: https://antonioguimaraes.org/publications/qc-mdpc-arithmetic-failures/

## Abstract

In this work, we optimize the performance of QC-MDPC code-based cryptosystems through the insertion of configurable failure rates in their arithmetic procedures. We present constant time algorithms with a configurable failure rate for multiplication and inversion over binary polynomials, the two most expensive subroutines used in QC-MDPC implementations. Using a failure rate negligible compared to the security level ($2^{-128}$), our multiplication is 2 times faster than NTL on sparse polynomials and 1.6 times faster than a naive constant-time sparse polynomial multiplication. Our inversion algorithm, based on Wu et al., is 2 times faster than the original algorithm and 12 times faster than Itoh-Tsujii using the same modulus polynomial ($x^{32749} - 1$). By inserting these algorithms in a version of QcBits at the 128-bit quantum security level, we were able to achieve a speedup of 1.9 on the key generation and up to 1.4 on the decryption time. Comparing with variant 2 of the BIKE suite, which also implements the Niederreiter Cryptosystem using QC-MDPC codes, our final version of QcBits performs the uniform decryption 2.7 times faster.

## BibTeX

```bibtex
@inproceedings{guimaraes2019introducing,
  author    = {Antonio Guimarães and Edson Borin and Diego F. Aranha},
  title     = {{Introducing Arithmetic Failures to Accelerate QC-MDPC Code-Based Cryptography}},
  booktitle = {Code-Based Cryptography Workshop (CBC 2019), Darmstadt. Springer LNCS, pp. 44–68},
  year      = {2019},
  doi       = {10.1007/978-3-030-25922-8_3},
  url       = {https://doi.org/10.1007/978-3-030-25922-8_3}
}
```

Topics: Post-quantum cryptography, Efficient implementation