Cryptology ePrint Archive: Report 2019/150

QcBits: Constant-Time Small-Key Code-Based Cryptography

Tung Chou

Abstract: This paper introduces a constant-time implementation for a quasi-cyclic moderate-density-parity-check (QC-MDPC) code based encryption scheme. At a $2^{80}$ security level, the software takes 14679937 Cortex-M4 and 1560072 Haswell cycles to decrypt a short message, while the previous records were 18416012 and 3104624 (non-constant-time) cycles. Such speed is achieved by combining two techniques: 1) performing each polynomial multiplication in $\mathbb{F}_2[x]/(x^r-1)$ and $\mathbb{Z}[x]/(x^r-1)$ using a sequence of constant-time rotations'' and 2) bitslicing.

Category / Keywords: implementation / McEliece, Niederreiter, QC-MDPC codes, bitslicing, software implementation

Original Publication (in the same form): IACR-CHES-2016
DOI:
10.1007/978-3-662-53140-2_14