Cryptography Reference
In-Depth Information
In Appendix A, we give a detailed example of the generation process that
illustrates some subtleties of the algorithm.
Decoding quasi-monoidic Goppa codes.
In [BLM10], an ecient decoding algo-
rithm for square-free (irreducible or otherwise) Goppa codes over
F
p
for any
prime
p
is presented. Since it fits perfectly to decode quasi-monoidic Goppa
codes, we will provide a brief description of this method in Appendix B.
Decoding GS codes is less studied than the case of Goppa codes, though both
are closely related. Let
D
be a diagonal matrix containing the scaling factors,
then adding an error pattern
e
to a GS codeword
c
amounts to adding the pattern
eD
to the codeword
cD
of the associated unscaled Goppa code. So, if the Goppa
decoder capability depends only on the weight of the error pattern (like the wild
decoder [BLP10]), then it can be used equally well for GS codes and scaling
could be used. On the other hand, if the Goppa decoder capability is best if all
error magnitudes coincide (like the “equal magnitude” decoder [BLM10]), then
scaling must not be used. It turns out that, in the latter case, keys also get
potentially smaller due to the larger number of correctable errors.
4
Monoidic Encryption and Signatures
In this section we provide the basic description about the McEliece encryption
scheme [McE78] and the Parallel-CFS signature scheme [Fin10]. Both of them
can be instantiated with our monoidic codes.
4.1 McEliece Encryption Scheme
Let the security level be
λ
. The parameters for the code below are assumed to
be chosen so that the cost of the best attack against it is at least 2
λ
(see [Pet11]
for a recent survey) takes at least 2
λ
operations.
F
q
with
q
=
p
m
for some
m>
0 and a Quasi-Monoidic code
Γ
(
L, g
) with support
L
=(
L
0
,...,L
n−
1
)
Key Generation:
Choose a prime
p
, a finite field
∈
F
q
)
n
of distinct elements and a square-free generator polynomial
g
(
∈
F
q
[
x
]of
degree
t
, satisfying
g
(
L
j
)
=0,0
j<n
, both provided by the algorithm of
k×n
p
Figure 3. Let
k
=
n
−
mt
. Compute a systematic generator matrix
G
∈
F
mt×
p
and
I
k
an
identity matrix of size
k
. The private key is
sk
:= (
L, g
) and the public key
is
pk
:= (
M, t
).
Encryption:
To encrypt a plain text
d
M
T
] for some matrix
M
for
Γ
(
L, g
), i.e.
G
=[
I
k
|−
∈
F
p
, choose an error-vector
e
∈
F
∈
n
p
{
0
,
1
}
⊆
F
with weight
wt
(
e
)
t
, and compute the cipher text
c
←
p
.
Decryption:
To decrypt a cipher text
c
dG
+
e
∈
F
p
knowing
L
and
g
, compute the
decodable syndrome of
c
, apply a decoder to determine the error-vector
e
,
and recover the plain text
d
from the first
k
columns of
c
∈
F
−
e
.
