How to find low-weight polynomial multiples.

We present an improved algorithm for finding low-weight multiples of polynomials over the binary field using coding heoretic methods. The associated code defined by the given olynomial has a cyclic structure, allowing an algorithm to earch for shifts of the sought minimum-weight odeword. Therefore, a code with higher dimension is onstructed, having a larger number of low-weight codewords nd through some additional processing also reduced minimum istance. Applying an algorithm for finding low-weight odewords in the constructed code yields a lower complexity or finding low-weight polynomial multiples compared to revious approaches. As an application, we show a key-recovery ttack against TCHo that has a lower complexity than the hosen security level indicate. Using similar ideas we also present a new probabilistic algorithm for finding a multiple of weight 4, which is faster than previous approaches. For example, this is relevant in correlation attacks on stream ciphers.