Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Optimizing Information Set Decoding Algorithms to Attack Cyclosymetric MDPC Codes

Published

Author(s)

Ray A. 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 or quasi-dyadic 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 against 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.
Proceedings Title
Post-Quantum Cryptography (Lecture Notes in Computer Science)
Volume
8772
Conference Dates
October 1-3, 2014
Conference Location
Waterloo
Conference Title
6th International Conference on Post-Quantum Cryptography (PQCrypto 2014)

Keywords

information set decoding, code-based cryptography, moderate density parity check (MDPC) codes, cyclosymmetric

Citation

Perlner, R. (2014), Optimizing Information Set Decoding Algorithms to Attack Cyclosymetric MDPC Codes, Post-Quantum Cryptography (Lecture Notes in Computer Science), Waterloo, -1, [online], https://doi.org/10.1007/978-3-319-11659-4_13 (Accessed December 1, 2023)
Created October 3, 2014, Updated November 10, 2018