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
-
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},
url = {https://eprint.iacr.org/2015/966}
}
