Guided syndrome decoding under posterior leakage

The syndrome decoding problem (SDP) is the computational foundation of code-based cryptography, underlying schemes such as McEliece, Niederreiter, and the Hamming quasi-cyclic key encapsulation mechanism standardized in 2025. While these constructions are secure in the standard model, practical implementations may still leak partial information about secret error vectors through physical attacks such as cold boot attacks and related side-channel scenarios. Motivated by this setting, we study syndrome decoding in the presence of probabilistic leakage. We adopt a bitwise Bayesian leakage model (BBLM) that represents leakage as coordinate-wise posterior beliefs over the secret error vector, providing a generic abstraction for noisy bitwise leakage. Building on this model, we develop a posterior-guided decoding framework that integrates leakage-derived information directly into the information set decoding (ISD) process through conditioned decoding and recursive instance reduction. The framework is decoder-agnostic and can be combined with different ISD variants and subset-enumeration strategies. As a proof of concept, we instantiate the framework using a genetic-algorithm-based enumerator guided by posterior-informed fitness functions. Experimental results on random linear codes and Reed–Muller (RM) codes show that informative leakage can guide subset selection toward conditioned instances that are substantially easier to decode under realistic asymmetric noise conditions.