Cryptography Reference
In-Depth Information
full error-correction capability when given their generator matrix in a disguised
form [McE78]. At ASIACRYPT 2001, Courtois, Finiasz, and Sendrier showed
that a signature scheme can be based on the same problem [CFS01].
So far, no algorithm is capable of decoding Goppa codes, or the closely related
Generalized Srivastava (GS) codes, better than completely random linear codes.
And the problem of decoding random linear codes is widely believed to be very
hard. The main drawback of cryptographic schemes which use Goppa/GS codes
is that their keys are several orders of magnitude bigger than those of classical
schemes with comparable practical security. This issue of big key sizes is directly
related to the size of the code description. This is the main problem which we
will address.
Related Work.
The problem of finding Goppa/GS codes with small descriptions
is not new.
In [BLP10], Bernstein, Lange, and Peters find that Goppa codes over
F
q
,
where the Goppa polynomial has
t
roots of multiplicity
r
−
1and
r
divides
q
,
have the capability of correcting
errors they can correct with an alternant decoder. These codes are called wild
Goppa codes and due to their increased correction capability, one can use codes
with smaller descriptions for the same level of practical security.
Another major breakthrough in saving description size has been achieved
in [MB09] by Barreto and Misoczki. They define a new class of quasi-dyadic
codes, which have very compact descriptions, and show that this has a non-
empty intersection with the class of binary Goppa codes. They also show how to
generate codes in this intersection eciently and give some preliminary param-
eters. Later, in [BCMN10], they are joined by Cayrel and Niebuhr and go on to
show that quasi-dyadic Goppa codes can be generated in such a way that they
are dense enough to be usable with the CFS signature scheme.
More generally, other proposals aimed at key reduction not restricted to Goppa
codes were proposed [BC07, Gab05, MRS00] but subsequently broken [OTD10];
in special, [FOPT10a] and [GL10] presented structural attacks against McEliece
variants with compact keys, being effective against quasi-cyclic codes [BCGO09].
With respect to the binary quasi-dyadic Goppa codes, this attack was not suc-
cessful and, focused on increasing the effort of this attack, Persichetti proposed a
construction using quasi-dyadic Srivastava codes [Per11], instead of Goppa ones,
providing keys with similar size to the keys presented in [MB09].
Most attempts at decreasing key sizes deal with codes in characteristic 2, in
spite of evidence [Pet10] that odd characteristics may offer security advantages.
Our Contribution.
In this paper we introduce a new class of codes which allow
for an extremely small representation and ecient processing. Our so called
quasi-monoidic codes are a generalization of quasi-dyadic codes to finite fields of
odd characteristics.
Using quasi-monoidic Goppa codes for the McEliece cryptosystems and CFS
signature scheme, one can potentially obtain smaller key sizes than before, as
exemplified by Tables 1 and 3 in Section 6. For example, we find that many wild
Goppa codes are in fact quasi-monoidic.
rq/
2
errors instead of the usual
(
r
−
1)
q/
2
