A BKW-style solver for the restricted syndrome decoding problem
Open Access
- 23 July 2026
- journal article
- research article
- Published by Springer Nature in Cryptography and Communications
- Vol. 18 (5) , 1735-1762
Abstract
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 $$\mathbb {F}_{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.
Keywords
All Related Versions
Funding Information
- Excellence Center at Linköping – Lund in Information Technology (Grant number)
- Knut och Alice Wallenbergs Stiftelse (Grant number)
- Vetenskapsrådet (Grant number)
This publication has 28 references indexed in Scilit:
- Short Signatures from Regular Syndrome Decoding in the Head2023
- A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions2023
- Statistical Decoding 2.0: Reducing Decoding to LPN2022
- PKP-Based Signature Scheme2019
- An Improved LPN Algorithm2006
- A Family of Fast Syndrome Based Cryptographic Hash Functions2005
- How to Achieve a McEliece-Based Digital Signature Scheme2001
- An Efficient Identification Scheme Based on Permuted Kernels (extended abstract)2001
- An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding1996
- A new identification scheme based on syndrome decoding1994