Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Vulnerabilities of "McEliece in the World of Escher"

Published

Author(s)

Dustin Moody, Ray A. Perlner

Abstract

Recently, Gligoroski et al. proposed code-based encryption and signature schemes using list decoding, blockwise triangular private keys, and a nonuniform error pattern based on "generalized error sets." The general approach was referred to as "McEliece in the World of Escher". This paper demonstrates attacks which are significantly cheaper than the claimed security level of the parameters given by Gligoroski et al. We implemented an attack on the proposed 80-bit parameters which was able to recover private keys for both encryption and signatures in approximately 2 hours on a single laptop. We further find that increasing the parameters to avoid our attack will require parameters to grow by (at least) two orders of magnitude for encryption, and may not be achievable at all for signatures.
Proceedings Title
Proceedings of the 7th International Workshop on Post-Quantum Cryptography
Volume
9606
Conference Dates
February 24-26, 2016
Conference Location
Fukuoka
Conference Title
7th International Conference on Post-Quantum Cryptography (PQCrypto 2016)

Keywords

Information Set Decoding, Code-based Cryptography, McEliece, Post-Quantum Cryptography

Citation

Moody, D. and Perlner, R. (2016), Vulnerabilities of "McEliece in the World of Escher", Proceedings of the 7th International Workshop on Post-Quantum Cryptography, Fukuoka, -1, [online], https://doi.org/10.1007/978-3-319-29360-8_8 (Accessed February 26, 2024)
Created March 3, 2016, Updated November 10, 2018