Improved algorithms for finding lowweight polynom

Authors: Carl Löndahl Thomas Johansson

Publish Date: 2014/04/24

Volume: 73, Issue: 2, Pages: 625-640

PDF Link

Abstract

In this paper we present an improved algorithm for finding lowweight multiples of polynomials over the binary field using coding theoretic methods The associated code defined by the given polynomial has a cyclic structure allowing an algorithm to search for shifts of the sought minimumweight codeword Therefore a code with higher dimension is constructed having a larger number of lowweight codewords and through some additional processing also reduced minimum distance Applying an algorithm for finding lowweight codewords in the constructed code yields a lower complexity for finding lowweight polynomial multiples compared to previous approaches As an application we show a keyrecovery attack against Open image in new window  that has a lower complexity than the chosen 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 ciphersWe would like to thank the anonymous reviewers in the submission to DCC and WCC for their valuable and insightful comments that helped improve the manuscript We also want to thank Martin Ågren for helping out with the initial implementation of the algorithm described in Sect 6 This research was funded by a grant 62120094646 from the Swedish Research CouncilThe complexity function C refers to the expected complexity of running Algorithm 1 with an instance where we have one single solution ie only one codeword of weight w exists in the code whereas in the case of LWPMb there will exist several weight w codewords Having y+1 possible solutions instead of one suggests that finding at least one is roughly y+1 times more likely However for this to be true the probability xi of finding one single codeword in one iteration must be small In particular we require that yxi ll 1 Secondly we require the events of finding the shifted lowweight codewords to be independent of each otherUnder the two conditions y xi ll 1 and w left 1fracd Pdright gg 2p we can conclude that the probability of finding at least one out of y+1 codewords is 11xi y+1 approx y+1 xi since all codewords are equally likely to be found Moreover the complexity C is mathcal Oleft xi 1right and therefore Algorithm 2 has complexity mathcal Oleft y+11xi 1right This concludes the proof of Proposition 1

Keywords: