2019/03/31 by Nicolas Aragon, Philippe Gaborit, Aragon, Nicolas +7 · 1 citation
Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding #Cryptography and Security (cs.CR) #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1904.00357
openalex publication_date 2019/03/31 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
We introduce a new family of rank metric codes: Low Rank Parity Check codes\n(LRPC), for which we propose an efficient probabilistic decoding algorithm.\nThis family of codes can be seen as the equivalent of classical LDPC codes for\nthe rank metric. We then use these codes to design cryptosystems `a la\nMcEliece: more precisely we propose two schemes for key encapsulation mechanism\n(KEM) and public key encryption (PKE). Unlike rank metric codes used in\n previous encryption algorithms -notably Gabidulin codes - LRPC codes have a\nvery weak algebraic structure. Our cryptosystems can be seen as an equivalent\nof the NTRU cryptosystem (and also to the more recent MDPC citeMTSB12\ncryptosystem) in a rank metric context. The present paper is an extended\nversion of the article introducing LRPC codes, with important new\ncontributions. We have improved the decoder thanks to a new approach which\nallows for decoding of errors of higher rank weight, namely up to\n\(2)/(3)(n-k) when the previous decoding algorithm only decodes up to\n\(n-k)/(2) errors. Our codes therefore outperform the classical Gabidulin\ncode decoder which deals with weights up to \(n-k)/(2). This comes at the\nexpense of probabilistic decoding, but the decoding error probability can be\nmade arbitrarily small. The new approach can also be used to decrease the\ndecoding error probability of previous schemes, which is especially useful for\ncryptography. Finally, we introduce ideal rank codes, which generalize\ndouble-circulant rank codes and allow us to avoid known structural attacks\nbased on folding. To conclude, we propose different parameter sizes for our\nschemes and we obtain a public key of 3337 bits for key exchange and 5893 bits\nfor public key encryption, both for 128 bits of security.\n