Improved algorithms for finding low-weight polynomial multiples in F₂[x] and some cryptographic applications

DOI10.1007/S10623-014-9960-6MaRDI QIDQ398976zbMATH OpenOpenAlexFDO

Authors Carl Löndahl, Thomas Johansson

Publication date 18 August 2014

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10623-014-9960-6

zbMATH Keywords

public-key cryptographycorrelation attacksinformation-set decodinglow-weight codeword\(\mathrm{TCH}_{\mathrm O}\)low-weight polynomial multiple

Mathematics Subject Classification ID

Randomized algorithms (68W20) Cryptography (94A60) Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Recommendations

• A new approach for finding low-weight polynomial multiples
• A discrete logarithm-based approach to compute low-weight multiples of binary polynomials
• Computation of low-weight parity checks for correlation attacks on stream ciphers
• Correlation attacks on stream ciphers: computing low-weight parity checks based on error-correcting codes
• Finding low-weight polynomial multiples using the rho method

Cites work

• scientific article; zbMATH DE number 4112524 (Why is no real title available?)
• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• scientific article; zbMATH DE number 2086708 (Why is no real title available?)
• $\mathcal{TCH}o$ : A Hardware-Oriented Trapdoor Cipher
• A Practical Key Recovery Attack on Basic TCHo
• A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511
• A survey on fast correlation attacks
• Algorithmic Cryptanalysis
• Attacking and Defending the McEliece Cryptosystem
• Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
• Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)
• Fast correlation attacks on certain stream ciphers
• Improved fast correlation attacts using parity-check equations of weight 4 and 5
• Introduction to post-quantum cryptography
• Security bounds for the design of code-based cryptosystems
• Smaller decoding exponents: ball-collision decoding
• When Stream Cipher Analysis Meets Public-Key Cryptography

Cited in

(7)

• Finding low-weight polynomial multiples using the rho method
• Walsh transforms and cryptographic applications in bias computing
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension
• Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
• A new approach for finding low-weight polynomial multiples
• A discrete logarithm-based approach to compute low-weight multiples of binary polynomials

Describes a project that uses

Uses Software

• McEliece

This page was built for publication: Improved algorithms for finding low-weight polynomial multiples in \(\mathbb F_2[x]\) and some cryptographic applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q398976)