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)
- author
- Koochak Shooshtari, Masoumeh
; Ahmadian-Attari, Mahmoud
; Johansson, Thomas
LU
and Aref, Mohammad Reza
- organization
- publishing date
- 2016-07-01
- 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
-
- wos:000378417900005
- scopus:84973547871
- 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
- 2024-04-05 14:52:00
@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}},
doi = {{10.1049/iet-ifs.2015.0064}},
volume = {{10}},
year = {{2016}},
}