Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A BKW-Style Solver for the Restricted Syndrome Decoding Problem

Nguyen, Vu LU orcid ; Johansson, Thomas LU orcid and Guo, Qian LU (2025)
Abstract
The Restricted Syndrome Decoding Problem (RSDP) is a variant of the well-known syndrome decoding problem. It has been recently 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 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.... (More)
The Restricted Syndrome Decoding Problem (RSDP) is a variant of the well-known syndrome decoding problem. It has been recently 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 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. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Other contribution
publication status
unpublished
subject
pages
28 pages
language
English
LU publication?
yes
id
80f45996-880a-43c5-b9ce-d267a4a9cfe2
date added to LUP
2025-04-22 12:12:15
date last changed
2025-05-05 13:34:52
@misc{80f45996-880a-43c5-b9ce-d267a4a9cfe2,
  abstract     = {{The Restricted Syndrome Decoding Problem (RSDP) is a variant of the well-known syndrome decoding problem. It has been recently 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 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.}},
  author       = {{Nguyen, Vu and Johansson, Thomas and Guo, Qian}},
  language     = {{eng}},
  title        = {{A BKW-Style Solver for the Restricted Syndrome Decoding Problem}},
  year         = {{2025}},
}