Paper 2025/2221 Original: eprint.iacr.org/2025/2221 ↗

Sparse Vector Reconstruction from Distance Spectrum using Soft Information

Abstract

QC-MDPC based schemes feature secret sparse binary vectors in a cyclic polynomial ring. When those vectors are sparse enough, they can be reconstructed from their distance spectrum, that is the set of all distances between the coordinates of the non-zero coefficients. In this work, we revisit the reconstruction algorithms and we explore to what extent a secret sparse vector can be recovered from a partial knowledge of its distance spectrum. In particular, we show how to efficiently use reliability (soft information) in the reconstruction process. Another aspect of this work is to investigate which kind of side-channel leaks information about the distance spectrum and to understand the models that enable us to quantify the reliability on leaking data depending on the amount of side-channel observations (or queries). For instance, we show that for BIKE level 1, assuming that a side-channel leaks information about the syndrome weight, using soft information in the reconstruction process reduces the number of queries by a factor 10. Our technique can also be applied to HQC, which also features sparse secret vector, with similar figures, assuming there exists a side-channel leaking relevant information, the error weight in the case of HQC.