Scholarlink

<p>The regular decoding problem asks for (the existence of) regular solutions to a syndrome decoding problem (SDP). This problem has increased applications in post-quantum cryptography and cryptanalysis. Recently, Esser and Santini explored in depth the connection between the regular (RSD) and classical syndrome decoding problems. They have observed that while RSD to SDP reductions are known (in any parametric regime), a similar generic reduction from SDP to RSD is not known. In our contribution, we examine two different generic polynomial reductions from a syndrome decoding problem to a regular decoding problem instance. The first reduction is based on constructing a special parity check matrix that encodes weight counter progression inside the parity check matrix, which is then the input of the regular decoding oracle. The target regular decoding problem has a significantly longer code length, that depends linearly on the weight parameter of the original SDP. The second reduction is based on translating the SDP to a non-linear system of equations in the Multiple Right-Hand Sides form, and then applying RSD oracle to solve this system. The second reduction has better code length. The ratio between RSD and SDP code length of the second reduction can be bounded by a constant (less than 8).</p>

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

Polynomial reduction from syndrome decoding problem to regular decoding problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年1月28日

查看全文
  • Pavol Zajac

摘要

The regular decoding problem asks for (the existence of) regular solutions to a syndrome decoding problem (SDP). This problem has increased applications in post-quantum cryptography and cryptanalysis. Recently, Esser and Santini explored in depth the connection between the regular (RSD) and classical syndrome decoding problems. They have observed that while RSD to SDP reductions are known (in any parametric regime), a similar generic reduction from SDP to RSD is not known. In our contribution, we examine two different generic polynomial reductions from a syndrome decoding problem to a regular decoding problem instance. The first reduction is based on constructing a special parity check matrix that encodes weight counter progression inside the parity check matrix, which is then the input of the regular decoding oracle. The target regular decoding problem has a significantly longer code length, that depends linearly on the weight parameter of the original SDP. The second reduction is based on translating the SDP to a non-linear system of equations in the Multiple Right-Hand Sides form, and then applying RSD oracle to solve this system. The second reduction has better code length. The ratio between RSD and SDP code length of the second reduction can be bounded by a constant (less than 8).