Advanced

Cryptanalysis of McEliece cryptosystem variants based on quasi-cyclic low-density parity check codes

Koochak Shooshtari, Masoumeh; Ahmadian-Attari, Mahmoud; Johansson, Thomas LU and Aref, Mohammad Reza (2016) In IET Information Security 10(4). p.194-202
Abstract

One of the approaches to modify the McEliece cryptosystem to overcome its large key size is replacing binary Goppa codes with a new structured code. However, this modification makes such cryptosystems encounter some new attacks. There are a few modified McEliece cryptosystem variants which are known to be secure. One of them is the cryptosystem introduced by Baldi et al. which uses quasi-cyclic low-density parity check (QC-LDPC) codes. This cryptosystem is still unbroken as no efficient attack has been reported against it since 2008. In this study, an attack has been applied to this cryptosystem which is feasible when the code length is a multiple of a power of 2. Also an important weakness of this kind of cryptosystem has been pointed... (More)

One of the approaches to modify the McEliece cryptosystem to overcome its large key size is replacing binary Goppa codes with a new structured code. However, this modification makes such cryptosystems encounter some new attacks. There are a few modified McEliece cryptosystem variants which are known to be secure. One of them is the cryptosystem introduced by Baldi et al. which uses quasi-cyclic low-density parity check (QC-LDPC) codes. This cryptosystem is still unbroken as no efficient attack has been reported against it since 2008. In this study, an attack has been applied to this cryptosystem which is feasible when the code length is a multiple of a power of 2. Also an important weakness of this kind of cryptosystem has been pointed out, namely utilising a too low-weight intentional error vector. The authors have established a new security level for this cryptosystem which is applicable to other McEliece-like cryptosystems using QC-LDPC codes. This security level for instance is 29.18 times lower than previous ones in the case of n = 4 x 4096 when only one ciphertext is available. The gain of the attack in this study can be increased if more than one ciphertext is available.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IET Information Security
volume
10
issue
4
pages
9 pages
publisher
Institution of Engineering and Technology
external identifiers
  • scopus:84973547871
  • wos:000378417900005
ISSN
1751-8709
DOI
10.1049/iet-ifs.2015.0064
language
English
LU publication?
yes
id
9e1c7f5f-4341-41bc-9a9e-7f709aa9a85e
date added to LUP
2017-01-17 16:45:24
date last changed
2017-09-18 11:32:11
@article{9e1c7f5f-4341-41bc-9a9e-7f709aa9a85e,
  abstract     = {<p>One of the approaches to modify the McEliece cryptosystem to overcome its large key size is replacing binary Goppa codes with a new structured code. However, this modification makes such cryptosystems encounter some new attacks. There are a few modified McEliece cryptosystem variants which are known to be secure. One of them is the cryptosystem introduced by Baldi et al. which uses quasi-cyclic low-density parity check (QC-LDPC) codes. This cryptosystem is still unbroken as no efficient attack has been reported against it since 2008. In this study, an attack has been applied to this cryptosystem which is feasible when the code length is a multiple of a power of 2. Also an important weakness of this kind of cryptosystem has been pointed out, namely utilising a too low-weight intentional error vector. The authors have established a new security level for this cryptosystem which is applicable to other McEliece-like cryptosystems using QC-LDPC codes. This security level for instance is 2<sup>9.18</sup> times lower than previous ones in the case of n = 4 x 4096 when only one ciphertext is available. The gain of the attack in this study can be increased if more than one ciphertext is available.</p>},
  author       = {Koochak Shooshtari, Masoumeh and Ahmadian-Attari, Mahmoud and Johansson, Thomas and Aref, Mohammad Reza},
  issn         = {1751-8709},
  language     = {eng},
  month        = {07},
  number       = {4},
  pages        = {194--202},
  publisher    = {Institution of Engineering and Technology},
  series       = {IET Information Security},
  title        = {Cryptanalysis of McEliece cryptosystem variants based on quasi-cyclic low-density parity check codes},
  url          = {http://dx.doi.org/10.1049/iet-ifs.2015.0064},
  volume       = {10},
  year         = {2016},
}