Paper 2023/1387
Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes
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)
- 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
-
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} }