Paper 2023/1387

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

Yongcheng Song
Jiang Zhang
Xinyi Huang
Wei Wu
Abstract

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: Updated and Improved parameters in Tables (1, 3 - 7)

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Keywords
Post-Quantum CryptographyNIST PQC CandidatesRank Metric Code-Based CryptographyRank Decoding ProblemLRPC Codes
Contact author(s)
yongchengsong @ outlook com
jiangzhang09 @ gmail com
xinyi @ ust hk
serenaweiwu @ hkust-gz edu cn
History
2023-12-18: revised
2023-09-17: received
See all versions
Short URL
https://ia.cr/2023/1387
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2023/1387,
      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},
      url = {https://eprint.iacr.org/2023/1387}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.