Low Rank Parity Check Codes: New Decoding Algorithms and Applications to Cryptography
From MaRDI portal
Abstract: We introduce a new family of rank metric codes: Low Rank Parity Check codes (LRPC), for which we propose an efficient probabilistic decoding algorithm. This family of codes can be seen as the equivalent of classical LDPC codes for the rank metric. We then use these codes to design cryptosystems `a la McEliece: more precisely we propose two schemes for key encapsulation mechanism (KEM) and public key encryption (PKE). Unlike rank metric codes used in previous encryption algorithms -notably Gabidulin codes - LRPC codes have a very weak algebraic structure. Our cryptosystems can be seen as an equivalent of the NTRU cryptosystem (and also to the more recent MDPC cite{MTSB12} cryptosystem) in a rank metric context. The present paper is an extended version of the article introducing LRPC codes, with important new contributions. We have improved the decoder thanks to a new approach which allows for decoding of errors of higher rank weight, namely up to when the previous decoding algorithm only decodes up to errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to . This comes at the expense of probabilistic decoding, but the decoding error probability can be made arbitrarily small. The new approach can also be used to decrease the decoding error probability of previous schemes, which is especially useful for cryptography. Finally, we introduce ideal rank codes, which generalize double-circulant rank codes and allow us to avoid known structural attacks based on folding. To conclude, we propose different parameter sizes for our schemes and we obtain a public key of 3337 bits for key exchange and 5893 bits for public key encryption, both for 128 bits of security.
Cited in
(22)- Generalization of low rank parity-check (LRPC) codes over the ring of integers modulo a positive integer
- Cryptanalysis of the rank preserving signature
- Low-rank parity-check codes over Galois rings
- scientific article; zbMATH DE number 2154506 (Why is no real title available?)
- Rank-metric codes and their applications
- Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
- LRPC codes with multiple syndromes: near ideal-size KEMs without ideals
- Constructions of optimal rank-metric codes from automorphisms of rational function fields
- Hardness estimates of the code equivalence problem in the rank metric
- Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme
- LowMS: a new rank metric code-based KEM without ideal structure
- An analysis of the RankSign signature scheme with rank multipliers
- On the rank decoding problem over finite principal ideal rings
- Blockwise rank decoding problem and LRPC codes: cryptosystems with smaller sizes
- An upper-bound on the decoding failure probability of the LRPC decoder
- Injective rank metric trapdoor functions with homogeneous errors
- Generalizing the Augot-Finiasz PKE to other code classes
- Low-rank parity-check codes over finite commutative rings
- Somewhat homomorphic encryption based on random codes
- A digital signature scheme based on the vector space factorization problem and the MPC-in-the-head paradigm
- MacWilliams duality for rank metric codes over finite chain rings
- The blockwise rank syndrome learning problem and its applications to cryptography
This page was built for publication: Low Rank Parity Check Codes: New Decoding Algorithms and Applications to Cryptography
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211530)
