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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2019/155}},
      url = {https://eprint.iacr.org/2019/155}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.