Cryptography Reference
In-Depth Information
Simplified High-Speed High-Distance
List Decoding for Alternant Codes
Daniel J. Bernstein
Department of Computer Science
University of Illinois at Chicago, Chicago, IL 60607{7045, USA
djb@cr.yp.to
Abstract. This paper presents a simplified list-decoding algorithm to
correct any numberwof errors in any alternant code of any lengthnwith
any designed distancet+ 1 over any finite eldF
q
; in particular, in the
classical Goppa codes used in the McEliece and Niederreiter public-key
cryptosystems. The algorithm is ecient forwclose t
o, and in many
cases
slightly beyond, theF
q
Johnson boundJ
0
=n
0
p
n
0
(n
0
t 1) where
n
0
=n(q 1)=q, assumingt+ 1 n
0
. In the typical case thatqn=t2
(lgn)
O(1)
and that the parent field has (lgn)
O(1)
bits, the algorithm
usesn(lgn)
O(1)
bit operations forwJ
0
n=(lgn)
O(1)
;O(n
4:5
) bit
operations forwJ
0
+o((lgn)=lg lgn); andn
O(1)
bit operations for
wJ
0
+O((lgn)=lg lgn).
1
Introduction
Take any prime power q; integer m 1; integer n m with n q
m
; integer
t 1 with t n=m; distinct
1
;:::;
n
2 F
q
m
; and nonzero
1
;:::;
n
2 F
q
m
.
Dene
C =
(
1
f(
1
);:::;
n
f(
n
)) :
f 2 F
q
m
[x];
deg f < nt;
i
f(
i
) 2 F
q
for each i
:
This set C is an [n; nmt; t+ 1] linear code over F
q
. In other words: it is a
subspace of the F
q
-vector space F
q
; it has dimension at least nmt, i.e., at least
q
nmt
elements; and any two distinct elements of it have Hamming distance at
least t + 1, i.e., differ in at least t + 1 coordinates.
Any code C defined as above is called an alternant code. This class of
codes was introduced by Helgert in [
38
], independently by Chien and Choy in
[
22
], and independently by Delsarte in [
28
]. The class includes binary Reed{
Solomon codes, which had been introduced by Reed and Solomon in [
47
]; BCH
codes, which had been introduced by Hocquenghem in [
39
] and independently
by Bose and Ray-Chaudhuri in [
16
]; various odd-characteristic generalizations
This work was supported in part by NIST grant 60NANB10D263 and in part
by the Cisco University Research Program. Permanent ID of this document:
f529c2ab14c4ec22244b0a3f0190089b
. Date: 2011.09.10.
