Paper on decoding random linear codes

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.

Available here.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s