Paper 2017/596

A Side-Channel Assisted Cryptanalytic Attack Against QcBits

Mélissa Rossi, Mike Hamburg, Michael Hutter, and Mark E. Marson

Abstract

QcBits is a code-based public key algorithm based on a problem thought to be resistant to quantum computer attacks. It is a constant time implementation for a quasi-cyclic moderate density parity check (QC-MDPC) Niederreiter encryption scheme, and has excellent performance and small key sizes. In this paper, we present a key recovery attack against QcBits. We first used differential power analysis (DPA) against the syndrome computation of the decoding algorithm to recover partial information about one half of the private key. We then used the recovered information to set up a system of noisy binary linear equations. Solving this system of equations gave us the entire key. Finally, we propose a simple but effective countermeasure against the power analysis used during the syndrome calculation.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CHES 2017
Keywords
QcBitsPost-quantum cryptographyMcElieceNiederreiterQC-MDPC codesSide-channel analysisDifferential power analysisNoisy binary linear equationsLearning parity with noise
Contact author(s)
melissa rossi @ ens fr
History
2017-10-11: revised
2017-06-21: received
See all versions
Short URL
https://ia.cr/2017/596
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/596,
      author = {Mélissa Rossi and Mike Hamburg and Michael Hutter and Mark E.  Marson},
      title = {A Side-Channel Assisted Cryptanalytic Attack Against QcBits},
      howpublished = {Cryptology ePrint Archive, Paper 2017/596},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/596}},
      url = {https://eprint.iacr.org/2017/596}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.