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.

• Author: Carl Löndahl; Thomas Johansson
• Department/s: Department of Electrical and Information Technology; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publishing year: 2014
• Language: English
• Pages: 625-640
• Publication/Series: Designs, Codes and Cryptography
• Volume: 73
• Issue: 2
• Links: http://dx.doi.org/10.1007/s10623-014-9960-6
• Document type: Journal article
• Publisher: Springer
• Topic: Electrical Engineering, Electronic Engineering, Information Engineering
• Keywords: low-weight codeword; Low-weight polynomial multiple; information-set decoding; public-key cryptography; TCHo; correlation attacks
• Status: Published
• Research group: Crypto and Security
• ISBN/ISSN/Other: ISSN: 1573-7586