In 2012, Misoczki, Tillich, Sendrier, and Barreto proposed to use quasi-cyclic moderate-density-parity-check (QC-MDPC) codes for the McEliece encryption system. The main benefit of using QC-MDPC code is that it allows small key-sizes: public keys take only 0.6 KB for 80-bit security and 1.2 KB for 128-bit security. Since then, several implementation papers have been published. However, almost none of them addresses the issue of timing attacks.

This webpage is dedicated for QcBits (pronounced "quick-bits"), a fully constant-time implementation of a QC-MDPC-code-based encryption scheme. Decryption takes 14,679,937 Cortex-M4 cycles using the implementation, while the PQCrypto 2016 paper "IND-CCA Secure Hybrid Encryption from QC-MDPC Niederreiter" reports 18,416,012 (non-constant-time) cycles. Regarding higher-end CPUs, decryption takes only 1,560,072 Haswell cycles, while the previous (non-constant-time) record was 3,104,624 cycles. Such speed is achieved by combination of two techiniques: 1) performing each polynomial multiplication in F2[x]/(xn-1) and Z[x]/(xn-1) using a sequence of constant-time "rotations" and 2) bitslicing.


The current code for implementations "ref" and "clmul" can be found here. The code is in the public domain.


The slides for CHES 2016 is available here.


The paper is available here.