A new algorithm for finding low-weight polynomial multiples and its application to TCHo
(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:
https://lup.lub.lu.se/record/3634199
- author
- Johansson, Thomas LU and Löndahl, Carl LU
- organization
- publishing date
- 2013
- 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}}, }