Low-rank parity-check (LRPC) code

Low-rank parity-check (LRPC) code[1]

Description

An LRPC code of rank \(d\) is a rank-metric code that, when interpreted as a linear code over \(GF(q^m)\), admits an \((n-k)\times n\) parity-check matrix whose entries span a subspace of \(GF(q^m)\) that is at most \(d\)-dimensional.

Decoding

Efficient probabilistic decoder [1].Mixed decoder [2].

Realizations

Cryptosystem [1] that is a rank-metric analogue of NTRU [3] and MDPC [4] cryptosystems.Post-quantum cryptography [2].

Parent

Rank-metric code

Cousin

Low-density parity-check (LDPC) code — LRPC codes are rank-metric analogues of LDPC codes [1].

References

[1]: Gaborit, P., Murat, G., Ruatta, O., & Zemor, G. (2013, April). Low rank parity check codes and their application to cryptography. In Proceedings of the Workshop on Coding and Cryptography WCC (Vol. 2013).
[2]: P. Gaborit et al., “RankSign: An Efficient Signature Algorithm Based on the Rank Metric”, Post-Quantum Cryptography 88 (2014) DOI
[3]: J. Hoffstein, J. Pipher, and J. H. Silverman, “NTRU: A ring-based public key cryptosystem”, Lecture Notes in Computer Science 267 (1998) DOI
[4]: R. Misoczki et al., “MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes”, 2013 IEEE International Symposium on Information Theory (2013) DOI

Page edit log

Mazin Karjikar (2023-01-16) — most recent
Victor V. Albert (2023-01-16)

Cite as:

“Low-rank parity-check (LRPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/lrpc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/rank-metric/lrpc.yml.