Paper 2017/1251

A toolbox for software optimization of QC-MDPC code-based cryptosystems

Nir Drucker and Shay Gueron

Abstract

The anticipated emergence of quantum computers in the foreseeable future drives the cryptographic community to start considering cryptosystems, which are based on problems that remain intractable even with strong quantum computers. One example is the family of code-based cryptosystems that relies on the Syndrome Decoding Problem (SDP). Recent work by Misoczki et al. [34] showed a variant of McEliece encryption which is based on Quasi Cyclic - Moderate Density Parity Check (MDPC) codes, and has significantly smaller keys than the original McEliece encryption. It was followed by the newly proposed QC-MDPC based cryptosystems CAKE [9] and Ouroboros [13]. These motivate dedicated new software optimizations. This paper lists the cryptographic primitives that QC-MDPC cryptosystems commonly employ, studies their software optimizations on modern processors, and reports the achieved speedups. It also assesses methods for side channel protection of the implementations, and their performance costs. These optimized primitives offer a useful toolbox that can be used, in various ways, by designers and implementers of QC-MDPC cryptosystems.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Code-based cryptosystemsMDPC
Contact author(s)
shay gueron @ gmail com
History
2017-12-30: received
Short URL
https://ia.cr/2017/1251
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1251,
      author = {Nir Drucker and Shay Gueron},
      title = {A toolbox for software optimization of QC-MDPC code-based cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1251},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1251}},
      url = {https://eprint.iacr.org/2017/1251}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.