Cryptography Reference
In-Depth Information
A consequence of this reduction is that, for small q, there is no point in
pushing the algorithms of the previous sections very close to their limits: instead
of correcting J
0
0:001 errors one can much more cheaply correct J
0
1:001
errors and guess the remaining error.
More generally, one can build a w-error-correcting algorithm as follows: guess e
distinct error positions (probability w(w1)(we+1)=n(n1)(ne+1));
guess the error values (probability 1=(q1)
e
); correct the errors; apply a (we)-
error-correcting algorithm. This takes (q 1)
e
n(n 1)(n e + 1)=w(w
1)(we + 1) repetitions on average.
Assume that q 2 (lg n)
O(1)
, that n=t 2 (lg n)
O(1)
, and that we bt=2c. The
average number of repetitions is then bounded by (2(q 1)n=t)
e
2 (lg n)
O(e)
;
i.e., by n
O(1)
if e 2 O((lg n)= lg lg n), and by n
o(1)
if e 2 o((lg n)= lg lg n). In
particular, this algorithm corrects J
0
+o((lg n)= lg lg n) errors using n
+2+o(1)
bit
operations, and corrects J
0
+ O((lg n)= lg lg n) errors using n
O(1)
bit operations.
6
Application to Classical Goppa Codes
The code C is called a classical Goppa code if there is a monic degree-t
polynomial g 2 F
q
m
[x] such that each
i
can be expressed as g(
i
)=A
0
(
i
). Here
A =
Q
i
(x
i
) 2 F
q
m
[x] as in Sections 3 and 4. In this case C is denoted
q
(
1
;:::;
n
;g).
Sugiyama, Kasahara, Hirasawa, and Namekawa showed in [
51
] that
q
(
1
;:::;
n
;
Y
i
g
e
i
) =
q
(
1
;:::;
n
;
Y
i
g
e
i
+[e
i
modq=q1]
i
)
when the g
i
's are distinct monic irreducible polynomials. Here [e
i
mod q = q
1] means 1 if ei
i
2 fq 1; 2q 1;:::g, otherwise 0. For example,
2
(:::;g) =
2
(:::;g
2
) if g is squarefree; this had been proven earlier by Goppa in [
31
] using
a different technique.
Write g =
Q
i
g
e
i
i
and g =
Q
i
g
e
i
+[e
i
modq=q1
i
. The Sugiyama{Kasahara{
Hirasawa{Namekawa identity
q
(:::;g) =
q
(:::;g) implies that one can corr
ec
t
w errors in
q
(:::;g) by using
a
ny w-error-correcting algorithm for
q
(:::;g).
If some ei
i
mod q = q 1 then g has larger d
e
gree than g, making all of these
error-correcting algorithms more effective for g than for g.
In particular, combining the SKHN identity with Berlekamp's algorithm cor-
rects bqt=2c errors in \wild Goppa codes"
q
(:::;g
q1
) with squarefree g. Com-
bining
the SKHN id
entity with the Guruswami{Sudan algorithm corrects nearly
n
p
n(nqt 1) errors in the same codes in polynomial time, as discussed in
[
12
, Section 5]. Combin
ing the SKHN
identity with the Koetter{Vardy algorithm
corrects nearly n
0
p
n
0
(n
0
qt 1) errors in polynomial time, as pointed out
in [
4
]. Combining the SKHN identity with the algorithm in this paper corrects
even more errors in polynomial time.
See also [
5
] for a different approach that decodes more errors in some cases,
particularly for q = 3.
