QcBits : constant-time small-key code-based cryptography

This paper introduces a constant-time implementation for a quasi-cyclic moderate-density-parity-check (QC-MDPC) code based encryption scheme. At a 280 security level, the software takes 14 679 937 Cortex-M4 and 1 560 072 Haswell cycles to decrypt a short message, while the previous records were 18 416 012 and 3 104 624 (non-constant-time) cycles. Such speed is achieved by combining two techniques: 1) performing each polynomial multiplication in F2[x]/(xr − 1) and Z[x]/(xr − 1) using a sequence of “constant-time rotations” and 2) bitslicing.