An improvement to Stern's algorithm

Thomas Johansson, Carl Löndahl

Research output: Book/ReportReportResearch

778 Downloads (Pure)


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.
Original languageEnglish
Publisher[Publisher information missing]
Publication statusUnpublished - 2011

Subject classification (UKÄ)

  • Electrical Engineering, Electronic Engineering, Information Engineering


  • information set decoding
  • random codes
  • public-key cryptography
  • birthday technique
  • binary codes


Dive into the research topics of 'An improvement to Stern's algorithm'. Together they form a unique fingerprint.

Cite this