Advanced

An improvement to Stern's algorithm

Johansson, Thomas LU and Löndahl, Carl LU (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:
author
organization
publishing date
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
2011-11-16 12:55:45
date last changed
2016-04-16 10:36:38
@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]},
  keyword      = {information set decoding,random codes,public-key cryptography,birthday technique,binary codes},
  language     = {eng},
  title        = {An improvement to Stern's algorithm},
  year         = {2011},
}