International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Yongcheng Song , State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China
Jiang Zhang , State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China
Xinyi Huang , Artificial Intelligence Thrust, Information Hub, The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, 511455, China
Wei Wu , College of Education Sciences, The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, 511455, China; School of Mathematics and Statistics, Fujian Normal University, Fuzhou, 350117, China
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
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.
BibTeX
@inproceedings{asiacrypt-2023-33513,
  title={Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes},
  publisher={Springer-Verlag},
  author={Yongcheng Song and Jiang Zhang and Xinyi Huang and Wei Wu},
  year=2023
}