Cryptology ePrint Archive: Report 2019/155

Constant-time BCH Error-Correcting Code

Matthew Walters and Sujoy Sinha Roy

Abstract: Error-correcting codes can be useful in reducing decryption failure rate of several lattice-based and code-based public-key encryption schemes. Two schemes, namely LAC and HQC, in NIST’s round 2 phase of its post-quantum cryptography standardisation project use the strong error-correcting BCH code. However, direct application of the BCH code in decryption algorithms of public-key schemes could open new avenues to the attacks. For example, a recent attack exploited non-constant-time execution of BCH code to reduce the security of LAC.

In this paper we analyse the BCH error-correcting code, identify computation steps that cause timing variations and design the first constant-time BCH algorithm. We implement our algorithm in software and evaluate its resistance against timing attacks by performing leakage detection tests. To study the computational overhead of the countermeasures, we integrated our constant-time BCH code in the reference and optimised implementations of the LAC scheme as a case study, and observed nearly 1.1 and 1.4 factor slowdown respectively for the CCA-secure primitives

Category / Keywords: public-key cryptography / Post-quantum cryptography, Decryption failures, Error-correcting codes, Constant-time implementation

Date: received 13 Feb 2019, last revised 16 Apr 2019

Contact author: mjw553 at cs bham ac uk, s sinharoy at cs bham ac uk

Available format(s): PDF | BibTeX Citation

Note: Minor efficiency improvements and algorithm correcting

Version: 20190416:122845 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]