Cryptography Reference
In-Depth Information
with Grobner basis techniques. A related technique inspired by the Sidelnikov-
Shestakov attack [SS92] is described in [GL10].
The former attack recovers variables
x
i
and
y
i
which denote respectively the
diagonal and the support of the code, i.e. the
x
i
define the Vandermonde matrix
V
,andthe
y
i
define the diagonal matrix
D
, which compose the parity-check
matrix
H
=
VD
in the alternant case. In the Goppa case, these variables are
coupled by a more complex relationship, namely
y
i
=
g
(
x
i
)
−
1
.Inbothcases,
the result is a multivariate system, with equations of degree up to
t
,namely,
H
ij
=
x
j
y
j
1.
For generic codes, this system is too complex to be feasibly solved with
Grobner bases. However in the dyadic case (and, by extension, the monoidic
case), many equations are redundant, due to relation (2) of Theorem 1. Fur-
thermore, for subcodes defined over extension fields (but not over the base field
itself), it turns out that only linear and quadratic equations are enough to spec-
ify variables
x
i
and
y
i
. This feature yields a simpler multivariate system that can
be tackled with, and in fact the corresponding quasi-dyadic codes over extension
fields in [MB09] can be broken this way.
However, for the case of a subcode defined over the base field, the associated
Grobner basis is trivial if only linear and quadratic equations are used to define
the
x
i
and the
y
i
variables, and the attack fails [FOPT10b]. Although those
results were obtained for characteristic 2, at the time of writing there does not
appear to be any way to take advantage of larger characteristics to improve this
attack. Exploring this line of attack is thus left as an open problem for followup
research.
Regarding the attack in [GL10], a 'small' extension degree
m
could lead to a
successful break, but it is unclear how small
m
must be so that such an attack
would become feasible. Just how small
m
should be for the attack to be successful
in each characteristic
p>
2 is unclear, though. In this sense, the parameters listed
in this paper deliberately use relatively small values of
m
, in the hope that they
stimulate further cryptanalysis research. While we stress that these parameters
are not designed for effective deployment, the indicated security levels correspond
to the best known generic decoding attacks so as to give a realistic impression
of what practical might look like.
for 0
≤
i<t
−
1and0
≤
j<n
−
6
Parameters of Cryptographic Interest
We now assess the eciency of the proposed codes in possible practical crypto-
graphic scenarios.
Tables 1, 2, and 3 compare some of the best quasi-monoidic codes achievable
for each characteristic at several security levels. These figures only assume the
ability to correct
t
errors of equal magnitude, already taking into account that
this choice of introduced errors decreases the WF to break it. Correcting such
error patterns is possible using e.g. the decoding method for square-free Goppa
codes proposed in [BLM10]. The design minimum distance is at least
t
+1 when
differences between codewords are allowed to assume any pattern, but codewords
that differ by patterns where all magnitudes are equal are much more sparse than
