Constant-Time BCH Error-Correcting Code
Matthew Walters, Sujoy Sinha Roy · 2020
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 [1] 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 a constant-time BCH implementation. 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.