Paper 2021/1631

Secure Sampling of Constant-Weight Words – Application to BIKE

Nicolas Sendrier, Inria

The pseudorandom sampling of constant weight words, as it is currently implemented in cryptographic schemes like BIKE or HQC, is prone to the leakage of information on the seed being used for the pseudorandom number generation. This creates a vulnerability when the semantic security conversion requires a deterministic re-encryption. This observation was first made in [HLS21] about HQC and a timing attack was presented to recover the secret key. As suggested in [HLS21] a similar attack applies to BIKE and instances of such an attack were presented in an earlier version of this work [Sen21] and independently in [GHJ+22]. The timing attack stems from the variation of the amount of pseudorandom data to draw and process for sampling uniformly a constant weight word. We give here the exact distribution of this amount for BIKE. This will allow us to estimate precisely the cost of the natural countermeasure which consists in drawing always the same (large enough) amount of randomness for the sampler to terminate with probability overwhelmingly close to one. The main contribution of this work is to suggest a new approach for fixing the issue. It is first remarked that, contrary to what is done currently, the sampling of constant weight words doesn't need to produce a uniformly distributed output. If the distribution is close to uniform in the appropriate metric, the impact on security is negligible. Also, a new variant of the Fisher-Yates shuffle is proposed which is (1) very well suited for secure implementations against timing and cache attacks, and (2) produces constant weight words with a distribution close enough to uniform.

Available format(s)
Public-key cryptography
Publication info
BIKEtiming attackconstant-weight words
Contact author(s)
nicolas sendrier @ inria fr
2023-08-22: last of 2 revisions
2021-12-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Sendrier},
      title = {Secure Sampling of Constant-Weight Words – Application to {BIKE}},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1631},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.