Optimizing Information Set Decoding Algorithms to Attack Cyclosymmetric MDPC Codes

Recently, several promising approaches have been proposed to reduce keysizes for code based cryptography 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... See full abstract

Recently, several promising approaches have been proposed to reduce keysizes for code based cryptography 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. While Biasi et al. analyze the complexity of attacking their scheme using standard information-set-decoding algorithms, the research presented here shows that information set decoding algorithms can be improved, 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. QC-MDPC schemes are not affected by this paper’s result.
Hide full abstract