Published: March 03, 2016
Author(s)
Dustin Moody (NIST), Ray Perlner (NIST)
Conference
Name: 7th International Workshop on Post-Quantum Cryptography (PQCrypto 2016)
Dates: February 24-26, 2016
Location: Fukuoka, Japan
Citation: Post-Quantum Cryptography, Lecture Notes in Computer Science vol. 9606, pp. 104-117
Announcement
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.
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...
See full 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.
Hide full abstract
Keywords
code-based cryptography; information set decoding; McEliece PKC; McEliece in the World of Escher
Control Families
None selected
) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)
