Improved Algorithms for Finding Low-Weight Polynomial Multiples in GF(2)[x] and Some Cryptographic Applications
Författare
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.
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.
Avdelning/ar
Publiceringsår
2014
Språk
Engelska
Sidor
625-640
Publikation/Tidskrift/Serie
Designs, Codes and Cryptography
Volym
73
Issue
2
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