Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Löndahl, Carl LU ; Johansson, Thomas LU orcid ; 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
; ; ; and
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
  • wos:000378885600007
  • scopus:84930526584
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
2024-01-04 20:06:04
@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}},
  keywords     = {{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}},
  doi          = {{10.1007/s10623-015-0099-x}},
  volume       = {{80}},
  year         = {{2016}},
}