### Optimizing Information Set Decoding Algorithms to Attack Cyclosymmetric MDPC Codes

Ray Perlner

##### Abstract

The most important drawback to code-based cryptography has historically been its large key sizes. Recently, several promising approaches have been proposed to reduce keysizes. In particular, significant keysize reduction has been achieved by using structured, but non-algebraic codes, such as quasi-cyclic (QC) Moderate Density Parity Check (MDPC) codes. Biasi et al. propose further reducing the keysizes of code-based schemes using cyclosymmetric (CS) codes. Biasi et al. analyze the complexity of attacking their scheme using standard information-set-decoding attacks. However, the research presented here shows that information set decoding algorithms can be modified, by choosing the columns of the information set in a way that takes advantage of the added symmetry. The result is an attack that significantly reduces the security of the proposed CS-MDPC schemes to the point that they no longer offer an advantage in keysize over QC-MDPC schemes of the same security level.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
information set decodingcode-based cryptographymoderate density parity check (MDPC) codescyclosymmetric
Contact author(s)
ray perlner @ nist gov
History
2014-05-27: revised
See all versions
Short URL
https://ia.cr/2014/354

CC BY

BibTeX

@misc{cryptoeprint:2014/354,
author = {Ray Perlner},
title = {Optimizing Information Set Decoding Algorithms to Attack Cyclosymmetric MDPC Codes},
howpublished = {Cryptology ePrint Archive, Paper 2014/354},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/354}},
url = {https://eprint.iacr.org/2014/354}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.