Information-set decoding for convolutional codes

Area of Science:

• Cryptography
• Coding Theory
• Computer Science

Background:

• Code-based cryptography relies on the difficulty of decoding general linear codes.
• Convolutional codes are a specific type of code used in some cryptosystems.
• Existing cryptanalysis methods for these systems can be computationally intensive.

Purpose of the Study:

• To present a generic decoding framework for convolutional codes.
• To apply this framework for cryptanalysis of code-based cryptosystems.
• To evaluate the success probabilities and provide tools for parameter selection in information set decoding.

Main Methods:

• Developed a generic decoding framework for convolutional codes.
• Applied the framework to information set decoding.
• Analyzed success probabilities and variable selection for decoding.
• Performed cryptanalysis on two specific cryptosystems using convolutional codes.

Main Results:

• Successfully recovered approximately 74% of errors in a variation of the McEliece cryptosystem within 10 hours.
• Provided experimental evidence for recovering 80% of errors in another cryptosystem (Almeida et al.) in times equivalent to ~70 bits of security.
• Demonstrated practical attacks on cryptosystems leveraging convolutional codes.

Conclusions:

• The proposed decoding framework is effective for cryptanalyzing code-based systems using convolutional codes.
• The framework offers practical methods for attacking existing cryptosystems, impacting key size and security estimations.
• This work provides valuable tools for understanding and potentially breaking convolutional code-based cryptography.