Paper 2023/1387

Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes

Yongcheng Song
Jiang Zhang
Xinyi Huang
Wei Wu

In this paper, we initiate the study of the Rank Decoding (RD) problem and LRPC codes with blockwise structures in rank-based cryptosystems. First, we introduce the blockwise errors ($\ell$-errors) where each error consists of $\ell$ blocks of coordinates with disjoint supports, and define the blockwise RD ($\ell$-RD) problem as a natural generalization of the RD problem whose solutions are $\ell$-errors (note that the standard RD problem is actually a special $\ell$-RD problem with $\ell=1$). We adapt the typical attacks on the RD problem to the $\ell$-RD problem, and find that the blockwise structures do not ease the problem too much: the $\ell$-RD problem is still exponentially hard for appropriate choices of $\ell>1$. Second, we introduce blockwise LRPC ($\ell$-LRPC) codes as generalizations of the standard LPRC codes whose parity-check matrices can be divided into $\ell$ sub-matrices with disjoint supports, i.e., the intersection of two subspaces generated by the entries of any two sub-matrices is a null space, and investigate the decoding algorithms for $\ell$-errors. We find that the gain of using $\ell$-errors in decoding capacity outweighs the complexity loss in solving the $\ell$-RD problem, which makes it possible to design more efficient rank-based cryptosystems with flexible choices of parameters. As an application, we show that the two rank-based cryptosystems submitted to the NIST PQC competition, namely, RQC and ROLLO, can be greatly improved by using the ideal variants of the $\ell$-RD problem and $\ell$-LRPC codes. Concretely, for 128-bit security, our RQC has total public key and ciphertext sizes of 2.5 KB, which is not only about 50% more compact than the original RQC, but also smaller than the NIST Round 4 code-based submissions HQC, BIKE, and Classic McEliece.

Note: Accepted by ASIACRYPT 2023

Available format(s)
Public-key cryptography
Publication info
Post-Quantum CryptographyNIST PQC CandidatesRank Metric Code-Based CryptographyRank Decoding ProblemLRPC Codes
Contact author(s)
yongchengsong @ outlook com
jiangzhang09 @ gmail com
xinyi @ ust hk
weiwu @ fjnu edu cn
2023-09-18: approved
2023-09-17: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Yongcheng Song and Jiang Zhang and Xinyi Huang and Wei Wu},
      title = {Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1387},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.