Gianluigi Liva

Hannes Bartz, Emna Ben Yacoub, Lorenza Bertarelli et al.

A new protograph-based framework for message passing (MP) decoding of low density parity-check (LDPC) codes with Hamming weight amplifiers (HWAs), which are used e.g. in the NIST post-quantum crypto candidate LEDAcrypt, is proposed. The scheme exploits the correlations in the error patterns introduced by the HWA using a turbo-like decoding approach where messages between the decoders for the outer code given by the HWA and the inner LDPC code are exchanged. Decoding thresholds for the proposed scheme are computed using density evolution (DE) analysis for belief propagation (BP) and ternary message passing (TMP) decoding and compared to existing decoding approaches. The proposed scheme improves upon the basic approach of decoding LDPC code from the amplified error and has a similar performance as decoding the corresponding moderate-density parity-check (MDPC) code but with a significantly lower computational complexity.

Albin Severinson, Alexandre Graell i Amat, Eirik Rosnes et al.

We propose a coded distributed computing scheme based on Raptor codes to address the straggler problem. In particular, we consider a scheme where each server computes intermediate values, referred to as droplets, that are either stored locally or sent over the network. Once enough droplets are collected, the computation can be completed. Compared to previous schemes in the literature, our proposed scheme achieves lower computational delay when the decoding time is taken into account.

Gianluigi Liva, Hannes Bartz

In this paper, ensembles of quasi-cyclic moderate-density parity-check (MDPC) codes based on protographs are introduced and analyzed in the context of a McEliece-like cryptosystem. The proposed ensembles significantly improve the error correction capability of the regular MDPC code ensembles that are currently considered for post-quantum cryptosystems without increasing the public key size. The proposed ensembles are analyzed in the asymptotic setting via density evolution, both under the sum-product algorithm and a low-complexity (error-and-erasure) message passing algorithm. The asymptotic analysis is complemented at finite block lengths by Monte Carlo simulations. The enhanced error correction capability remarkably improves the scheme robustness with respect to (known) decoding attacks.

Hannes Bartz, Gianluigi Liva

Recently, it has been shown how McEliece public-key cryptosystems based on moderate-density parity-check (MDPC) codes allow for very compact keys compared to variants based on other code families. In this paper, classical (iterative) decoding schemes for MPDC codes are considered. The algorithms are analyzed with respect to their error-correction capability as well as their resilience against a recently proposed reaction-based key-recovery attack on a variant of the MDPC-McEliece cryptosystem by Guo, Johansson and Stankovski (GJS). New message-passing decoding algorithms are presented and analyzed. Two proposed decoding algorithms have an improved error-correction performance compared to existing hard-decision decoding schemes and are resilient against the GJS reaction-based attack for an appropriate choice of the algorithm's parameters. Finally, a modified belief propagation decoding algorithm that is resilient against the GJS reaction-based attack is presented.