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

Thomas Johansson; Carl Löndahl

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

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

Abstract

In this paper we present an algorithm for ﬁnding low-weight multiples of
polynomials over the binary ﬁeld using coding theoretic methods. The code deﬁned
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 ﬁnding low-weight
codewords on the constructed code yields complexity for a key-recovery attack against
TCHo that is lower than previously expected.

Original language	English
Title of host publication	Preproceedings The International Workshop on Coding and Cryptography WCC 2013
Editors	Lilya Budaghyan, Tor Helleseth, Matthew G. Parker
Publisher	The Selmer Center at the University of Bergen
Number of pages	12
ISBN (Print)	978-82-308-2269-2
Publication status	Published - 2013
Event	International Workshop on Coding and Cryptography, WCC 2013 - Bergen, Norway Duration: 2013 Apr 15 → 2013 Apr 19

Conference

Conference	International Workshop on Coding and Cryptography, WCC 2013
Country/Territory	Norway
City	Bergen
Period	2013/04/15 → 2013/04/19

Subject classification (UKÄ)

Electrical Engineering, Electronic Engineering, Information Engineering

Free keywords

Low-weight polynomial multiple
low-weight codeword
information-set decoding
public-key cryptography
TCHo

Access to Document

http://www.selmer.uib.no/WCC2013/PreProceedings.pdf

Cite this

@inproceedings{56d1e95a470a47dd803a1fafc447c147,

title = "A new algorithm for finding low-weight polynomial multiples and its application to TCHo",

abstract = "In this paper we present an algorithm for ﬁnding low-weight multiples of polynomials over the binary ﬁeld using coding theoretic methods. The code deﬁned 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 ﬁnding low-weight codewords on the constructed code yields complexity for a key-recovery attack against TCHo that is lower than previously expected.",

keywords = "Low-weight polynomial multiple, low-weight codeword, information-set decoding, public-key cryptography, TCHo",

author = "Thomas Johansson and Carl L{\"o}ndahl",

year = "2013",

language = "English",

isbn = "978-82-308-2269-2",

editor = "Lilya Budaghyan and Tor Helleseth and Parker, {Matthew G.}",

booktitle = "Preproceedings The International Workshop on Coding and Cryptography WCC 2013",

publisher = "The Selmer Center at the University of Bergen",

note = "International Workshop on Coding and Cryptography, WCC 2013 ; Conference date: 15-04-2013 Through 19-04-2013",

}

Johansson, T & Löndahl, C 2013, A new algorithm for finding low-weight polynomial multiples and its application to TCHo. in L Budaghyan, T Helleseth & MG Parker (eds), Preproceedings The International Workshop on Coding and Cryptography WCC 2013. The Selmer Center at the University of Bergen, International Workshop on Coding and Cryptography, WCC 2013, Bergen, Norway, 2013/04/15. <http://www.selmer.uib.no/WCC2013/PreProceedings.pdf>

A new algorithm for finding low-weight polynomial multiples and its application to TCHo. / Johansson, Thomas; Löndahl, Carl.
Preproceedings The International Workshop on Coding and Cryptography WCC 2013. ed. / Lilya Budaghyan; Tor Helleseth; Matthew G. Parker. The Selmer Center at the University of Bergen, 2013.

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

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

AU - Johansson, Thomas

AU - Löndahl, Carl

PY - 2013

Y1 - 2013

N2 - In this paper we present an algorithm for ﬁnding low-weight multiples of polynomials over the binary ﬁeld using coding theoretic methods. The code deﬁned 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 ﬁnding low-weight codewords on the constructed code yields complexity for a key-recovery attack against TCHo that is lower than previously expected.

AB - In this paper we present an algorithm for ﬁnding low-weight multiples of polynomials over the binary ﬁeld using coding theoretic methods. The code deﬁned 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 ﬁnding low-weight codewords on the constructed code yields complexity for a key-recovery attack against TCHo that is lower than previously expected.

KW - Low-weight polynomial multiple

KW - low-weight codeword

KW - information-set decoding

KW - public-key cryptography

KW - TCHo

M3 - Paper in conference proceeding

SN - 978-82-308-2269-2

BT - Preproceedings The International Workshop on Coding and Cryptography WCC 2013

A2 - Budaghyan, Lilya

A2 - Helleseth, Tor

A2 - Parker, Matthew G.

PB - The Selmer Center at the University of Bergen

T2 - International Workshop on Coding and Cryptography, WCC 2013

Y2 - 15 April 2013 through 19 April 2013

ER -

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

Abstract

Conference

Subject classification (UKÄ)

Free keywords

Access to Document

Fingerprint

Cite this