WEBVTT
00:00:00.280 --> 00:00:05.250
The final session of this week is
devoted to Decoding One Out of Many.
00:00:05.850 --> 00:00:09.440
Decoding One Out of Many
is interested in solving the
00:00:09.440 --> 00:00:11.890
following variant
of Syndrome Decoding.
00:00:13.490 --> 00:00:17.210
In this variant, the only
difference with the usual
00:00:17.210 --> 00:00:22.110
Syndrome Decoding is
that we are interested in
00:00:22.150 --> 00:00:26.840
a set of syndromes
rather than a single syndrome.
00:00:26.980 --> 00:00:31.890
So, the instance will be S, a
00:00:31.890 --> 00:00:35.650
set of syndromes of size N.
00:00:35.670 --> 00:00:40.470
H, a parity-check
matrix and w an integer,
00:00:40.610 --> 00:00:42.290
the weight we are looking for.
00:00:42.540 --> 00:00:46.990
And we are interested
in an error e, such that
00:00:47.650 --> 00:00:52.440
the syndrome of e is an
element of the set S with e
00:00:53.010 --> 00:00:54.720
of weight w or less.
00:00:55.470 --> 00:01:00.230
We will denote CSD sub N of H, S, w,
00:01:00.800 --> 00:01:03.290
the set of all
solutions to the above problem.
00:01:05.130 --> 00:01:10.050
As for CSD1 which is, in
fact, the plain CSD, we will
00:01:10.050 --> 00:01:12.660
only consider solvable instances.
00:01:12.830 --> 00:01:16.840
And by solvable here
instances, we mean something very
00:01:16.840 --> 00:01:21.650
strong, we mean
that every syndrome in
00:01:21.900 --> 00:01:24.150
the set S belongs to that set.
00:01:24.150 --> 00:01:27.400
So, every syndrome in
the set S corresponds
00:01:29.350 --> 00:01:32.200
to an error of weight w.
00:01:32.200 --> 00:01:35.360
We expect with this
technique - and I will show you how
00:01:35.980 --> 00:01:40.800
we obtain this -, we
expect to get all solutions, the
00:01:41.020 --> 00:01:46.000
N solution to the problem at
the expense of a factor only √ N.
00:01:48.040 --> 00:01:52.460
Or alternatively, we
expect to get a single
00:01:52.460 --> 00:01:57.110
solution to the problem,
but to gain a factor √ N
00:01:57.870 --> 00:01:58.920
to obtain that solution.
00:02:00.750 --> 00:02:03.620
Again, I will start
with Birthday Decoding.
00:02:03.770 --> 00:02:08.030
Now, I want to solve
Birthday Decoding with multiple
00:02:08.060 --> 00:02:11.800
instances. I will
00:02:12.990 --> 00:02:17.040
now split the matrix into
two parts, but you can see here
00:02:17.040 --> 00:02:21.830
that n1 will be larger than
00:02:22.300 --> 00:02:26.850
n2, that is the left part
of the matrix is larger than
00:02:26.850 --> 00:02:28.430
the right part of the matrix.
00:02:28.810 --> 00:02:33.550
Also, the weight w,
instead of being divided in
00:02:33.740 --> 00:02:37.660
two equal parts is divided in w1+w2,
00:02:39.150 --> 00:02:42.370
and possibly one of those
weights, in fact, it will be
00:02:42.370 --> 00:02:45.920
w1, is greater than
the other part w2.
00:02:46.380 --> 00:02:49.620
I define those two sets:
the first set is simply a set
00:02:50.000 --> 00:02:54.990
of syndromes of errors
e1*(H1 transpose) when
00:02:55.180 --> 00:02:56.820
the weight of e1 is w1.
00:02:57.600 --> 00:03:01.730
But the second list
is in fact formed of
00:03:02.700 --> 00:03:07.400
the syndrome according to H2
that is e2*(H2 transpose) +
00:03:11.740 --> 00:03:16.290
any syndrome s. So, the list L2 will
00:03:16.840 --> 00:03:21.020
have a size equal to the number of
00:03:21.020 --> 00:03:25.970
syndromes N * (n2, w2)
that is the number of errors
00:03:26.110 --> 00:03:30.380
of weight w2, when the first list L1
00:03:31.010 --> 00:03:33.020
will have simply a size (n1,w1).
00:03:33.020 --> 00:03:37.390
And we will choose w1 and w2
00:03:38.790 --> 00:03:43.230
in proportion of the length
n1 and n2, that is, we are
00:03:43.230 --> 00:03:46.660
going to choose them
such that (w1/n1) = (w2/n2).
00:03:46.660 --> 00:03:47.860
And the following
00:03:51.710 --> 00:03:56.010
claim is true. Every time
the number of syndromes I am
00:03:58.650 --> 00:04:02.110
addressing in my N
Computational Syndrome Decoding,
00:04:04.590 --> 00:04:07.900
every time this number is
smaller than (n,w) we can
00:04:07.900 --> 00:04:12.490
obtain all solutions of
the Computational Syndrome
00:04:12.490 --> 00:04:17.150
Decoding for a set of N syndromes,
00:04:17.880 --> 00:04:21.950
for a cost which is the
following, up to a polynomial factor.
00:04:22.390 --> 00:04:27.340
And this corresponds roughly to an
00:04:27.340 --> 00:04:32.260
additional factor √ N to the
00:04:32.260 --> 00:04:33.600
complexity of the problem.
00:04:34.160 --> 00:04:37.920
But we get N times more solutions.
00:04:39.820 --> 00:04:44.750
Now if we try to use these
multiple instances Birthday
00:04:44.750 --> 00:04:48.950
Decoding in information set
decoding, we will obtain the
00:04:49.200 --> 00:04:50.470
improvement we expect.
00:04:51.470 --> 00:04:56.380
So now, we consider a problem CSD sub
00:04:56.460 --> 00:05:00.540
N of H, S, w which has N solutions.
00:05:00.760 --> 00:05:02.400
One for each syndrome.
00:05:02.930 --> 00:05:06.080
And we only want to
obtain one of those solutions.
00:05:06.230 --> 00:05:08.940
So, N∞ will not change.
00:05:08.970 --> 00:05:11.130
It is still the
same counting problem.
00:05:11.290 --> 00:05:16.250
And the formula for N∞ is the
00:05:16.250 --> 00:05:18.170
same as for the Dumer algorithm.
00:05:18.820 --> 00:05:23.620
If I only need one
solution, I expect that this number
00:05:24.160 --> 00:05:28.380
of iterations will be
divided by N, the number of
00:05:28.380 --> 00:05:33.210
solutions. And I
can do that as long as
00:05:33.260 --> 00:05:35.420
N is smaller than N∞.
00:05:35.590 --> 00:05:40.060
The iteration cost will
be the Birthday Decoding
00:05:40.090 --> 00:05:43.300
problem with multiple
instances of the previous slide.
00:05:43.340 --> 00:05:46.030
So, we know the
complexity of that problem.
00:05:46.560 --> 00:05:51.290
And from the claim I gave
in the previous slide, we
00:05:51.290 --> 00:05:55.490
know that this will hold as long as N
00:05:56.140 --> 00:05:58.700
is not larger than (k+l,p).
00:06:00.400 --> 00:06:04.020
Putting everything together,
I have a workfactor for the
00:06:04.020 --> 00:06:08.670
DOOM Information
Set Decoding given by
00:06:08.670 --> 00:06:12.680
this formula, which
is minimized over P.
00:06:12.680 --> 00:06:16.520
You see the value of l
also changes slightly if we
00:06:16.520 --> 00:06:20.450
compare that with the
formula for the Dumer algorithm and
00:06:20.470 --> 00:06:25.330
essentially, here we gain a
factor √ N and I have some
00:06:25.330 --> 00:06:29.800
conditions for the value of
N that is this algorithm will
00:06:29.800 --> 00:06:33.690
work as long as the
number of instances that I'm
00:06:33.730 --> 00:06:37.270
addressing simultaneously is
not larger than the minimum
00:06:37.270 --> 00:06:38.450
of those two values.
00:06:39.400 --> 00:06:44.110
Decoding out of many
techniques can also be applied
00:06:44.440 --> 00:06:47.610
at least for an Order 2
Generalized Birthday Algorythm.
00:06:48.650 --> 00:06:51.840
We can do that in
particular when N is
00:06:52.890 --> 00:06:55.380
exactly equal to (N/3,w/3).
00:06:59.170 --> 00:07:03.470
And in that case, I will
cut the matrix H into three
00:07:03.470 --> 00:07:07.180
parts only, and I will build
four lists, because we need
00:07:07.180 --> 00:07:09.190
four lists for an Order 2 GBA.
00:07:11.390 --> 00:07:14.440
The first three lists are
obtained from the parity check
00:07:14.440 --> 00:07:18.280
matrix, as usual,
with a zero syndrome,
00:07:19.110 --> 00:07:23.630
and the last list,
L4, will contain all the
00:07:23.630 --> 00:07:26.270
syndromes that I target.
00:07:26.500 --> 00:07:31.380
If I do that, finding solutions
00:07:32.270 --> 00:07:37.120
to the list problem, that
is, finding x1+x2+x3+x4=0 with
00:07:40.400 --> 00:07:44.890
one element in each
list, provides exactly a
00:07:44.890 --> 00:07:49.470
solution of the CSD
sub N problem for H,
00:07:49.510 --> 00:07:53.950
S, w. This will be obtained for a
00:07:53.950 --> 00:07:58.800
cost equal to the
size of my list, which
00:07:58.800 --> 00:08:00.780
is (n/3,w/3). In fact, up
00:08:04.170 --> 00:08:07.950
to a polynomial factor,
this is equal to √ (N,w).
00:08:11.360 --> 00:08:15.800
If we compare that with the
Birthday Decoding Complexity,
00:08:15.800 --> 00:08:20.530
that is √ (N,w),
again, we have gained
00:08:20.530 --> 00:08:22.820
this factor √ N, roughly.
00:08:22.970 --> 00:08:27.770
So, this is the end
of this week of course,
00:08:28.600 --> 00:08:32.990
and next week will be
devoted to Key Attacks.