WEBVTT
00:00:00.360 --> 00:00:02.890
All the results that we
have seen this week doesn't
00:00:02.890 --> 00:00:05.530
mean that code based
cryptography is broken.
00:00:06.440 --> 00:00:10.090
So in this session we will
see that Goppa code still
00:00:10.090 --> 00:00:11.590
resists to all these attacks.
00:00:12.710 --> 00:00:16.030
So recall that it is
assumed that Goppa codes are
00:00:16.330 --> 00:00:18.430
pseudorandom, that is
there exist no efficient
00:00:18.430 --> 00:00:19.430
distinguisher for Goppa
code. An efficient distinguisher
00:00:19.430 --> 00:00:24.290
was built for the case of high
00:00:24.290 --> 00:00:27.530
rate codes, where the rate
is very close to 1, but
00:00:27.530 --> 00:00:29.850
no generalization of this
distinguisher is known.
00:00:30.350 --> 00:00:32.720
The best known attacks are
based on the Support Splitting
00:00:32.720 --> 00:00:34.460
Algorithm and have
exponential runtime.
00:00:35.100 --> 00:00:37.570
In the third session of
this week, we have seen that
00:00:37.720 --> 00:00:40.700
Generalized Reed-Solomon codes
behave differently than random codes,
00:00:41.830 --> 00:00:44.570
with respect to the square
product that is the dimension
00:00:45.140 --> 00:00:47.630
of the square of a
Generalized Reed-Solomon code is very
00:00:47.630 --> 00:00:51.020
small compared to what it's
expected for a random code of
00:00:51.020 --> 00:00:52.050
the same length and dimension.
00:00:53.380 --> 00:00:55.720
Since an alternant code is
a subfield subcode of a
00:00:55.720 --> 00:00:59.170
Generalized Reed-Solomon
code, we might suspect that the star
00:00:59.170 --> 00:01:02.950
product of alternant codes also
behave differently from random codes.
00:01:03.320 --> 00:01:06.820
As we will see, this is true
but just for a very few cases.
00:01:07.490 --> 00:01:10.250
The following proposition
shows that the star product
00:01:10.270 --> 00:01:14.610
of two alternant codes is another
alternant code and the proof is very easy.
00:01:14.610 --> 00:01:17.990
We just need to recall
that alternant codes are
00:01:17.990 --> 00:01:20.180
subfield subcodes of
Generalized Reed-Solomon code.
00:01:20.850 --> 00:01:24.350
So how works this proof?
Let c1 be a codeword of an
00:01:24.350 --> 00:01:27.860
alternant code and c2 be
another codeword of a different
00:01:27.890 --> 00:01:29.670
alternant code with the same support.
00:01:29.940 --> 00:01:33.110
Then, there exist two
polynomials of degree smaller than n-s
00:01:33.110 --> 00:01:37.610
and another polynomial
of degree smaller than n-r
00:01:37.930 --> 00:01:40.010
such that the evaluation
of these polynomials at the
00:01:40.010 --> 00:01:41.800
corresponding
elements give our codewords.
00:01:42.270 --> 00:01:46.720
Thus the product of these
two codewords is a codeword
00:01:46.720 --> 00:01:51.620
which is the
evaluation of a polynomial of
00:01:51.620 --> 00:01:55.550
degree at most 2n - (s+r) - 1.
00:01:55.550 --> 00:01:59.210
Thus, this product
belongs to this Generalized
00:01:59.210 --> 00:02:03.200
Reed-Solomon code or, in other
words, belongs to this alternant code.
00:02:03.200 --> 00:02:07.710
Thus, the square of this
alternant code is contained in
00:02:07.710 --> 00:02:12.060
a Generalized Reed-Solomon
code but if we want that the
00:02:12.090 --> 00:02:14.540
Generalized Reed-Solomon
code is not the whole space, we
00:02:14.540 --> 00:02:17.730
need to satisfy this equation.
00:02:18.340 --> 00:02:22.100
Recall that the dimension
of the alternant code is this
00:02:22.100 --> 00:02:24.960
one and if we are talking
about non trivial alternant
00:02:24.960 --> 00:02:27.870
code then this condition holds.
00:02:28.470 --> 00:02:33.420
So if m is greater than 1,
the square of an alternant
00:02:33.420 --> 00:02:34.470
code is the whole space.
00:02:35.540 --> 00:02:38.540
However, in the special
case of Wild Goppa codes of
00:02:38.540 --> 00:02:43.350
extensions of degree 2,
then we have that the
00:02:43.350 --> 00:02:47.140
square code of its shortened code
has a abnormal
00:02:47.140 --> 00:02:49.740
dimension and we can
apply again square code
00:02:49.740 --> 00:02:53.210
considerations to break the
cryptosystem. There is another
00:02:53.210 --> 00:02:56.500
recent result which breaks
some special cases of Wild
00:02:56.500 --> 00:02:59.730
McEliece Incognito which
is a generalization of the
00:02:59.730 --> 00:03:03.340
original McEliece
cryptosystem. This attack is based in
00:03:03.340 --> 00:03:07.980
solving Algebraic system
since for some cases we can
00:03:08.020 --> 00:03:09.960
gradually reduce the
number of variables.
00:03:10.400 --> 00:03:13.490
Let us give a landscape of
the proposed families for
00:03:13.490 --> 00:03:13.740
Code-based Cryptography.
00:03:13.740 --> 00:03:17.350
Generalized Reed-Solomon
codes, Goppa codes, Subcodes of
00:03:17.350 --> 00:03:21.760
the Generalized Reed-Solomon
codes, Reed-Muller codes and
00:03:21.760 --> 00:03:24.660
Algebraic Geometry codes have been
proposed for the McEliece cryptosystem.
00:03:25.780 --> 00:03:28.870
As we have seen Generalized
Reed-Solomon codes, Subcodes
00:03:29.250 --> 00:03:31.070
of Generalized
Reed-Solomon codes of a small
00:03:31.070 --> 00:03:33.650
codimension, binary
Reed-Muller codes, Algebraic
00:03:34.360 --> 00:03:38.120
Geometry codes, Subcodes of
Algebraic Geometry codes are
00:03:38.120 --> 00:03:41.900
subject to polynomial also
exponential time attack as we
00:03:41.900 --> 00:03:44.290
have already seen in
the previous sessions.
00:03:44.900 --> 00:03:48.890
And recent results break
also few instances of Goppa
00:03:48.890 --> 00:03:51.060
codes but binary
Goppa codes still resist.
00:03:52.830 --> 00:03:55.790
Next week we will talk
about other cryptographic
00:03:55.790 --> 00:03:58.520
construction relying on
Coding theory, this week will be
00:03:58.520 --> 00:03:59.810
presented by Matthieu Finiasz.