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:
https://lup.lub.lu.se/record/4360127
- author
- Löndahl, Carl
LU
and Johansson, Thomas
LU
- organization
- publishing date
- 2014
- 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
- 2016-04-01 10:21:32
- date last changed
- 2025-11-24 09:35:18
@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}},
keywords = {{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}},
doi = {{10.1007/s10623-014-9960-6}},
volume = {{73}},
year = {{2014}},
}