Paper 2024/1736
A graph-theoretic approach to analyzing decoding failures of BIKE
Abstract
We present experimental findings on the decoding failure rate (DFR) of BIKE, a fourth-round candidate in the NIST Post-Quantum Standardization process, at the 20-bit security level using graph-theoretic approaches. We select parameters according to BIKE design principles and conduct a series of experiments using Rust to generate significantly more decoding failure instances than in prior work using SageMath. For each decoding failure, we study the internal state of the decoder at each iteration and find that for 97% of decoding failures at block size $r=587$, the decoder reaches a fixed point within 7 iterations. We then consider the corresponding Tanner graphs of each decoding failure instance to determine whether the decoding failures are due to absorbing sets. We find that 81% of decoding failures at $r=587$ were caused by absorbing sets, and of these the majority were $(d,d)$-near codewords.
Note: A version of this extended abstract was submitted to PQCrypto 2023 and withdrawn pending further work. We have added only figures and brief clarifying points.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- qc-mdpccoding theorybike
- Contact author(s)
- sarpin @ vt edu
- History
- 2024-10-25: approved
- 2024-10-23: received
- See all versions
- Short URL
- https://ia.cr/2024/1736
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1736,
author = {Sarah Arpin and Tyler Raven Billingsley and Daniel Rayor Hast and Jun Bo Lau and Ray Perlner and Angela Robinson},
title = {A graph-theoretic approach to analyzing decoding failures of {BIKE}},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1736},
year = {2024},
url = {https://eprint.iacr.org/2024/1736}
}