Paper 2015/966

Vulnerabilities of ``McEliece in the World of Escher"

Dustin Moody and Ray 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 \emph{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 almost an order of magnitude for signatures, and (at least) two orders of magnitude for encryption.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2016
DOI
10.1007/978-3-319-29360-8_8
Keywords
Information Set DecodingCode-based CryptographyMcEliece PKCMcEliece in the World of Escher
Contact author(s)
ray perlner @ nist gov
History
2016-02-17: revised
2015-10-09: received
See all versions
Short URL
https://ia.cr/2015/966
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/966,
      author = {Dustin Moody and Ray Perlner},
      title = {Vulnerabilities of ``McEliece in the World of Escher"},
      howpublished = {Cryptology ePrint Archive, Paper 2015/966},
      year = {2015},
      doi = {10.1007/978-3-319-29360-8_8},
      note = {\url{https://eprint.iacr.org/2015/966}},
      url = {https://eprint.iacr.org/2015/966}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.