A graph-theoretic approach to analyzing decoding failures of BIKE

Published

October 25, 2024

Author(s)

Sarah Arpin, Tyler Raven Billingsley, Daniel Rayor Hast, Jun Bo Lau, Ray Perlner, Angela Robinson

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.

Citation

Cryptology ePrint Archive

Volume

2024

Pub Weblink

https://eprint.iacr.org/2024/1736

Pub Type

Websites

Download Paper

Local Download

Keywords

BIKE, error-correcting codes, McEliece, PQC, QC-MDPC

Citation

Arpin, S. , Billingsley, T. , Hast, D. , Lau, J. , Perlner, R. and Robinson, A. (2024), A graph-theoretic approach to analyzing decoding failures of BIKE, Cryptology ePrint Archive, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=958782, https://eprint.iacr.org/2024/1736 (Accessed December 13, 2024)