Creating and sharing knowledge for telecommunications

Using Low-Density Parity-Check codes to improve the McEliece cryptosystem

Branco, P. ; Mateus, P. ; Salema, C. ; Souto, A.

Information Sciences Vol. 510, Nº -, pp. 243 - 255, February, 2020.

ISSN (print): 0020-0255
ISSN (online):

Journal Impact Factor: 3,095 (in 2008)

Digital Object Identifier: 10.1016/j.ins.2019.09.030

Developing secure and fast asymmetric cryptographic primitives is a priority in cryptography. This fact steams from high demand for fast communication involving an increasing amount of private and sensible information. To this end, we propose an efficient McEliece-based cryptosystem to handle large messages that can be easily implemented in hardware. The main idea is to incorporate Low-Density Parity-Check (LDPC) codes after several parallel runs of the original McEliece cryptosystem. In this way, we achieve a low circuit-depth complexity while profiting from the capability of LDPC codes to deal with high-dimensional data. The proposed cryptosystem is at least as hard as the original McEliece cryptosystem, and therefore, it is believed to be robust to quantum attacks. Moreover, known attacks to McEliece cryptosystems based on LDPC codes are ineffective against our proposal. The key size of the cryptosystem is roughly ten times smaller than the original McEliece for similar levels of security. Finally, we present a variant of the proposed cryptosystem that is resistant to adaptive indistinguishability chosen-chiphertext attacks (IND-CCA2), which is a desirable property that the original McEliece cryptosystem does not fulfill.