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

Summary, in English

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.

• Author: Thomas Johansson; Carl Löndahl
• Editor: Lilya Budaghyan; Tor Helleseth; Matthew G. Parker
• Department/s: Department of Electrical and Information Technology; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publishing year: 2013
• Language: English
• Publication/Series: Preproceedings The International Workshop on Coding and Cryptography WCC 2013
• Links: http://www.selmer.uib.no/WCC2013/PreProceedings.pdf
• Document type: Conference paper
• Publisher: The Selmer Center at the University of Bergen
• Topic: Electrical Engineering, Electronic Engineering, Information Engineering
• Keywords: Low-weight polynomial multiple; low-weight codeword; information-set decoding; public-key cryptography; TCHo
• Conference name: International Workshop on Coding and Cryptography, WCC 2013
• Conference date: 2013-04-15 - 2013-04-19
• Conference place: Bergen, Norway
• Status: Published
• ISBN/ISSN/Other: ISBN: 978-82-308-2269-2