Generalized Low Rank Parity Check Codes

Abstract

The F_{q^m}-linear low-rank parity-check (LRPC) codes have been used in many cryptographic schemes.

I will show how it is possible to generalize LRPC codes obtaining a large family of Fq -linear codes sharing a similar probabilistic decoding algorithm.

Starting from a 3-tensor T we can define binary operation we call T -product.

Based on this product, I will show a generic method to expand an Fq-linear matrix code generated by k matrices who share the same small column support to a matrix code of dimension km.

The generalized LRPC codes are mostly Fq-linear matrix codes. But they include also the standard F_{q^m} -linear LRPC codes for some particular choices of the 3-tensor T.

I will present two slightly different decoding algorithms. One is very similar to the original algorithm and it can be applied only when the column space of the defining matrices and the T-product are compatible. The estimation of its decoding failure rates, confirmed by experimental results, is almost the same as that of decoding F_{q^m}-linear LRPC codes. The second algorithm can be applied also when T and the column space are not compatible but its harder to give a precise estimation of its failure rate.

Biography