Advanced

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

Löndahl, Carl LU and Johansson, Thomas LU (2014) In Designs, Codes and Cryptography 73(2). p.625-640
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
low-weight codeword, Low-weight polynomial multiple, information-set decoding, public-key cryptography, TCHo, correlation attacks
in
Designs, Codes and Cryptography
volume
73
issue
2
pages
625 - 640
publisher
Springer
external identifiers
  • wos:000339826100023
  • scopus:84905170758
ISSN
1573-7586
DOI
10.1007/s10623-014-9960-6
language
English
LU publication?
yes
id
30f8186a-73bb-4a74-b46c-564582c6dabd (old id 4360127)
date added to LUP
2014-03-20 13:05:52
date last changed
2017-01-01 03:30:46
@article{30f8186a-73bb-4a74-b46c-564582c6dabd,
  abstract     = {In this paper we present an improved algorithm for finding<br/><br>
 low-weight multiples of polynomials over the binary field<br/><br>
 using coding theoretic methods. The associated code defined by<br/><br>
 the given polynomial has a cyclic structure, allowing an<br/><br>
 algorithm to search for shifts of the sought minimum-weight<br/><br>
 codeword. Therefore, a code with higher dimension is<br/><br>
 constructed, having a larger number of low-weight codewords<br/><br>
 and through some additional processing also reduced minimum<br/><br>
 distance. Applying an algorithm for finding low-weight codewords<br/><br>
 in the constructed code yields a lower complexity for finding low-weight polynomial<br/><br>
 multiples compared to previous approaches. As an application, we<br/><br>
 show a key-recovery attack against TCHo that has<br/><br>
 a lower complexity than the chosen security level indicate.},
  author       = {Löndahl, Carl and Johansson, Thomas},
  issn         = {1573-7586},
  keyword      = {low-weight codeword,Low-weight polynomial multiple,information-set decoding,public-key cryptography,TCHo,correlation attacks},
  language     = {eng},
  number       = {2},
  pages        = {625--640},
  publisher    = {Springer},
  series       = {Designs, Codes and Cryptography},
  title        = {Improved Algorithms for Finding Low-Weight Polynomial Multiples in GF(2)[x] and Some Cryptographic Applications},
  url          = {http://dx.doi.org/10.1007/s10623-014-9960-6},
  volume       = {73},
  year         = {2014},
}