Cryptology ePrint Archive: Report 2014/354
Optimizing Information Set Decoding Algorithms to Attack Cyclosymmetric MDPC Codes
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.
Category / Keywords: public-key cryptography / information set decoding, code-based cryptography, moderate density parity check (MDPC) codes, cyclosymmetric
Date: received 20 May 2014, last revised 27 May 2014
Contact author: ray perlner at nist gov
Available format(s): PDF | BibTeX Citation
Version: 20140527:204953 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]