Cryptography Reference
In-Depth Information
In this paper we use the McEliece cryptosystem, the Niederreiter cryptosys-
tem, etc. with codes of the form
q
(a
1
;:::;a
n
;fg
q1
), where f and g are coprime
squarefree monic polynomials.
If g= 1 then
q
(a
1
;:::;a
n
;fg
q1
) is the squarefree Goppa code
q
(a
1
;:::;a
n
;f);
these are, for q = 2, the traditional codes used in the McEliece cryptosystem.
If f = 1 then
q
(a
1
;:::;a
n
;fg
q1
) is thewildGoppacode
q
(a
1
;:::;a
n
;g
q1
),
which we proposed in [6] for thewildMcEliececryptosystem; what makes these
codes interesting is that they can correct bqt=2c errors, or even slightly more
using list decoding.
The Goppa code with polynomial fg
q1
has dimension at least nm(s+ (q
1)t), where s is the degree of f and t is the degree of g. Theorem 2.1 below says
that fg
q
gives the same Goppa code. It follows that
q
(a
1
;a
2
;:::;a
n
;fg
q1
) has
minimum distance at least s + qt + 1. One can plug fg
q
into (e.g.) the alternant
decoder described in [6, Section 5] to eciently decode b(s + qt)=2c errors, or
into the list-decoder described in [5] to eciently decode more errors.
Theorem 2.1 is a special case of a theorem of Sugiyama, Kasahara, Hirasawa,
and Namekawa [24]. To keep this paper self-contained we give a streamlined
proof here, generalizing the streamlined proof for f = 1 from [6].
Theorem2.1.Letqbeaprimepower.Letmbeapositiveinteger.Letnbe
anintegerwith1 n q
m
.Leta
1
;a
2
;:::;a
n
bedistinctelementsofF
q
m
.Let
fandgbecoprimemonicpolynomialsinF
q
m
[x]thatbothdonotvanishat
anyofa
1
;:::;a
n
.Assumethatgissquarefree.Then
q
(a
1
;a
2
;:::;a
n
;fg
q1
) =
q
(a
1
;a
2
;:::;a
n
;fg
q
).
Proof. If
P
i
c
i
=(xa
i
) = 0 inF
q
m
[x]=(fg
q
) then certainly
P
i
c
i
=(xa
i
) = 0
inF
q
m
[x]=(fg
q1
).
Conversely, consider any (c
1
;c
2
;:::;c
n
) 2F
n
q
such that
P
i
c
i
=(xa
i
) = 0
inF
q
m
[x]=(fg
q1
); i.e., fg
q1
divides
P
i
c
i
=(x a
i
) inF
q
m
[x]. We need to
show that fg
q
divides
P
i
c
i
=(x a
i
) inF
q
m
[x], in particular that g
q
divides
P
i
c
i
=(xa
i
) inF
q
m
[x]. Find an extension k ofF
q
m
so that g splits into linear
factors in k[x]. Then
P
i
c
i
=(xa
i
) = 0 in k[x]=g
q1
, so
P
i
c
i
=(xa
i
) = 0 in
k[x]=(xr)
q1
for each factor xr of g. The elementary series expansion
(a
i
r)
2
(xr)
2
xa
i
=
1
1
a
i
r
xr
(a
i
r)
3
then implies
X
a
i
r
+ (xr)
X
i
(a
i
r)
2
+ (xr)
2
X
i
c
i
(a
i
r)
3
+ = 0
in k[x]=(xr)
q1
; i.e.,
P
i
c
i
=(a
i
r) = 0,
P
i
c
i
=(a
i
r)
2
= 0, . . . ,
P
i
c
i
=(a
i
c
i
c
i
i
r)
q1
= 0. Now take the qth power of the equation
P
i
c
i
=(a
i
r) = 0, and use
the fact that ci
i
2F
q
, to obtain
P
i
c
i
=(a
i
r)
q
= 0. Work backwards to see that
P
i
c
i
=(xa
i
) = 0 in k[x]=(xr)
q
.
