An improvement to Stern's algorithm

Thomas Johansson, Carl Löndahl

Research output: Book/ReportReportResearch

640 Downloads (Pure)

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

Subject classification (UKÄ)

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

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

Fingerprint

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

Cite this