Welcome to the resource topic for 2023/1387
Title:
Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes
Authors: 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.
ePrint: https://eprint.iacr.org/2023/1387
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .