Cryptology ePrint Archive: Report 2017/596
A Side-Channel Assisted Cryptanalytic Attack Against QcBits
Mélissa Rossi and Mike Hamburg and 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.
Category / Keywords: QcBits, Post-quantum cryptography, McEliece, Niederreiter, QC-MDPC codes, Side-channel analysis, Differential power analysis, Noisy binary linear equations, Learning parity with noise
Original Publication (in the same form): IACR-CHES-2017
Date: received 20 Jun 2017, last revised 11 Oct 2017
Contact author: melissa rossi at ens fr
Available format(s): PDF | BibTeX Citation
Version: 20171011:082416 (All versions of this report)
Short URL: ia.cr/2017/596
[ Cryptology ePrint archive ]