International Association
for Cryptologic Research

Recently, several variants of the McEliece cryptosystem based on low-density parity-check (LDPC) codes have been proposed. When combined with quasi-cyclic structure, these proposals provide much smaller key sizes than the original McEliece cryptosystem. LDPC codes are characterized by the existence of low weight dual codewords, used to perform an efficient iterative decoding. In order to avoid attacks aimed at recovering such codewords, these last proposals suggested to replace the permutation matrix used by McEliece by a matrix of small constant row and column weight, in order to increase the dual codeword weight. In this paper, we introduce the moderate density parity-check codes (MPDC, for short), which provide a better decoding process than the aforementioned LDPC variants. It also recovers the possibility to use permutation equivalent private and public codes. As a result, we present two new McEliece variants (one using quasi-cyclic MDPC codes and other employing generic MDPC codes). One of the main benefits of our variants is that both key-recovery and message decoding attacks boil down to the same coding-theory problem: low weight codeword finding. Therefore we present a security reduction much closer to the general decoding problem than any other code-based encryption scheme. Regarding each variant separately, while the QC-MDPC variant is mainly focused on allowing smaller public keys (e.g., for 80-bits of security, only 4800 bits), the MDPC variant further reduces the ways for structural attacks. Finally, we evaluate several kind of attacks, resulting in practical parameters quite competitive to conventional cryptography.