Paper 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
Note: Minor efficiency improvements and algorithm correcting
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Post-quantum cryptographyDecryption failuresError-correcting codesConstant-time implementation
- Contact author(s)
-
mjw553 @ cs bham ac uk
s sinharoy @ cs bham ac uk - History
- 2019-04-16: last of 4 revisions
- 2019-02-20: received
- See all versions
- Short URL
- https://ia.cr/2019/155
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/155,
author = {Matthew Walters and Sujoy Sinha Roy},
title = {Constant-time {BCH} Error-Correcting Code},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/155},
year = {2019},
url = {https://eprint.iacr.org/2019/155}
}
