Cryptology ePrint Archive: Report 2021/837

On McEliece type cryptosystems using self-dual codes with large minimum weight

Luca Mariot and Stjepan Picek and Radinka Yorgova

Abstract: One of the finalists in the NIST post-quantum cryptography competition is the Classic McEliece cryptosystem. Unfortunately, its public key size represents a practical limitation. One option to address this problem is to use different families of error-correcting codes. Most of such attempts failed as those cryptosystems were proved not secure. In this paper, we propose a McEliece type cryptosystem using high minimum distance self-dual codes and punctured codes derived from them. To the best of our knowledge, such codes have not been implemented in a code-based cryptosystem until now. For the 80-bit security case, we construct an optimal self-dual code of length 1\,064, which, as far as we are aware, was not presented before. Compared to the original McEliece cryptosystem, this allows us to reduce the key size by about 38.5\%.

Category / Keywords: public-key cryptography / Post-quantum cryptography, McEliece cryptosystem, Self-dual codes

Date: received 19 Jun 2021

Contact author: picek stjepan at gmail com, L Mariot@tudelft nl, r a yorgova@student tudelft nl

Available format(s): PDF | BibTeX Citation

Version: 20210621:075838 (All versions of this report)

Short URL: ia.cr/2021/837


[ Cryptology ePrint archive ]