Scholarlink

<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathbb {F}_{p}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation> 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 <i>Covering codes</i> and <i>Subspace Hypothesis Testing</i>. 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A BKW-style solver for the restricted syndrome decoding problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月23日

查看全文
  • Thomas Johansson,
  • Qian Guo,
  • Vu Nguyen

摘要

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}\) 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.