Improved Algorithms for Finding Low-Weight Polynomial Multiples in GF(2)[x] and Some Cryptographic Applications

Summary, in English

In this paper we present an improved algorithm for finding

low-weight 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 minimum-weight

codeword. Therefore, a code with higher dimension is

constructed, having a larger number of low-weight codewords

and through some additional processing also reduced minimum

distance. Applying an algorithm for finding low-weight codewords

in the constructed code yields a lower complexity for finding low-weight polynomial

multiples compared to previous approaches. As an application, we

show a key-recovery attack against TCHo that has

a lower complexity than the chosen security level indicate.

• Författare: Carl Löndahl; Thomas Johansson
• Avdelning/ar: Institutionen för elektro- och informationsteknik; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 625-640
• Publikation/Tidskrift/Serie: Designs, Codes and Cryptography
• Volym: 73
• Issue: 2
• Länkar: http://dx.doi.org/10.1007/s10623-014-9960-6
• Dokumenttyp: Artikel i tidskrift
• Förlag: Springer
• Ämne: Electrical Engineering, Electronic Engineering, Information Engineering
• Nyckelord: low-weight codeword; Low-weight polynomial multiple; information-set decoding; public-key cryptography; TCHo; correlation attacks
• Status: Published
• Forskningsgrupp: Crypto and Security
• ISBN/ISSN/Övrigt: ISSN: 1573-7586