Advanced

Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension

Löndahl, Carl LU ; Johansson, Thomas LU ; Koochak Shooshtari, Masoumeh; Ahmadian-Attari, Mahmoud and Aref, Mohammad Reza (2016) In Designs, Codes, and Cryptography 80(2). p.359-377
Abstract

We present a general purpose algorithm for finding low-weight codewords as well as for decoding a received codeword in any quasi-cyclic code whose length and dimension is a multiple of a power of 2. In this paper, we apply the algorithm on a McEliece variant recently proposed by Misoczki et al. (MDPC-McEliece: New McEliece variants from moderate density parity-check codes, 2013). In their paper, the authors present instances of LDPC codes with increased weight for use in a McEliece type PKC. They claim that all message-recovery and key-recovery attacks can be avoided. We show that this is not true for certain parameters and public-key matrices.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Information-set decoding, Low-weight codeword, McEliece, MDPC codes, Public-key cryptography
in
Designs, Codes, and Cryptography
volume
80
issue
2
pages
19 pages
publisher
Springer
external identifiers
  • scopus:84930526584
  • wos:000378885600007
ISSN
0925-1022
DOI
10.1007/s10623-015-0099-x
language
English
LU publication?
yes
id
f71f135c-05f5-4cc1-a714-5e5685836c3d
date added to LUP
2016-12-30 11:48:46
date last changed
2017-11-05 05:11:49
@article{f71f135c-05f5-4cc1-a714-5e5685836c3d,
  abstract     = {<p>We present a general purpose algorithm for finding low-weight codewords as well as for decoding a received codeword in any quasi-cyclic code whose length and dimension is a multiple of a power of 2. In this paper, we apply the algorithm on a McEliece variant recently proposed by Misoczki et al. (MDPC-McEliece: New McEliece variants from moderate density parity-check codes, 2013). In their paper, the authors present instances of LDPC codes with increased weight for use in a McEliece type PKC. They claim that all message-recovery and key-recovery attacks can be avoided. We show that this is not true for certain parameters and public-key matrices.</p>},
  author       = {Löndahl, Carl and Johansson, Thomas and Koochak Shooshtari, Masoumeh and Ahmadian-Attari, Mahmoud and Aref, Mohammad Reza},
  issn         = {0925-1022},
  keyword      = {Information-set decoding,Low-weight codeword,McEliece,MDPC codes,Public-key cryptography},
  language     = {eng},
  month        = {08},
  number       = {2},
  pages        = {359--377},
  publisher    = {Springer},
  series       = {Designs, Codes, and Cryptography},
  title        = {Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension},
  url          = {http://dx.doi.org/10.1007/s10623-015-0099-x},
  volume       = {80},
  year         = {2016},
}