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.