Improved Algorithms for Finding Low-Weight Polynomial Multiples in GF(2)[x] and Some Cryptographic Applications
(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
- 2023-08-31 00:31:13
@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}}, }