Paper 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in Ches 2016
DOI
10.1007/978-3-662-53140-2_14
Keywords
McElieceNiederreiterQC-MDPC codesbitslicingsoftware implementation
Contact author(s)
blueprint @ crypto tw
History
2019-02-20: received
Short URL
https://ia.cr/2019/150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/150,
      author = {Tung Chou},
      title = {QcBits: Constant-Time Small-Key Code-Based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2019/150},
      year = {2019},
      doi = {10.1007/978-3-662-53140-2_14},
      note = {\url{https://eprint.iacr.org/2019/150}},
      url = {https://eprint.iacr.org/2019/150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.