Cryptography Reference
In-Depth Information
Organization.
In Section 2, we introduce the basic concepts of coding theory,
which are relevant to our proposal. In Section 3, we introduce our new class
of quasi-monoidic codes and show how to construct Goppa/GS codes that are
quasi-monoidic. Next, we describe how to instantiate the standard code-based
encryption and signature schemes with this family in Section 4. Afterwards, in
Section 5 we assess the security properties of our proposal, and in Section 6 we
suggest a few actual parameters to encourage further analysis. Finally, in Section
7 we briefly argue why the matrix-vector products for quasi-monoidic matrices
can be computed eciently using a discrete Fourier transform.
2CodingTh ory
Basic concepts.
We will start with some matrix descriptions. For both descrip-
tions,
t
is an integer greater than zero. Given a sequence
L
=(
L
0
,...,L
n−
1
)
∈
q
,the
Vandermonde matrix
vdm(
t, L
)isthe
t
F
n
matrix with elements
V
Tij
=
L
j
. Given a polynomial
g
with coecients (
g
1
,...,g
t
)
×
q
,the
Toeplitz ma-
∈
F
trix
toep(
g
1
,...,g
t
)isthe
t
i
and
T
Tij
:= 0 otherwise. The following are the
GRS
,
alternant
and
Goppa codes
definitions.
Definition 1.
Given a sequence
L
=(
L
0
,...,L
n−
1
)
×
t
matrix with elements
T
Tij
:=
g
t−i
+
j
for
j
∈
F
q
of distinct elements
q
of nonzero elements, the
General-
ized Reed-Solomon code
GRS
r
(
L, D
)
is the
[
n, k, r
]
linear error-correcting code
defined by the parity-check matrix
andasequence
D
=(
D
0
,...,D
n−
1
)
∈
F
diag(
D
)
.
An
alternant code
is a subfield subcode of a Generalized Reed-Solomon code.
Definition 2.
Given a prime power
p
,
q
=
p
d
H
=vdm(
r
−
1
,L
)
·
for some
d
, a sequence
L
=
q
(
L
0
,...,L
n−
1
)
∈
F
of distinct elements and a polynomial
g
(
x
)
∈
F
q
[
x
]
of degree
t
such that
g
(
L
i
)
=0
for
0
i<n
,the
Goppa code
Γ
(
L, g
)
over
F
p
is defined
by the parity-check matrix
H
=toep(
g
1
,...,g
t
)
·
vdm(
t, L
0
,...L
n−
1
)
(1)
diag(
g
(
L
0
)
−
1
,...,g
(
L
n−
1
)
−
1
)
·
3]
, we can omit
toep(
g
1
,...,g
t
)
from this construction,
making it easy to see that
Goppa codes
are also
alternant codes
over
By
[MS77][Ch. 12,
§
F
p
corre-
sponding to
GRS
t
(
L, D
)
where
D
=(
g
(
L
0
)
−
1
,...,g
(
L
n−
1
)
−
1
)
.
Goppa codes have minimum distance at least
t
+ 1. Binary Goppa codes improve
this to at least 2
t
+ 1. It turns out that, although this improvement does not
hold in general for larger characteristics, codewords that differ by vectors whose
components are all equal are on average much more sparsely distributed. Thus,
while the unambiguous correction of general errors in odd characteristics can
in general not proceed beyond about
t/
2 errors, correction of error patterns of
homogeneous (all-equal) error magnitudes can probabilistically reach as much
as
t
errors [BLM10].
