An improvement to Stern's algorithm
(2011)- Abstract
- The decoding problem is a fundamental problem in computational complexity theory. In particular, the efficiency of which the problem can be decided has implications on the security of cryptosystems based on hard problems in coding theory. Stern's algorithm has long been the best algorithm available, with slight modifications over the years yielding only small speed-ups. This paper describes an improved method of finding low weight codewords in a random code, leading to an improved decoding algorithm.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/2204753
- author
- Johansson, Thomas LU and Löndahl, Carl LU
- organization
- publishing date
- 2011
- type
- Book/Report
- publication status
- unpublished
- subject
- keywords
- information set decoding, random codes, public-key cryptography, birthday technique, binary codes
- publisher
- [Publisher information missing]
- language
- English
- LU publication?
- yes
- id
- ae6b4a32-b5db-4854-bbe5-b26e8083718b (old id 2204753)
- date added to LUP
- 2016-04-04 12:52:23
- date last changed
- 2019-04-30 17:03:23
@techreport{ae6b4a32-b5db-4854-bbe5-b26e8083718b, abstract = {{The decoding problem is a fundamental problem in computational complexity theory. In particular, the efficiency of which the problem can be decided has implications on the security of cryptosystems based on hard problems in coding theory. Stern's algorithm has long been the best algorithm available, with slight modifications over the years yielding only small speed-ups. This paper describes an improved method of finding low weight codewords in a random code, leading to an improved decoding algorithm.}}, author = {{Johansson, Thomas and Löndahl, Carl}}, institution = {{[Publisher information missing]}}, keywords = {{information set decoding; random codes; public-key cryptography; birthday technique; binary codes}}, language = {{eng}}, title = {{An improvement to Stern's algorithm}}, url = {{https://lup.lub.lu.se/search/files/6012849/2204899.pdf}}, year = {{2011}}, }