WEBVTT
00:00:00.220 --> 00:00:02.880
In this session, we will present an
attack against Algebraic Geometry codes (AG codes).
00:00:02.920 --> 00:00:05.690
Algebraic Geometry codes
is determined by a triple.
00:00:06.860 --> 00:00:11.280
First of all, an
algebraic curve of genus g, then a
00:00:11.280 --> 00:00:14.320
n-tuple of rational points
and then a divisor which has
00:00:14.320 --> 00:00:16.990
disjoint support from the n-tuple P.
00:00:16.990 --> 00:00:20.150
Then, the Algebraic
Geometry code is obtained by
00:00:20.150 --> 00:00:22.970
evaluating at P all
functions that belong to the vector
00:00:22.970 --> 00:00:24.650
space associated to the divisor E.
00:00:26.970 --> 00:00:29.710
Some properties of these
codes are nearly optimal codes,
00:00:30.210 --> 00:00:33.540
that is, their designed minimum
distance is nearly the optimal one.
00:00:33.540 --> 00:00:38.200
Moreover, the dual of an
AG-code is again an AG-code.
00:00:39.060 --> 00:00:42.330
What about using Algebraic
Geometry codes in code-based
00:00:42.330 --> 00:00:44.980
cryptography? Janwa and
Moreno suggest to use Algebraic
00:00:45.250 --> 00:00:47.290
Geometry codes for the
McEliece cryptosystem.
00:00:47.290 --> 00:00:52.280
This is a suitable proposal
since these codes are nearly
00:00:52.310 --> 00:00:53.490
optimal and have
efficient decoding algorithms.
00:00:55.490 --> 00:00:58.820
If we talk about codes over
curves of genus zero then we
00:00:58.820 --> 00:01:00.830
are talking about
generalized Reed-Solomon codes, as we
00:01:00.830 --> 00:01:05.320
will see in the next slides.
So, for a curve of genus 0,
00:01:05.430 --> 00:01:07.020
this proposal is broken.
00:01:07.130 --> 00:01:11.950
If we talk about codes over
curves of genus 1 and 2, then
00:01:11.950 --> 00:01:14.170
this proposal is
broken by Faure and Minder.
00:01:14.170 --> 00:01:17.290
However, this attack has
several drawbacks which makes it
00:01:17.310 --> 00:01:21.980
impossible to extend to a
higher genera. But there is an
00:01:21.980 --> 00:01:23.130
attack for the general case.
00:01:24.580 --> 00:01:29.440
We will explain here this
general attack. First over
00:01:29.440 --> 00:01:31.390
generalized Reed-Solomon
codes and then we will give an
00:01:31.390 --> 00:01:33.110
idea on how it works
for the general case.
00:01:33.110 --> 00:01:36.660
Recall that the
generalized Reed-Solomon codes are
00:01:36.880 --> 00:01:39.790
Algebraic Geometry codes
over curves of genus 0.
00:01:40.170 --> 00:01:42.760
Indeed, if we consider the
projective line, this curve
00:01:42.760 --> 00:01:46.120
has genus 0 and its
points are of the form
00:01:47.700 --> 00:01:51.170
(x:y)
00:01:51.170 --> 00:01:54.200
Now, we will consider P the n-tuple
00:01:57.340 --> 00:02:02.270
of points formed by these
points and we take E to
00:02:02.270 --> 00:02:05.200
be K-1 times the point at the infinity.
00:02:05.200 --> 00:02:09.980
A basis of the
vector space associated to
00:02:09.980 --> 00:02:12.000
this divisor is the following one.
00:02:12.730 --> 00:02:17.580
And if we evaluate this
basis at the points P, we get a
00:02:17.580 --> 00:02:21.260
generator matrix of this
AG code, which is also a
00:02:21.260 --> 00:02:24.020
generator matrix of a
generalized Reed-Solomon code of
00:02:24.020 --> 00:02:28.610
dimension k associated to the
pair (a,1), the all-ones vector.
00:02:29.330 --> 00:02:31.990
Let us recall the attack
against generalized Reed-Solomon
00:02:31.990 --> 00:02:34.740
code which retrieves an
error correcting pair.
00:02:35.160 --> 00:02:37.810
We have already presented this
attack in a previous session.
00:02:38.520 --> 00:02:41.050
So, if we retrieve an error
correcting pair, we have an
00:02:41.050 --> 00:02:43.460
efficient decoding algorithm,
so we break the cryptosystem.
00:02:45.170 --> 00:02:46.340
So how does this attack work?
00:02:46.810 --> 00:02:49.430
First of all, recall that
if we know a generalized
00:02:49.430 --> 00:02:52.380
Reed-Solomon code
associated to the pair (a, b) of the
00:02:52.380 --> 00:02:57.120
dimension k and dimension
k-1, then we can obtain a
00:02:57.120 --> 00:03:01.250
generalized Reed-Solomon code of
dimension k-2 by solving this equation.
00:03:03.030 --> 00:03:06.070
So, if we apply this
property iteratively,
00:03:08.000 --> 00:03:09.660
we can build the
following decreasing sequence.
00:03:12.280 --> 00:03:14.470
These properties will
be used for the attack.
00:03:14.690 --> 00:03:17.560
Also recall that,
if we have a generalized
00:03:18.190 --> 00:03:22.920
Reed-Solomon code, then this pair is
00:03:23.120 --> 00:03:25.420
an error correcting
pair for our code.
00:03:25.980 --> 00:03:27.170
But we can do it better.
00:03:27.770 --> 00:03:32.420
Suppose that we just know
a code B of this type, then
00:03:32.520 --> 00:03:35.520
A can be obtained by
applying linear algebra.
00:03:35.860 --> 00:03:37.940
Let us explain how this attack works.
00:03:37.940 --> 00:03:41.340
Recall that a generator
matrix of a generalized
00:03:41.340 --> 00:03:44.670
Reed-Solomon code is the
public key and also the number
00:03:44.670 --> 00:03:46.030
of errors that we can correct.
00:03:46.460 --> 00:03:50.470
So first of all, we
determine the following two codes
00:03:50.560 --> 00:03:54.110
which are the first two
elements of this filtration.
00:03:55.000 --> 00:03:58.930
The first one is the dual
of the public code and the
00:03:58.930 --> 00:04:03.490
second one is just shortening the
dual code in the first position.
00:04:03.610 --> 00:04:08.020
Recall that we can obtain
the generator matrix of this
00:04:08.020 --> 00:04:09.850
shortened code by
applying linear algebra.
00:04:10.620 --> 00:04:14.060
Applying the previous
property, we obtain a code B.
00:04:14.410 --> 00:04:18.400
With this, the code B of
an error correcting pair,
00:04:19.270 --> 00:04:23.860
A, from the error
correcting pair, can be obtained by
00:04:23.860 --> 00:04:25.160
solving linear algebra.
00:04:25.490 --> 00:04:28.610
So we have a method for
retrieving an error correcting
00:04:28.610 --> 00:04:32.640
pair for our code, except
if there is an error in the
00:04:32.640 --> 00:04:35.050
first position, which
is not a high problem.
00:04:35.710 --> 00:04:38.970
Let us explain now how to
generalize the previous attack
00:04:39.010 --> 00:04:40.480
to Algebraic Geometry code.
00:04:41.700 --> 00:04:46.470
Suppose now that we
have these two codes.
00:04:46.470 --> 00:04:50.540
Then, applying linear
algebra, we can obtain a code
00:04:50.680 --> 00:04:52.260
associated to this triple.
00:04:53.240 --> 00:04:57.550
And iteratively applying
these propositions, we can
00:04:57.550 --> 00:04:58.960
obtain the following
decreasing sequence.
00:04:58.960 --> 00:05:03.940
This pair of codes is an
error correcting pair for this
00:05:03.940 --> 00:05:08.500
code. That is, A is
associated with a triplet (X, P, F) and
00:05:08.530 --> 00:05:13.470
B is associated to a
triplet (X, P, E-F), where
00:05:13.500 --> 00:05:17.550
F is any divisor of degree t+g.
00:05:18.070 --> 00:05:20.810
But we can do it better.
00:05:20.810 --> 00:05:25.740
Just if we have a code of
this type and we apply linear
00:05:25.740 --> 00:05:30.360
operations, we can obtain a
code A, such that A and B is an
00:05:30.360 --> 00:05:31.810
error correcting pair for C.
00:05:32.330 --> 00:05:35.020
Now we have all the
ingredients to present the attack
00:05:35.050 --> 00:05:36.380
against Algebraic Geometry code.
00:05:36.380 --> 00:05:40.550
So, the public key is a
generator matrix of an algebraic
00:05:40.550 --> 00:05:43.670
geometry code and also the
number of errors that we can correct.
00:05:44.060 --> 00:05:47.960
First of all, we
compute these two codes: the
00:05:48.860 --> 00:05:52.260
first one is the dual of
the public code and the second
00:05:52.260 --> 00:05:56.130
one is just the codewords
which are 0 in the first position.
00:05:56.130 --> 00:06:01.060
So, applying linear algebra, we
have a generator matrix of both codes.
00:06:01.200 --> 00:06:05.300
Applying the previous
proposition if we know the first
00:06:05.330 --> 00:06:08.390
two elements of the
sequence, we can obtain the complete
00:06:08.390 --> 00:06:11.450
sequence until we arrive
to a code of this type.
00:06:12.720 --> 00:06:15.670
A code of this type is what
we need to retrieve an error
00:06:15.670 --> 00:06:17.560
correcting pair for our code C.
00:06:18.700 --> 00:06:22.960
So we have retrieved an error
correcting pair for our code C.
00:06:23.590 --> 00:06:28.430
With this, we have an efficient
decoding algorithm for the public key.
00:06:28.460 --> 00:06:30.270
So, we break the cryptosystem.
00:06:30.780 --> 00:06:34.740
All the results that we
have presented this week doesn't
00:06:34.740 --> 00:06:37.070
mean that McEliece
cryptosystem is broken.
00:06:38.390 --> 00:06:42.420
As we will see in the next
session, Goppa codes still resist.