WEBVTT
00:00:00.340 --> 00:00:03.640
In this session, we will
talk about the easy map of the
00:00:03.640 --> 00:00:06.330
one-way trapdoor functions
based on error-correcting codes.
00:00:07.330 --> 00:00:10.040
We suppose that the set of
all messages that we wish to transmit
00:00:10.040 --> 00:00:13.820
is the set of k-tuples having
elements from the field Fq.
00:00:13.820 --> 00:00:17.940
There are qk possible
messages and we referred to
00:00:18.600 --> 00:00:20.340
it as the message space.
00:00:20.340 --> 00:00:22.880
In order to detect and
possibly correct errors, we add
00:00:22.880 --> 00:00:27.710
some redundancy, thus the k
tuples will be embedded into
00:00:27.710 --> 00:00:29.950
n-tuples with n greater than k.
00:00:30.630 --> 00:00:34.840
In this MOOC, we will focus on linear
encoder that is linear transformations.
00:00:35.260 --> 00:00:38.430
Every linear transformation can be
represented by a matrix multiplication.
00:00:38.430 --> 00:00:43.400
Thus our code, which is the
image of the message space,
00:00:43.730 --> 00:00:47.520
consists of codewords of the
same length which are closed
00:00:47.540 --> 00:00:48.720
under addition and
scalar multiplication.
00:00:48.720 --> 00:00:53.300
If the encoded matrix
is injective, that is, if
00:00:53.580 --> 00:00:56.860
no two messages have the
same image, or in other words,
00:00:56.860 --> 00:00:59.650
if the encoding matrix has
rank k, then we consider a one
00:00:59.980 --> 00:01:02.980
to one correspondence between the
message space and the linear code.
00:01:03.910 --> 00:01:06.710
These are the cases that
will care, where the encoding is
00:01:06.710 --> 00:01:10.390
some multiplication by a
matrix of rank k, that is, our code
00:01:10.430 --> 00:01:12.810
is a vector subspace of Fq^n.
00:01:13.230 --> 00:01:16.700
The following properties
are satisfied, the sum of two
00:01:16.700 --> 00:01:19.880
codewords is another
codeword, the multiplication of a
00:01:19.880 --> 00:01:22.520
codeword by a constant is
again a codeword and the zero
00:01:22.520 --> 00:01:26.970
vector is always a codeword.
A basis of a vector space is
00:01:26.970 --> 00:01:30.720
linearly independent and
spans the vector space.
00:01:30.720 --> 00:01:34.230
The encoding matrix is a
basis for our linear code which
00:01:34.230 --> 00:01:36.800
will be called a generator matrix.
00:01:37.430 --> 00:01:42.200
A basis for a vector space is not
unique, neither is the generator matrix.
00:01:43.920 --> 00:01:46.450
Different encoding matrices
could lead to the same linear code.
00:01:47.180 --> 00:01:50.140
However, all bases have the
same number of elements which
00:01:50.140 --> 00:01:51.060
defines the dimension of a linear code.
00:01:51.060 --> 00:01:55.410
Thus, all generator matrices have
the same size and the same
00:01:56.480 --> 00:01:59.330
rank. If the encoding
matrix has rank k then we simply
00:01:59.330 --> 00:02:03.730
say that our code is a
[n,k]q code: n defines the length,
00:02:03.940 --> 00:02:06.780
k the dimension and q the
number of elements of the
00:02:06.780 --> 00:02:09.420
alphabet that we are
using. Elementary row operations
00:02:09.420 --> 00:02:12.680
performed on a generator
matrix that is multiplying a row
00:02:13.090 --> 00:02:15.990
by a scalar, adding a
scalar multiple of one row to
00:02:15.990 --> 00:02:19.130
another or extending two
rows, give different generator
00:02:19.130 --> 00:02:20.490
matrices for the same code.
00:02:21.090 --> 00:02:23.770
Some generator matrices could
be more useful than others,
00:02:24.020 --> 00:02:27.320
for example, if we have a
generator matrix of this form
00:02:27.580 --> 00:02:31.180
where, at the beginning,
we have the identity matrix,
00:02:31.450 --> 00:02:36.390
then the information
symbols will appear in the first
00:02:36.390 --> 00:02:39.750
k position of the
codeword, that is, the message will
00:02:39.750 --> 00:02:42.110
appear in the first k
position of the codeword.
00:02:42.110 --> 00:02:45.040
This matrix is said to
be in a standard form.
00:02:45.750 --> 00:02:49.320
If the encoding matrix is
injective, in other words, if
00:02:49.680 --> 00:02:52.930
the direct matrix has rank
k, then there exists a one to
00:02:52.930 --> 00:02:56.380
one correspondence between the
message space and the linear code.
00:02:56.870 --> 00:03:00.380
Recall that we have q^k
possible messages so we
00:03:00.380 --> 00:03:02.900
have q^k possible
codewords in our code.
00:03:03.800 --> 00:03:07.810
We have already described the
repetition code, the idea is very simple.
00:03:07.850 --> 00:03:10.520
We just repeat each
message symbol several times.
00:03:10.850 --> 00:03:14.320
For example, if we use the
3-repetition code, then this
00:03:14.320 --> 00:03:16.050
message will become this codeword.
00:03:16.050 --> 00:03:19.470
This is a generator matrix
for the 3-repetition code.
00:03:19.470 --> 00:03:24.250
The 3-repetition code is a
code of length n and dimension 1.
00:03:25.710 --> 00:03:29.500
Consider the binary code
given by this list of codewords,
00:03:30.660 --> 00:03:33.720
instead of listing all
codewords, we can just select four
00:03:33.720 --> 00:03:38.710
of them which are linearly
independent to create a generator matrix.
00:03:38.910 --> 00:03:41.300
But this generator matrix
is not unique, we can choose
00:03:41.340 --> 00:03:44.750
another four which give us
another generator matrix of this code.
00:03:45.410 --> 00:03:48.230
On this sequence, we have
seen the easy mapping of the
00:03:48.230 --> 00:03:49.020
one-way trapdoor function
of code-based cryptography.
00:03:51.700 --> 00:03:54.690
We have seen that it is easy
and fast to encode a message
00:03:54.690 --> 00:03:57.170
using linear transformation,
that is matrix multiplication.
00:03:58.630 --> 00:04:01.400
In the next sequence, we
will explain another way of
00:04:01.430 --> 00:04:03.610
defining linear code
using the parity check matrix.
00:04:03.610 --> 00:04:07.360
This matrix will play an
important role on the hard
00:04:07.360 --> 00:04:11.040
mapping of the one-way trapdoor
function that is the decoding process.