Scholarlink

Code-based cryptosystem (CBC) is one of the candidates for post-quantum cryptosystems (PQCs). Its security is primarily based on the syndrome decoding problem (SDP). In this paper, we focus on the rank CBC, whose security relies on the rank SDP. The Gaborit–Ruatta–Schrek (GRS) algorithm is well known as the current best decoding algorithm for the rank SDP. Therefore, we propose the quantum version of the GRS algorithm. Then, we introduce an attack strategy using this quantum algorithm for the previous rank CBCs that remained at the 2nd Round of the NIST’s PQC standardization project and consider the quantum security for those cryptosystems. We present results that according to the currently recommended key-size parameter, our approach does not threaten the security of ROLLO, but that it is effective and can be a threat to the RQC encryption scheme. Then, we give new RQC instances that are secure against such an attack.

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

Proposal for Quantum GRS Algorithm and Cryptanalysis for ROLLO and RQC

  • 章节

  • 出版模式：

    开放获取

  • 发表日期：

    2026年

查看全文
  • Asuka Wakasugi,
  • Mitsuru Tada

摘要

Code-based cryptosystem (CBC) is one of the candidates for post-quantum cryptosystems (PQCs). Its security is primarily based on the syndrome decoding problem (SDP). In this paper, we focus on the rank CBC, whose security relies on the rank SDP. The Gaborit–Ruatta–Schrek (GRS) algorithm is well known as the current best decoding algorithm for the rank SDP. Therefore, we propose the quantum version of the GRS algorithm. Then, we introduce an attack strategy using this quantum algorithm for the previous rank CBCs that remained at the 2nd Round of the NIST’s PQC standardization project and consider the quantum security for those cryptosystems. We present results that according to the currently recommended key-size parameter, our approach does not threaten the security of ROLLO, but that it is effective and can be a threat to the RQC encryption scheme. Then, we give new RQC instances that are secure against such an attack.