Low Rank Parity Check Codes: New Decoding Algorithms and Applications to Cryptography

DOI10.1109/TIT.2019.2933535zbMATH Open1433.94152arXiv1904.00357OpenAlexW2967670694MaRDI QIDQ5211530FDOQ5211530

Authors: Nicolas Aragon, Adrien Hauteville, Olivier Ruatta, Gilles Zémor, Philippe Gaborit 

Publication date: 28 January 2020

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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 $frac23(n-k)$ when the previous decoding algorithm only decodes up to $fracn-k2$ errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to $fracn-k2$. 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.

Full work available at URL: https://arxiv.org/abs/1904.00357

Mathematics Subject Classification ID

Cryptography (94A60) Decoding (94B35)

Cited In (16)

• Title not available (Why is that?)
• Constructions of optimal rank-metric codes from automorphisms of rational function fields
• Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme
• Low-rank parity-check codes over Galois rings
• On the rank decoding problem over finite principal ideal rings
• An upper-bound on the decoding failure probability of the LRPC decoder
• Blockwise rank decoding problem and LRPC codes: cryptosystems with smaller sizes
• Cryptanalysis of the rank preserving signature
• Injective rank metric trapdoor functions with homogeneous errors
• LRPC codes with multiple syndromes: near ideal-size KEMs without ideals
• Generalization of low rank parity-check (LRPC) codes over the ring of integers modulo a positive integer
• Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
• LowMS: a new rank metric code-based KEM without ideal structure
• Rank-metric codes and their applications
• An analysis of the RankSign signature scheme with rank multipliers
• Hardness estimates of the code equivalence problem in the rank metric

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)