Paper 2024/076

A provably masked implementation of BIKE Key Encapsulation Mechanism

Loïc Demange, French Institute for Research in Computer Science and Automation, Thales (France)
Mélissa Rossi, ANSSI
Abstract

BIKE is a post-quantum key encapsulation mechanism (KEM) selected for the 4th round of the NIST’s standardization campaign. It relies on the hardness of the syndrome decoding problem for quasi-cyclic codes and on the indistinguishability of the public key from a random element, and provides the most competitive performance among round 4 candidates, which makes it relevant for future real-world use cases. Analyzing its side-channel resistance has been highly encouraged by the community and several works have already outlined various side-channel weaknesses and proposed ad-hoc countermeasures. However, in contrast to the well-documented research line on masking lattice-based algorithms, the possibility of generically protecting code-based algorithms by masking has only been marginally studied in a 2016 paper by Cong Chen et al. At this stage of the standardization campaign, it is important to assess the possibility of fully masking BIKE scheme and the resulting cost in terms of performances. In this work, we provide the first high-order masked implementation of a code-based algorithm. We had to tackle many issues such as finding proper ways to handle large sparse polynomials, masking the key-generation algorithm or keeping the benefit of the bitslicing. In this paper, we present all the gadgets necessary to provide a fully masked implementation of BIKE, we discuss our different implementation choices and we propose a full proof of masking in the Ishai Sahai and Wagner (Crypto 2003) model. More practically, we also provide an open C-code masked implementation of the key-generation, encapsulation and decapsulation algorithms with extensive benchmarks. While the obtained performance is slower than existing masked lattice-based algorithms, the scaling in the masking order is still encouraging and no Boolean to Arithmetic conversion has been used. We hope that this work can be a starting point for future analysis and optimization.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Communications in Cryptology
DOI
10.62056/aesgvua5v
Keywords
BIKEPQCSide-Channel countermeasureProvable high-order maskingd-probing model
Contact author(s)
ldemange-research @ etik com
melissa rossi @ ssi gouv fr
History
2024-05-07: last of 2 revisions
2024-01-17: received
See all versions
Short URL
https://ia.cr/2024/076
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/076,
      author = {Loïc Demange and Mélissa Rossi},
      title = {A provably masked implementation of {BIKE} Key Encapsulation Mechanism},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/076},
      year = {2024},
      doi = {10.62056/aesgvua5v},
      url = {https://eprint.iacr.org/2024/076}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.