A BKW-Style Solver for the Restricted Syndrome Decoding Problem

The Restricted Syndrome Decoding Problem (RSDP) is a variant of the well-known syndrome decoding problem. It has recently been turned into a post-quantum signature scheme named CROSS by Baldi et al.. It is a scheme highlighted for being computationally friendly and providing a compact signature and public key size. This paper investigates an Oracle-based definition of the RSDP that has already proved useful in constructing other cryptographic primitives. We propose a new solving algorithm for this novel and interesting problem. Our approach is to first introduce a new weight definition for vectors over $\ffield{p}$ and then develop a solving algorithm similar to the BKW algorithm that includes finding many such low-weight vectors in a dual space. We make use of several advanced techniques, such as Covering codes and Subspace Hypothesis Testing . We show that when there are many samples, our algorithm can be more advantageous than prior work based on information-set decoding adaptations for RSDP or algebraic approaches.