WEBVTT
00:00:00.500 --> 00:00:02.460
In this session, we are
going to see how to build an
00:00:02.460 --> 00:00:05.140
efficient provably secure
one-way function from coding theory.
00:00:05.890 --> 00:00:08.140
As you know, a one-way
function is a function which is
00:00:08.260 --> 00:00:11.250
simple to evaluate and
which should be as fast as
00:00:11.250 --> 00:00:15.350
possible and hard to invert,
ideally with good security arguments.
00:00:16.350 --> 00:00:17.670
There are many
applications of one-way functions,
00:00:18.330 --> 00:00:20.930
especially in symmetric
cryptography. For example, for
00:00:21.020 --> 00:00:23.470
compression functions to
build hash functions, expansion
00:00:23.470 --> 00:00:27.230
functions to build pseudorandom
number generators but many more.
00:00:27.490 --> 00:00:29.800
Unfortunately, one-way
functions are hard to build.
00:00:30.100 --> 00:00:33.200
We know some very fast
functions which have very few
00:00:33.230 --> 00:00:35.450
security arguments and we
have some very strong security
00:00:35.450 --> 00:00:37.530
arguments for
functions which are very slow.
00:00:38.710 --> 00:00:42.520
What we will try to do is to
get a fast and secure function.
00:00:42.570 --> 00:00:45.250
Niederreiter Encryption is a
good candidate for one-way function.
00:00:45.250 --> 00:00:47.930
Any public key encryption
scheme is a one-way function
00:00:48.410 --> 00:00:50.320
with a trapdoor, which
is the decryption key.
00:00:51.530 --> 00:00:54.740
It has very strong security
arguments usually a proof of security.
00:00:55.740 --> 00:00:58.320
But public key
encryption is usually very slow,
00:00:58.720 --> 00:01:02.050
especially if you take
construction from numbers theory,
00:01:02.050 --> 00:01:05.560
you require an expentiation
which is expensive to compute.
00:01:05.950 --> 00:01:08.890
Niederreiter Encryption is much
faster than other public key schemes.
00:01:08.920 --> 00:01:11.400
It simply converts the
input into a low weight word.
00:01:11.400 --> 00:01:14.030
There are many different
techniques to do this and then
00:01:14.030 --> 00:01:16.730
compute its syndrome which
is only a few XORs, especially
00:01:16.730 --> 00:01:18.120
if the weight is very small.
00:01:18.540 --> 00:01:21.360
The trapdoor can be easily
removed by simply using a
00:01:21.360 --> 00:01:23.980
random binary matrix which
is enough when we don't need
00:01:23.980 --> 00:01:25.290
to invert this one-way function.
00:01:25.290 --> 00:01:29.430
And with a few tweaks, it
can be made even faster than
00:01:29.430 --> 00:01:30.360
the usual Niederreiter Encryption.
00:01:30.570 --> 00:01:33.930
Here, we will give an overview of
the one-way function we are building.
00:01:34.370 --> 00:01:38.510
The parameters are matrix H
of size r*n and the constant
00:01:38.510 --> 00:01:42.050
weight encoding function φ
which takes l bits and output
00:01:42.050 --> 00:01:45.270
a word of weight w and length n.
00:01:45.270 --> 00:01:48.200
The one-way function simply
takes an input x and computes
00:01:48.220 --> 00:01:52.940
φ(x) and multiplies it by
H to obtain a value, a
00:01:52.940 --> 00:01:57.450
syndrome y. Security of
this function: inverting the
00:01:57.450 --> 00:01:59.420
function requires to
solve an instance of syndrome
00:01:59.420 --> 00:02:03.280
decoding; and efficiency:
if φ is fast and w is small,
00:02:03.280 --> 00:02:05.050
then the function
can be very efficient.
00:02:05.890 --> 00:02:08.930
Now, we will see how to build a
fast constant weight encoding function.
00:02:09.040 --> 00:02:12.110
The usual method for
constant weight encoding is to use
00:02:12.110 --> 00:02:14.550
what we call an exact
encoding which takes an input which
00:02:14.550 --> 00:02:19.390
is an integer in [1, (n,w)]
and converts it to a word of
00:02:19.480 --> 00:02:20.940
weight w and length n.
00:02:21.260 --> 00:02:24.150
It requires some
computations on large integers which
00:02:24.150 --> 00:02:27.020
make it rather inefficient,
but that's what offers the
00:02:27.020 --> 00:02:28.410
largest possible input set.
00:02:29.160 --> 00:02:31.850
What we will use is what we
call regular word encoding
00:02:32.250 --> 00:02:35.130
and we restrict ourselves
to words with a weight 1 in
00:02:35.130 --> 00:02:39.010
each interval of size n/w
which means that we split the
00:02:39.010 --> 00:02:43.210
input into w intervals of size n/w
and pick a weight 1 in each interval.
00:02:44.150 --> 00:02:47.860
It is extremely fast
if n/w is a power of 2.
00:02:48.190 --> 00:02:50.290
What you have to keep in
mind is that using this
00:02:50.290 --> 00:02:54.490
function, the input space is a
bit smaller than the exact encoding.
00:02:55.010 --> 00:02:58.210
So, what do we get in the
end of a one-way function?
00:02:58.250 --> 00:03:01.200
The input is x of
size w * log(n/w) bits.
00:03:01.760 --> 00:03:06.430
And the algorithm is
simply to split the input into
00:03:06.430 --> 00:03:10.580
w blocks of size log(n/w)
and convert each of these
00:03:11.190 --> 00:03:13.380
blocks into an integer x1 to xw.
00:03:13.380 --> 00:03:18.200
Then, for each xi,
pick the column Hi at the
00:03:18.580 --> 00:03:21.390
position xi of the
i-th interval of H.
00:03:22.280 --> 00:03:26.270
What you return in the end is
simply the XOR of the different Hi.
00:03:26.860 --> 00:03:31.030
The efficiency of this algorithm:
in theory, splitting x has no cost.
00:03:31.320 --> 00:03:34.900
In practice, depending on
the value of the log(n/w), it
00:03:34.900 --> 00:03:39.160
can require a few shifts or
XORs to compute each value of xi.
00:03:39.160 --> 00:03:41.560
Then, XORing simply
consists in r * w binary XORs.
00:03:41.560 --> 00:03:46.490
So, if you pick secure
parameters with r and w small, you
00:03:46.490 --> 00:03:47.590
have a very fast function.
00:03:48.060 --> 00:03:50.280
Attacking the one-wayness
of the function requires to
00:03:50.280 --> 00:03:53.530
solve an instance of
syndrome decoding, but not any
00:03:53.530 --> 00:03:56.210
instance: a regular
instance which might be a little
00:03:56.210 --> 00:03:58.500
different from a standard
instance of syndrome decoding.
00:03:58.500 --> 00:04:02.650
There are two possible
approaches to measure the security
00:04:02.650 --> 00:04:06.350
of such instances. Either
try to tweak the ISD and GBA
00:04:06.470 --> 00:04:10.380
attacks for regular
instances, but it is hard to know
00:04:10.380 --> 00:04:12.480
if you have the absolute
best attack and measuring the
00:04:12.480 --> 00:04:14.990
security of the scheme is
not always obvious this way.
00:04:15.550 --> 00:04:18.690
Or we can choose to simply loosely
bound the security of the scheme.
00:04:19.310 --> 00:04:21.820
And in fact, what we can
note is that the security of the
00:04:21.820 --> 00:04:25.380
scheme cannot drop more than the
probability of the word to be regular.
00:04:25.730 --> 00:04:28.290
In the end, what we get is
that the security of regular
00:04:28.290 --> 00:04:31.590
syndrome decoding is at
least as much as the security of
00:04:31.700 --> 00:04:33.900
a same instance of
syndrome decoding with the same
00:04:33.900 --> 00:04:37.680
parameters n and w
multiplied by the density of regular
00:04:37.680 --> 00:04:39.730
words which is roughly w!/w^w.
00:04:40.160 --> 00:04:42.760
When selecting the
parameters for this one-way function,
00:04:44.850 --> 00:04:48.540
you have to keep in mind this
drawing of the security as a function of w.
00:04:49.250 --> 00:04:51.670
The maximum security
will be reached for the
00:04:51.670 --> 00:04:55.470
Gilbert-Varshamov bound
which is when the function gives
00:04:55.470 --> 00:04:56.920
no expansion or no compression.
00:04:57.030 --> 00:05:00.010
But if you take a smaller w,
you have an expanding function.
00:05:00.010 --> 00:05:02.480
If you take a large w, you
have a compressing function.
00:05:03.270 --> 00:05:05.520
Be careful though, if you
want to compress or expand a
00:05:05.520 --> 00:05:08.090
lot, then you require some
very large parameters, because
00:05:08.090 --> 00:05:10.380
the security will be
far from the maximum.
00:05:10.950 --> 00:05:13.170
In the next session, we will
see how to use this one-way
00:05:13.270 --> 00:05:16.950
function to design a hash
function which we call FSB.