Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A new algorithm for finding low-weight polynomial multiples and its application to TCHo

Johansson, Thomas LU orcid and Löndahl, Carl LU (2013) International Workshop on Coding and Cryptography, WCC 2013
Abstract
In this paper we present an algorithm for finding low-weight multiples of

polynomials over the binary field using coding theoretic methods. The code defined

by the public polynomial is cyclic, allowing an attacker to search for any shift of the

sought codeword. Therefore, a code with higher length and dimension is used, having

a larger number of low-weight codewords. Additionally, since the degree of the sought

polynomial is known, the sought codewords of weight w are transformed by a linear

mapping into codewords of weight w-2. Applying an algorithm for finding low-weight

codewords on the constructed code yields complexity for a key-recovery attack against

TCHo that is... (More)
In this paper we present an algorithm for finding low-weight multiples of

polynomials over the binary field using coding theoretic methods. The code defined

by the public polynomial is cyclic, allowing an attacker to search for any shift of the

sought codeword. Therefore, a code with higher length and dimension is used, having

a larger number of low-weight codewords. Additionally, since the degree of the sought

polynomial is known, the sought codewords of weight w are transformed by a linear

mapping into codewords of weight w-2. Applying an algorithm for finding low-weight

codewords on the constructed code yields complexity for a key-recovery attack against

TCHo that is lower than previously expected. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Low-weight polynomial multiple, low-weight codeword, information-set decoding, public-key cryptography, TCHo
host publication
Preproceedings The International Workshop on Coding and Cryptography WCC 2013
editor
Budaghyan, Lilya ; Helleseth, Tor and Parker, Matthew G.
pages
12 pages
publisher
The Selmer Center at the University of Bergen
conference name
International Workshop on Coding and Cryptography, WCC 2013
conference location
Bergen, Norway
conference dates
2013-04-15 - 2013-04-19
ISBN
978-82-308-2269-2
language
English
LU publication?
yes
id
56d1e95a-470a-47dd-803a-1fafc447c147 (old id 3634199)
alternative location
http://www.selmer.uib.no/WCC2013/PreProceedings.pdf
date added to LUP
2016-04-04 11:47:07
date last changed
2018-11-21 21:07:11
@inproceedings{56d1e95a-470a-47dd-803a-1fafc447c147,
  abstract     = {{In this paper we present an algorithm for finding low-weight multiples of<br/><br>
polynomials over the binary field using coding theoretic methods. The code defined<br/><br>
by the public polynomial is cyclic, allowing an attacker to search for any shift of the<br/><br>
sought codeword. Therefore, a code with higher length and dimension is used, having<br/><br>
a larger number of low-weight codewords. Additionally, since the degree of the sought<br/><br>
polynomial is known, the sought codewords of weight w are transformed by a linear<br/><br>
mapping into codewords of weight w-2. Applying an algorithm for finding low-weight<br/><br>
codewords on the constructed code yields complexity for a key-recovery attack against<br/><br>
TCHo that is lower than previously expected.}},
  author       = {{Johansson, Thomas and Löndahl, Carl}},
  booktitle    = {{Preproceedings The International Workshop on Coding and Cryptography WCC 2013}},
  editor       = {{Budaghyan, Lilya and Helleseth, Tor and Parker, Matthew G.}},
  isbn         = {{978-82-308-2269-2}},
  keywords     = {{Low-weight polynomial multiple; low-weight codeword; information-set decoding; public-key cryptography; TCHo}},
  language     = {{eng}},
  publisher    = {{The Selmer Center at the University of Bergen}},
  title        = {{A new algorithm for finding low-weight polynomial multiples and its application to TCHo}},
  url          = {{http://www.selmer.uib.no/WCC2013/PreProceedings.pdf}},
  year         = {{2013}},
}