0:00:00.000,0:00:10.064
<i>preroll music</i>

0:00:10.064,0:00:12.189
Herald: Tanja Lange and djb,

0:00:12.189,0:00:15.519
or, Daniel Bernstein,

0:00:15.519,0:00:19.980
came from the elliptic curve

0:00:19.980,0:00:21.710
are gonna talk today also about

0:00:21.710,0:00:24.380
the McEliece crypto where they took us.

0:00:24.380,0:00:25.759
They're both in the steering committee

0:00:25.759,0:00:28.219
for the PQCrypt

0:00:28.219,0:00:30.259
and I've talked to other people[br]in the community

0:00:30.259,0:00:31.239
and they said,

0:00:31.239,0:00:32.390
especially about Tanja,

0:00:32.390,0:00:37.739
she is the one that brings practice[br]and reality into all this theoretical mess

0:00:37.739,0:00:44.420
so let's please have a hand for[br]Tanja Lange and Daniel Bernstein.

0:00:44.420,0:00:55.260
<i>applause</i>

0:00:55.260,0:00:58.769
djb: Okay. Am I on? I apparently am.

0:00:58.769,0:01:01.980
Welcome to a late night show,[br]with Dan and Tanja.

0:01:01.980,0:01:05.570
<i>laughter</i>[br]There's a lot of crypto talks out there

0:01:05.570,0:01:09.560
where you'll get the idea that[br]crypto has problems.

0:01:09.560,0:01:12.340
Crypto has massive usability problems,

0:01:12.340,0:01:13.890
has performance problems,

0:01:13.890,0:01:15.460
has pitfalls for implementors,

0:01:15.460,0:01:17.750
has crazy complexity in implementation,

0:01:17.750,0:01:19.729
stupid standards,

0:01:19.729,0:01:21.920
millions of lines of unauditable code,

0:01:21.920,0:01:23.320
and then all of these problems

0:01:23.320,0:01:27.189
are combined into a[br]grand unified clusterfuck

0:01:27.189,0:01:30.030
called transport layer security.

0:01:30.030,0:01:38.030
<i>laughter, applause</i>

0:01:38.030,0:01:41.449
But, actually, the situation is worse.

0:01:41.449,0:01:43.510
<i>laughter</i>

0:01:43.510,0:01:45.790
Because of what's coming, namely,

0:01:45.790,0:01:49.260
quantum computers.

0:01:49.260,0:01:51.610
These typical talks will give you the idea

0:01:51.610,0:01:54.829
that the core of crypto,[br]the basic cryptographic primitives

0:01:54.829,0:01:57.280
like elliptic curve crypto, ECC,

0:01:57.280,0:01:59.240
that those are just fine,[br]and all the problems

0:01:59.240,0:02:01.229
are integration into applications,

0:02:01.229,0:02:03.100
that's where the security problems happen.

0:02:03.100,0:02:06.609
But quantum computers will break ECC.

0:02:06.609,0:02:09.258
This has been know since the 1990s.

0:02:09.258,0:02:11.500
For people who don't recognise[br]the picture here,

0:02:11.500,0:02:17.040
this is a mathematician named Peter Shor,[br]20 years ago.

0:02:17.040,0:02:25.769
<i>laughter, applause</i>

0:02:25.769,0:02:27.640
20 years ago he wrote a paper saying

0:02:27.640,0:02:29.340
that a big quantum computer would be

0:02:29.340,0:02:33.300
able to factor big integers[br]in polynomial time.

0:02:33.300,0:02:34.770
Now, if you like doing attacks,

0:02:34.770,0:02:36.259
and you hear about something like this,

0:02:36.259,0:02:37.190
then your first thought is

0:02:37.190,0:02:39.080
"Ooh, I wanna quantum computer!"

0:02:39.080,0:02:41.430
"I want a big quantum computer[br]so I can run this attack!"

0:02:41.430,0:02:43.350
"And, where is it? Does anybody have one?"

0:02:43.350,0:02:44.620
"Can anybody gimme one?"

0:02:44.620,0:02:46.610
"Oh, it isn't there yet?[br]Well, what's the progress?"

0:02:46.610,0:02:48.670
"Are we there yet?[br]Can I have one, please?"

0:02:48.670,0:02:50.470
And, well, in the news, you now hear

0:02:50.470,0:02:53.669
about this D-wave quantum computer,

0:02:53.669,0:02:56.879
which, okay, there's some very good[br]quantum engineering

0:02:56.879,0:02:58.180
that goes into this machine.

0:02:58.180,0:02:59.420
It's pretty clear that it's quantum,

0:02:59.420,0:03:01.800
I mean, it's actually doing the quantum[br]stuff they say it does.

0:03:01.800,0:03:04.920
And there's some fantastic[br]marketing in this machine.

0:03:04.920,0:03:06.230
But, unfortunately,

0:03:06.230,0:03:07.650
it's not actually useful.

0:03:07.650,0:03:09.780
So the D-wave quantum computer

0:03:09.780,0:03:11.690
doesn't do the basic things

0:03:11.690,0:03:14.830
that we expect a universal[br]quantum computer to do.

0:03:14.830,0:03:18.159
It can only do very limited[br]kinds of quantum computation.

0:03:18.159,0:03:20.480
It cannot maintain qubits,

0:03:20.480,0:03:22.520
do error correction on qubits for a while,

0:03:22.520,0:03:23.750
hold on to them to be able to do

0:03:23.750,0:03:25.659
basic qubit computations.

0:03:25.659,0:03:27.739
It can't even do those computations,

0:03:27.739,0:03:29.769
even if it could hold on to the qubits.

0:03:29.769,0:03:31.299
It can't do Shor's algorithm.

0:03:31.299,0:03:32.939
Can't factor big numbers.

0:03:32.939,0:03:35.390
Can't do other quantum algorithms[br]that we care about.

0:03:35.390,0:03:38.080
Now, the D-wave company says that's[br]not the point,

0:03:38.080,0:03:39.519
there's some other computations

0:03:39.519,0:03:41.799
that we designed this machine to do.

0:03:41.799,0:03:43.549
But they cherry-picked the computations

0:03:43.549,0:03:45.280
for this machine, saying basically

0:03:45.280,0:03:48.769
Here is the problem of[br]simulating this machine

0:03:48.769,0:03:51.129
simulating the quantum[br]thing that it's doing,

0:03:51.129,0:03:53.400
and of course the machine is very good[br]at simulating itself,

0:03:53.400,0:03:54.610
by just running,

0:03:54.610,0:03:57.909
whereas a normal laptop, they compared to

0:03:57.909,0:04:00.189
sort of standard programs[br]on a normal laptop,

0:04:00.189,0:04:02.439
and latest results, 10^8 times faster

0:04:02.439,0:04:06.129
except, well, there's a much[br]more optimised program

0:04:06.129,0:04:07.780
that somebody put out last year,

0:04:07.780,0:04:10.159
which basically is the same speed[br]as the D-wave machine

0:04:10.159,0:04:12.049
and like ten thousand times cheaper.

0:04:12.049,0:04:15.630
So, the D-wave machine is not,[br]for the moment, something useful.

0:04:15.630,0:04:18.360
Lange: Well, if this makes you[br]kind of comfortable,

0:04:18.360,0:04:22.440
so, no Shor monster coming,

0:04:22.440,0:04:23.720
there is progress.

0:04:23.720,0:04:25.760
There will be a universal[br]quantum computer,

0:04:25.760,0:04:28.000
so, something that can run[br]Shor's algorithm,

0:04:28.000,0:04:30.020
and there's a lot of research effort[br]going into this,

0:04:30.020,0:04:32.120
so if you track, like, spending on crypto

0:04:32.120,0:04:33.320
and you can spend...

0:04:33.320,0:04:36.450
and track spending on quantum computers,

0:04:36.450,0:04:37.670
that is a lot of money.

0:04:37.670,0:04:39.850
And there's a lot of institutions[br]and companies

0:04:39.850,0:04:41.700
and of course governments[br]all over the world

0:04:41.700,0:04:43.090
building stuff.

0:04:43.090,0:04:44.250
And we do see progress, so

0:04:44.250,0:04:45.730
we're keeping track on this,

0:04:45.730,0:04:48.300
and, go to the Wikipedia page here

0:04:48.300,0:04:50.270
so we see over the last few years

0:04:50.270,0:04:53.980
a huge progress in stability of qubits,

0:04:53.980,0:04:56.430
so these things usually[br]forget what they had,

0:04:56.430,0:04:57.930
they decay,

0:04:57.930,0:04:59.890
but they get more stable,

0:04:59.890,0:05:01.730
there's better error correction,

0:05:01.730,0:05:03.040
and there's better communication.

0:05:03.040,0:05:06.900
So the latest was that[br]even silicon-based qubits can communicate.

0:05:06.900,0:05:08.530
So something is happening.

0:05:08.530,0:05:12.970
Um, IBM has[br]on the record of Mark Ketchen

0:05:12.970,0:05:15.390
who's their CEO saying

0:05:15.390,0:05:19.640
"We actually do things that make us think[br]like, hey, this isn't 50 years off"

0:05:19.640,0:05:23.260
"This is maybe just 10 or 15 years off.[br]It's within reach."

0:05:23.260,0:05:24.590
So IBM is leaning out the window

0:05:24.590,0:05:27.510
and saying, yup, we're gonna be there[br]pretty damn soon.

0:05:27.510,0:05:31.560
They said that in 2012, so[br]let's fast-forward by 10 to 15 years

0:05:31.560,0:05:34.930
so it's now 2022 or 2027

0:05:34.930,0:05:37.990
and so there is a universal[br]quantum computer.

0:05:37.990,0:05:42.220
The effect this has on the Internet crypto

0:05:42.220,0:05:45.320
is that RSA, which is still the majority

0:05:45.320,0:05:46.650
of all the connections today,

0:05:46.650,0:05:49.760
RSA is broken. RSA is dead.

0:05:49.760,0:05:51.820
Discrete logs in finite fields.

0:05:51.820,0:05:53.250
You might have thought a lot about it

0:05:53.250,0:05:55.000
earlier this year about Logjam.

0:05:55.000,0:05:57.740
But Logjam just breaks the very small one.

0:05:57.740,0:06:00.210
This is breaking any big one.

0:06:00.210,0:06:03.250
So, discrete logs in finite fields[br]is totally dead as well.

0:06:03.250,0:06:05.810
Elliptic curves, that I already mentioned,[br]ECC is dead.

0:06:05.810,0:06:11.030
So this breaks all public-key crypto[br]on the Internet.

0:06:11.030,0:06:13.460
There's another algorithm due to Grover,

0:06:13.460,0:06:16.190
which is somewhat better under control,

0:06:16.190,0:06:18.360
somewhat less scary for crypto,

0:06:18.360,0:06:19.820
but it still has quite an effect,

0:06:19.820,0:06:22.250
so if you believe in the security of AES

0:06:22.250,0:06:26.010
and go like, well, AES-128 seems just fine,

0:06:26.010,0:06:27.200
has been not getting any

0:06:27.200,0:06:30.300
big progress in cryptanalysis,

0:06:30.300,0:06:33.850
but it halves the security,[br]so AES 128-bit keys

0:06:33.850,0:06:36.800
are only 64-bit secure.

0:06:36.800,0:06:40.460
However, you can go to 256 bits.

0:06:40.460,0:06:43.470
djb: Okay, so, the AES situation:[br]not so bad,

0:06:43.470,0:06:45.530
but all this public key stuff is broken.

0:06:45.530,0:06:46.470
So what do we do?

0:06:46.470,0:06:48.370
Well, you could bury[br]your head in the sand,

0:06:48.370,0:06:50.870
you could hope that quantum computers[br]don't come along,

0:06:50.870,0:06:55.800
you could deploy[br]a physically secure crypto.

0:06:55.800,0:06:59.100
You could take a locked briefcase[br]and chain it to your wrist,

0:06:59.100,0:07:01.090
or you could do quantum key distribution.

0:07:01.090,0:07:04.000
Now these things, obviously,[br]are very very expensive.

0:07:04.000,0:07:07.610
This is crypto, information protection[br]for rich people.

0:07:07.610,0:07:11.980
Or, quantum key distribution is crypto[br]for even richer people.

0:07:11.980,0:07:15.370
You, obviously, aren't going to be able[br]to democratically give this

0:07:15.370,0:07:16.840
to everybody who has a laptop.

0:07:16.840,0:07:19.210
But, well, okay, imagine that[br]you have enough money,

0:07:19.210,0:07:20.490
that you don't mind this.

0:07:20.490,0:07:23.830
There's a bigger problem[br]with physical cryptography,

0:07:23.830,0:07:25.290
which is the security.

0:07:25.290,0:07:26.950
Now these things are always advertised

0:07:26.950,0:07:30.100
as provably secure, guaranteed secure.

0:07:30.100,0:07:31.760
Nobody can get into this briefcase!

0:07:31.760,0:07:34.300
Nobody can get into this[br]quantum key distribution system!

0:07:34.300,0:07:36.340
Assuming, of course, blah blah blah.

0:07:36.340,0:07:37.550
And then you look at the assumptions

0:07:37.550,0:07:38.410
and you start saying

0:07:38.410,0:07:40.570
"Wait a minute, is that actually true?"

0:07:40.570,0:07:43.440
And then it turns out that when people try[br]attacking these systems,

0:07:43.440,0:07:44.770
the assumptions are not true.

0:07:44.770,0:07:47.520
And the systems get broken[br]again and again and again

0:07:47.520,0:07:50.380
for a very reasonable attack cost.

0:07:50.380,0:07:54.270
Okay. Even if you have a system[br]where you think it's secure,

0:07:54.270,0:07:55.770
which nobody's managed to build yet,

0:07:55.770,0:07:59.080
even if you had that, the design of[br]this physical security system

0:07:59.080,0:08:01.590
is incredibly difficult to audit.

0:08:01.590,0:08:03.700
It's something where, if somebody wants[br]to slip in a backdoor,

0:08:03.700,0:08:05.020
it's really easy.

0:08:05.020,0:08:06.260
But there's an even worse problem

0:08:06.260,0:08:07.860
with physical cryptography,

0:08:07.860,0:08:10.480
which is that it doesn't[br]do very much crypto.

0:08:10.480,0:08:14.860
Typically these systems do about[br]the same thing that AES does.

0:08:14.860,0:08:17.000
You start with a shared secret,

0:08:17.000,0:08:18.310
and then from that shared secret

0:08:18.310,0:08:20.560
you can authenticate more secrets

0:08:20.560,0:08:24.590
that you transmit through this[br]physically secure communication mechanism.

0:08:24.590,0:08:26.050
For instance, quantum key distribution

0:08:26.050,0:08:28.520
starts with some way,[br]some pre-existing way

0:08:28.520,0:08:30.190
of authenticating.

0:08:30.190,0:08:33.070
But that's just like AES starts with[br]a, a secret key

0:08:33.070,0:08:34.450
which is then used to generate

0:08:34.450,0:08:36.529
more and more secret data.

0:08:36.529,0:08:38.330
And quantum key distribution says

0:08:38.330,0:08:40.610
well, it's provably secure under[br]certain assumptions,

0:08:40.610,0:08:42.770
instead of AES which, well,

0:08:42.770,0:08:44.860
we just heard AES may be a little affected

0:08:44.860,0:08:46.260
by quantum computers, but

0:08:46.260,0:08:48.160
AES-256 is not broken.

0:08:48.160,0:08:50.030
Nobody has any idea how to break it.

0:08:50.030,0:08:52.200
So this physical cryptography

0:08:52.200,0:08:54.570
isn't actually serving[br]the needs that we want.

0:08:54.570,0:08:58.470
Imagine trying to distribute[br]operating system updates

0:08:58.470,0:09:00.550
through locked briefcases.

0:09:00.550,0:09:01.810
It's just not going to happen.

0:09:01.810,0:09:04.330
Microsoft sending out billions[br]of locked briefcases

0:09:04.330,0:09:05.800
to all of its customers.

0:09:05.800,0:09:07.020
If you think that's realistic,

0:09:07.020,0:09:11.150
or if you think that,[br]just, lasers are cool,

0:09:11.150,0:09:13.450
then there's a talk about quantum crypto

0:09:13.450,0:09:15.340
tomorrow, I believe.

0:09:15.340,0:09:20.010
Back in the real world, we obviously[br]need to do something better with crypto.

0:09:20.010,0:09:22.770
Lange: Alright, so,[br]let me take, momentarily,

0:09:22.770,0:09:24.770
a slightly more optimistic perspective.

0:09:24.770,0:09:26.370
Is there any hope? Yes.

0:09:26.370,0:09:29.180
So, the title of this talk, PQCHacks,

0:09:29.180,0:09:31.310
comes from post-quantum crypto,

0:09:31.310,0:09:32.860
and that's the term Dan coined

0:09:32.860,0:09:34.510
back in 2003

0:09:34.510,0:09:36.290
for crypto that remains secure

0:09:36.290,0:09:38.840
even if the adversary has[br]a quantum computer.

0:09:38.840,0:09:42.500
So you, the normal people,[br]me, him, the normal people,

0:09:42.500,0:09:44.290
the Internet, all the connections,

0:09:44.290,0:09:46.740
we have normal computers.

0:09:46.740,0:09:49.080
The adversary has a quantum computer.

0:09:49.080,0:09:50.700
We, today, encrypt something.

0:09:50.700,0:09:51.970
Adversary has all the time in the world

0:09:51.970,0:09:53.450
to build the quantum computer,

0:09:53.450,0:09:56.390
break us now or break us in the future.

0:09:56.390,0:09:57.370
And so this took off,

0:09:57.370,0:09:58.550
and there's been the first workshop

0:09:58.550,0:10:02.370
on post-quantum crypto,[br]called PQCrypto2006

0:10:02.370,0:10:03.770
and then there's been[br]a series of workshops

0:10:03.770,0:10:04.850
you can see here.

0:10:04.850,0:10:07.270
These are the attendees[br]of the last edition

0:10:07.270,0:10:09.580
which was in Waterloo.[br]It's more than a hundred people,

0:10:09.580,0:10:11.390
going like, yes,[br]this is an important topic,

0:10:11.390,0:10:13.490
let's do some research on it.

0:10:13.490,0:10:15.740
So something is happening.

0:10:15.740,0:10:17.500
If you're curious what's happening,

0:10:17.500,0:10:20.620
next there's a workshop in Japan[br]in February

0:10:20.620,0:10:23.420
and then in the Netherlands[br]in 2017,

0:10:23.420,0:10:26.630
and we also got a project through[br]from the EU

0:10:26.630,0:10:28.810
to support research on post-quantum.

0:10:28.810,0:10:30.320
So something is happening.

0:10:30.320,0:10:34.260
Actually, um, did I forget somebody?[br]Yes.

0:10:34.260,0:10:38.280
Um, the NSA is also saying,[br]let's do something.

0:10:38.280,0:10:44.400
So, on August 11 the NSA posted[br]on their Suite B... page

0:10:44.400,0:10:47.540
saying, "The Information Assurance[br]Director (so, IAD)

0:10:47.540,0:10:51.640
recognizes that there will be a move, in[br]the not distant future, to a

0:10:51.640,0:10:53.480
quantum resistant algorithm suite."

0:10:53.480,0:10:56.180
Oh my god! Somebody is doing something!

0:10:56.180,0:10:58.210
The public has realised[br]we have to do something!

0:10:58.210,0:11:00.510
Quick, quick,[br]let's put out a press release!

0:11:00.510,0:11:02.590
Um.

0:11:02.590,0:11:05.560
Looks like they kind of realised[br]it was embarrassing.

0:11:05.560,0:11:09.690
So, eight days later they pushed[br]a new release, saying

0:11:09.690,0:11:15.210
"IAD will initiate a transition to quantum[br]resistant algorithms in the not distant future."

0:11:15.210,0:11:19.910
So, NSA will lead us to a bright and[br]glorious future.

0:11:19.910,0:11:22.760
djb: America, fuck yeah.

0:11:22.760,0:11:30.790
<i>laughter, applause</i>

0:11:30.790,0:11:34.510
Lange: But if you thought that,[br]so far, this was bad,

0:11:34.510,0:11:38.340
it actually takes a lot of time[br]to build crypto.

0:11:38.340,0:11:41.810
With let's say, NSA[br]all ask the researchers

0:11:41.810,0:11:44.000
If you have some idea of[br]what could be secure

0:11:44.000,0:11:45.510
against a quantum computer,

0:11:45.510,0:11:47.120
say AES-256,

0:11:47.120,0:11:48.590
the reason that you have confidence in it

0:11:48.590,0:11:51.250
is we had more than ten years of people

0:11:51.250,0:11:53.000
trying to break it,

0:11:53.000,0:11:54.570
trying all kinds of approaches

0:11:54.570,0:11:55.870
and not getting anywhere.

0:11:55.870,0:12:00.350
It takes a lot of time to explore[br]the space of cryptosystems.

0:12:00.350,0:12:01.540
Once you have figured out

0:12:01.540,0:12:02.880
what could be actually doable,

0:12:02.880,0:12:05.230
you want to figure[br]what the best attacks are,

0:12:05.230,0:12:06.940
you want to focus on the security system,

0:12:06.940,0:12:09.430
you want to figure out[br]how to implement them,

0:12:09.430,0:12:10.380
how to implement them securely,

0:12:10.380,0:12:13.570
that is a whole lot of work[br]that needs to be done

0:12:13.570,0:12:15.860
before you can say, well,[br]this is actually practical.

0:12:15.860,0:12:18.060
We can actually use this.

0:12:18.060,0:12:22.680
Or sometimes, this is as practical[br]as we can get it.

0:12:22.680,0:12:27.210
And then, you have this tiny little[br]crypto primitive,

0:12:27.210,0:12:28.410
and then you have to build the hooks

0:12:28.410,0:12:31.200
and connections to get it into TLS.

0:12:31.200,0:12:32.670
Then we said at the beginning

0:12:32.670,0:12:33.910
that maybe you believe

0:12:33.910,0:12:36.670
that the cute little crypto cores[br]are all secure

0:12:36.670,0:12:37.600
and it's just the connections

0:12:37.600,0:12:39.500
with the AES, sorry, with the TLS

0:12:39.500,0:12:42.029
in other world that is the problem.

0:12:42.029,0:12:44.620
That still needs to be done[br]for post-quantum as well.

0:12:44.620,0:12:46.500
And, the side-channel attacks,

0:12:46.500,0:12:48.260
there's, uh, as an example,

0:12:48.260,0:12:52.370
ECC was introduced back in 85,

0:12:52.370,0:12:54.100
and now 30 years later,

0:12:54.100,0:12:57.460
we're seeing that ECC is actually[br]getting deployed on the Internet,

0:12:57.460,0:13:02.340
that now the IETF, having called[br]for having elliptic curve crypto,

0:13:02.340,0:13:05.560
because people start saying, yes,[br]we would like to use this.

0:13:05.560,0:13:08.440
So we cannot wait until[br]there's a quantum computer

0:13:08.440,0:13:10.670
in order to start research on it.

0:13:10.670,0:13:14.770
If you remember what 85 looked like

0:13:14.770,0:13:18.770
That's a while ago.

0:13:18.770,0:13:21.970
Now, if that sounded bad,

0:13:21.970,0:13:23.170
it's actually worse.

0:13:23.170,0:13:26.400
It's not just that, in 15 years from now,

0:13:26.400,0:13:29.259
whatever you send then will be broken.

0:13:29.259,0:13:33.420
There's some indication that some entities

0:13:33.420,0:13:40.690
might be recording your traffic.

0:13:40.690,0:13:42.700
We've given a talk like this in 2012

0:13:42.700,0:13:44.220
which was "Crypto for the Paranoid",

0:13:44.220,0:13:45.400
everybody thought it was, like,

0:13:45.400,0:13:46.960
pfft, you're crazy,

0:13:46.960,0:13:48.720
now it goes like[br]"well, there might be an entity"

0:13:48.720,0:13:52.960
and everybody goes like, yeah, hmm, yeah.

0:13:52.960,0:13:54.560
So, let's assume that this entity

0:13:54.560,0:13:57.020
has the records of all the connections,

0:13:57.020,0:14:01.220
and, that in ten years, you're going[br]to be an interesting person.

0:14:01.220,0:14:04.540
Maybe you're a politician,[br]maybe you've become rich,

0:14:04.540,0:14:07.880
maybe you associate with the wrong people,[br]or so they think,

0:14:07.880,0:14:12.630
and so somehow they go back to[br]the 27th of December 2015,

0:14:12.630,0:14:16.000
and figure out what you[br]were emailing during the talks,

0:14:16.000,0:14:18.279
because they have all the connections here

0:14:18.279,0:14:20.410
so they can go back in time

0:14:20.410,0:14:26.050
just by the metadata,[br]and of course the real data.

0:14:26.050,0:14:28.630
From the metadata, they can decrypt it,

0:14:28.630,0:14:31.670
because this metadata is using RSA or ECC

0:14:31.670,0:14:33.090
which are broken.

0:14:33.090,0:14:34.550
And then they get the same key

0:14:34.550,0:14:38.180
than you're currently using with your[br]other side to communicate.

0:14:38.180,0:14:42.920
And so they can go and decrypt this.

0:14:42.920,0:14:45.529
So it's not only that we can't wait for[br]quantum computers to come,

0:14:45.529,0:14:51.320
we might already be too late.

0:14:51.320,0:14:53.359
Well, on the next slide,

0:14:53.359,0:14:56.190
here's a bunch of people who are getting[br]together in this EU project,

0:14:56.190,0:14:59.720
and we have come up with[br]what we're currently thinking

0:14:59.720,0:15:02.290
are good recommendations.

0:15:02.290,0:15:04.080
We think it's necessary for people

0:15:04.080,0:15:07.190
who really care about the security[br]of their connections,

0:15:07.190,0:15:08.480
and when I say people I include myself,

0:15:08.480,0:15:10.740
I care about the security of[br]my connections,

0:15:10.740,0:15:12.330
we would like to have something

0:15:12.330,0:15:15.050
that we believe is secure[br]for the next hundred years.

0:15:15.050,0:15:17.310
And so we put out[br]a list of recommendations.

0:15:17.310,0:15:19.910
So, for symmetric, it's relatively easy.

0:15:19.910,0:15:22.500
You want something which is at least[br]a 256-bit key

0:15:22.500,0:15:25.110
and is sufficiently well understood

0:15:25.110,0:15:29.129
so there we have Salsa20,[br]and we have AES-256.

0:15:29.129,0:15:32.990
Then, for authentication in symmetric,

0:15:32.990,0:15:35.430
there, we don't actually have any decrease

0:15:35.430,0:15:36.750
from a quantum computer, because

0:15:36.750,0:15:38.899
these are already[br]information-theoretically secure.

0:15:38.899,0:15:40.899
So these are the nice part.

0:15:40.899,0:15:44.220
These two talk items is where we go like

0:15:44.220,0:15:47.690
"Pff. We might be okay on those."

0:15:47.690,0:15:49.880
We can do better,[br]we can have nice research

0:15:49.880,0:15:51.740
and get something which is even[br]better protected,

0:15:51.740,0:15:54.010
even faster under the new scenario,

0:15:54.010,0:15:55.740
but it's not so dire.

0:15:55.740,0:15:59.240
The bottom two, these are[br]the public key systems.

0:15:59.240,0:16:03.399
That's public key encryption[br]and public key signatures.

0:16:03.399,0:16:05.220
That's what we're going to[br]focus on in this talk.

0:16:05.220,0:16:07.750
So, for public key encryption,[br]we're recommending

0:16:07.750,0:16:10.620
the McEliece cryptosystem[br]with Goppa codes

0:16:10.620,0:16:13.250
for a certain parameter size,

0:16:13.250,0:16:15.240
and then for signatures,

0:16:15.240,0:16:17.959
the recommendation is to use hash-based.

0:16:17.959,0:16:19.170
djb: Okay, so...

0:16:19.170,0:16:23.240
Let me dive into[br]the hash-based part of this.

0:16:23.240,0:16:26.220
This is something which goes back[br]even further than the 80s.

0:16:26.220,0:16:28.720
It goes back to the 1970s. Lamport.

0:16:28.720,0:16:32.810
So here's a way to use hashes[br]to do one-time signatures.

0:16:32.810,0:16:34.300
Which are, we'll see in a few minutes,

0:16:34.300,0:16:35.700
signatures that you can use

0:16:35.700,0:16:38.460
to sign one message under a given key.

0:16:38.460,0:16:40.660
And then, well, that's a little bit[br]inconvenient

0:16:40.660,0:16:41.910
that you can't sign more messages

0:16:41.910,0:16:43.470
so then Merkle came along

0:16:43.470,0:16:45.100
and said, you can sign more messages

0:16:45.100,0:16:46.339
by modifying the system,

0:16:46.339,0:16:47.730
and we'll also take a look at that.

0:16:47.730,0:16:50.890
The only thing you need[br]for these public-key signature systems

0:16:50.890,0:16:52.130
is a good hash function.

0:16:52.130,0:16:54.690
And, okay, that's something where[br]historically,

0:16:54.690,0:16:57.740
some hash functions designed in like, 1991

0:16:57.740,0:16:58.580
had trouble.

0:16:58.580,0:17:00.920
But, now, we have some good hash functions

0:17:00.920,0:17:03.660
so, for instance, SHA-3 has[br]some great hash functions,

0:17:03.660,0:17:05.790
even SHA-2, there's no sign of trouble,

0:17:05.790,0:17:07.400
of those things being broken.

0:17:07.400,0:17:10.119
And then after these original systems[br]from Lamport and Merkle,

0:17:10.119,0:17:11.859
there's lots and lots of improvements,

0:17:11.859,0:17:14.020
but all of these hash-based systems,

0:17:14.020,0:17:16.670
it's really easy to[br]understand the security.

0:17:16.670,0:17:18.329
It's something where the basic idea

0:17:18.329,0:17:19.589
is really, really simple,

0:17:19.589,0:17:21.280
and the security analysis also ends up

0:17:21.280,0:17:22.869
being very straightforward.

0:17:22.869,0:17:24.679
You have to be careful about some things,

0:17:24.679,0:17:26.589
but, when you're careful about those,

0:17:26.589,0:17:28.790
and there's nothing subtle[br]about it, nothing tricky,

0:17:28.790,0:17:32.110
then we understand exactly[br]what security we get from these.

0:17:32.110,0:17:35.130
So let's dive into a signature scheme

0:17:35.130,0:17:37.820
that can only sign empty messages.

0:17:37.820,0:17:40.690
Now, this sounds kind of, like,[br]wait a minute,

0:17:40.690,0:17:42.760
what do you mean,[br]"can only sign empty messages?"

0:17:42.760,0:17:44.600
There's only one empty string,

0:17:44.600,0:17:46.290
and that's the only thing you can sign.

0:17:46.290,0:17:49.550
But imagine that you want[br]to have a panic button,

0:17:49.550,0:17:51.000
like, your revocation key,

0:17:51.000,0:17:52.000
you want to be able to say,

0:17:52.000,0:17:56.290
"Here's a message that says,[br]my house, my computer's been compromised,

0:17:56.290,0:17:58.290
don't trust anything from this anymore".

0:17:58.290,0:18:00.750
It's this one message[br]that you want to sign,

0:18:00.750,0:18:01.500
under a certain key,

0:18:01.500,0:18:03.750
and if anybody has that public key,

0:18:03.750,0:18:06.800
then they should be able to verify[br]that you sent that message,

0:18:06.800,0:18:08.350
and nobody should be able to forge that,

0:18:08.350,0:18:10.000
because it's really bad[br]if somebody can forge

0:18:10.000,0:18:10.880
your panic message.

0:18:10.880,0:18:12.960
So, being able to sign just one message

0:18:12.960,0:18:15.550
is not actually such a useless thing,

0:18:15.550,0:18:16.790
and we'll also see that it builds up

0:18:16.790,0:18:19.550
to the rest of hash-based crypto.

0:18:19.550,0:18:23.040
Okay. Let's look at[br]some Python stuff here,

0:18:23.040,0:18:25.650
simple SHA-3 you can get online

0:18:25.650,0:18:29.580
under Ubuntu or Debian[br]do install python-pip and python-dev

0:18:29.580,0:18:31.360
because it's a C library actually,

0:18:31.360,0:18:33.840
and then, pip install simplesha3,

0:18:33.840,0:18:36.210
that will give you SHA3-256,

0:18:36.210,0:18:38.000
and then to generate a keypair

0:18:38.000,0:18:41.140
in this empty-message signature system,

0:18:41.140,0:18:43.850
all you do is you make 32 bytes[br]of random data

0:18:43.850,0:18:45.070
and just hash it again,

0:18:45.070,0:18:49.740
just in in case... urandom is not[br]too well-reviewed...

0:18:49.740,0:18:51.770
I mean, we should trust urandom,

0:18:51.770,0:18:54.090
but it's really cheap[br]to put an extra hash on it.

0:18:54.090,0:18:57.140
So that's your secret key,[br]it's a 32-byte hash.

0:18:57.140,0:18:58.530
And then the public key is,

0:18:58.530,0:18:59.890
hash that secret again.

0:18:59.890,0:19:03.040
So the public key is simply[br]a hash of the secret key.

0:19:03.040,0:19:05.120
And then return the public key[br]and the secret key,

0:19:05.120,0:19:06.640
of course the public key[br]will get published,

0:19:06.640,0:19:08.860
and the secret key you keep for yourself.

0:19:08.860,0:19:11.370
As an example of doing this, well, um,

0:19:11.370,0:19:12.600
you just get random-looking data

0:19:12.600,0:19:15.000
coming out from your public key[br]at the bottom

0:19:15.000,0:19:17.910
your secret key right at the bottom[br]and public key above that.

0:19:17.910,0:19:19.870
And you can check that one[br]of them's a hash of the other

0:19:19.870,0:19:21.290
if you know the secret key,

0:19:21.290,0:19:22.730
you can hash it to get the public.

0:19:22.730,0:19:25.000
Okay, now, how do you sign a message?

0:19:25.000,0:19:27.380
Well, this maybe sort of spelled out

0:19:27.380,0:19:29.230
in more steps than it has to be.

0:19:29.230,0:19:32.260
The API here, this is, I would say,

0:19:32.260,0:19:33.910
getting to be a pretty popular API

0:19:33.910,0:19:36.790
for signatures and for verification,

0:19:36.790,0:19:40.010
where you include the signature[br]and the message together,

0:19:40.010,0:19:41.230
as a signed message.

0:19:41.230,0:19:44.940
And to emphasise that, here's a returned[br]signed message from the sign function.

0:19:44.940,0:19:48.730
Now, the signed message[br]will be later on verified,

0:19:48.730,0:19:50.450
and you get a message out of it,

0:19:50.450,0:19:52.080
where the only possible message

0:19:52.080,0:19:53.670
to be signed is the empty string,

0:19:53.670,0:19:55.610
and you can see that the top there

0:19:55.610,0:19:57.540
of the signature is checking

0:19:57.540,0:19:59.530
if the message is anything[br]other than the empty string

0:19:59.530,0:20:01.750
then you're not allowed to sign it.

0:20:01.750,0:20:04.740
Um, if you have the empty string coming in

0:20:04.740,0:20:09.600
then the signature is simply[br]your secret key.

0:20:09.600,0:20:11.780
So you reveal your secret key

0:20:11.780,0:20:13.610
and the whole idea of hash-based crypto

0:20:13.610,0:20:16.160
is that somebody can publicly check

0:20:16.160,0:20:18.650
the hashes of something that you reveal

0:20:18.650,0:20:22.220
to sign, in this case, the empty message.

0:20:22.220,0:20:23.860
And we'll see later how[br]you can use the same idea

0:20:23.860,0:20:25.390
to sign lots more.

0:20:25.390,0:20:27.030
And then, okay, verification,

0:20:27.030,0:20:29.270
you simply checked that signedmessage,

0:20:29.270,0:20:31.340
which is supposed to be the secret key,

0:20:31.340,0:20:32.480
check its hash

0:20:32.480,0:20:34.480
and see if that matches the public key.

0:20:34.480,0:20:36.120
What would somebody have to do[br]to attack this?

0:20:36.120,0:20:37.360
He would have to,

0:20:37.360,0:20:39.549
if you haven't actually signed a message,

0:20:39.549,0:20:40.540
the one message,

0:20:40.540,0:20:41.710
then he would have to figure out

0:20:41.710,0:20:45.010
some string that, when you hash it,

0:20:45.010,0:20:46.510
gives this public key.

0:20:46.510,0:20:48.460
And, well, that public key,

0:20:48.460,0:20:50.260
this is a preimage problem,

0:20:50.260,0:20:51.760
inverting the hash function.

0:20:51.760,0:20:53.580
The hash is supposed to be one-way,

0:20:53.580,0:20:55.460
if the input were low-entropy,

0:20:55.460,0:20:56.860
then this would be doable,

0:20:56.860,0:20:59.140
but the input was a 32-byte random string,

0:20:59.140,0:21:00.760
so nobody will be able to guess that,

0:21:00.760,0:21:03.730
or find any other string that passes this.

0:21:03.730,0:21:05.410
And then you return the message

0:21:05.410,0:21:06.660
and you can try this out

0:21:06.660,0:21:08.240
and see that it works.

0:21:08.240,0:21:09.610
Alright, let's move on.

0:21:09.610,0:21:11.470
We've managed to sign empty messages.

0:21:11.470,0:21:13.790
How about signing 0 or 1?

0:21:13.790,0:21:15.929
So now we'll make a signature system

0:21:15.929,0:21:18.270
where your key can sign 0

0:21:18.270,0:21:19.730
and your key can sign 1.

0:21:19.730,0:21:22.400
And, well, this is going[br]to be kind of stupid,

0:21:22.400,0:21:24.850
what you do is, you make two keys,

0:21:24.850,0:21:26.480
one of them is signing 0,

0:21:26.480,0:21:28.370
and the other one is signing 1.

0:21:28.370,0:21:31.600
You can see how complicated[br]this hash-based signature stuff is,

0:21:31.600,0:21:34.460
it's, okay, you put two keys together,

0:21:34.460,0:21:36.450
you make one key that will sign 0,

0:21:36.450,0:21:37.470
one key that will sign 1,

0:21:37.470,0:21:38.610
concatenate the public keys,

0:21:38.610,0:21:40.130
concatenate the secret keys,

0:21:40.130,0:21:42.520
the p0+p1, s0+s1,

0:21:42.520,0:21:43.880
and then if you want to sign, then,

0:21:43.880,0:21:45.860
well, if you're signing 0,

0:21:45.860,0:21:48.020
now the messages being signed[br]are integers now

0:21:48.020,0:21:49.490
instead the empty string,

0:21:49.490,0:21:50.670
if you want to sign 0,

0:21:50.670,0:21:51.940
then the signed message will be

0:21:51.940,0:21:55.830
the string "0", followed by the 32 bytes,

0:21:55.830,0:21:59.059
well, this is again more complicated[br]than it has to be,

0:21:59.059,0:22:01.400
but think of this as[br]signing the empty message

0:22:01.400,0:22:03.460
with the empty signature system,

0:22:03.460,0:22:06.540
which is just copying the 32 bytes[br]of the secret key.

0:22:06.540,0:22:08.410
And then if you want to sign message 1,

0:22:08.410,0:22:12.240
then you do that with the other 32 bytes[br]of the secret key.

0:22:12.240,0:22:13.770
And then, to verify it,

0:22:13.770,0:22:16.100
well, just whether the[br]signed message is 0 or 1,

0:22:16.100,0:22:18.150
just do the obvious thing.

0:22:18.150,0:22:19.950
Maybe I should emphasise this code

0:22:19.950,0:22:22.440
was written just for this talk,

0:22:22.440,0:22:24.179
it has not been reviewed,

0:22:24.179,0:22:25.860
and you should audit everything.

0:22:25.860,0:22:26.809
You know, you might feel like

0:22:26.809,0:22:28.990
six lines of code,[br]you can't possibly screw it up,

0:22:28.990,0:22:32.530
but, don't ever[br]use code like that in crypto.

0:22:32.530,0:22:34.760
So, this is just meant for[br]you to understand

0:22:34.760,0:22:35.700
what this is supposed to be doing,

0:22:35.700,0:22:36.860
this has not passed review.

0:22:36.860,0:22:39.640
But, I like to think it would pass review.

0:22:39.640,0:22:41.650
Um, okay, if you try

0:22:41.650,0:22:44.570
signing the 1 message, for example,

0:22:44.570,0:22:47.549
and take the signed 1 message[br]and open that signed message,

0:22:47.549,0:22:49.360
you do get the integer 1 back.

0:22:49.360,0:22:50.470
And if you try forging it,

0:22:50.470,0:22:51.600
you're again faced with this problem

0:22:51.600,0:22:53.980
of coming up with some 32-byte string

0:22:53.980,0:22:56.580
that hashes to a particular result.

0:22:56.580,0:22:59.790
Alright, let's move on to 4-bit messages!

0:22:59.790,0:23:02.440
So, I promise I won't do[br]every possible length.

0:23:02.440,0:23:04.610
But, 4 bits, this will make[br]an important point

0:23:04.610,0:23:06.600
that you don't see from 1 bit.

0:23:06.600,0:23:08.720
Let's try to sign a 4-bit message

0:23:08.720,0:23:11.150
by signing each of the four bits.

0:23:11.150,0:23:13.960
This all scales up to signing 1000 bits[br]if you want.

0:23:13.960,0:23:17.950
Um, so, okay, let's make[br]4 sign-bit keypairs

0:23:17.950,0:23:21.179
where each of those was[br]two 32-byte hashes,

0:23:21.179,0:23:25.590
I mean, each secret key is[br]two 32-byte random strings

0:23:25.590,0:23:29.380
and each of the public keys is the hash[br]of those 32-byte random strings.

0:23:29.380,0:23:31.970
Make 4 of those pairs[br]and concatenate them

0:23:31.970,0:23:34.950
to make some new public keys[br]and secret keys.

0:23:34.950,0:23:38.489
Alright, and now to sign a message, well,[br]you look at the message

0:23:38.489,0:23:41.179
and check,[br]is it an integer between 0 and 15,

0:23:41.179,0:23:42.580
and reject otherwise,

0:23:42.580,0:23:44.960
and then sign each bit of the message.

0:23:44.960,0:23:47.850
You can see m shifted right by 0, 1, 2, 3,

0:23:47.850,0:23:49.750
extract the bottom bit of each of those,

0:23:49.750,0:23:51.690
and then sign each of those bits,

0:23:51.690,0:23:53.730
and then concatenate the signatures

0:23:53.730,0:23:56.970
to get, well, signatures of the four bits[br]of the message.

0:23:56.970,0:24:00.200
And then verification works the way[br]you expect

0:24:00.200,0:24:02.750
and I'll just skip that.

0:24:02.750,0:24:04.290
Alright, this has a problem.

0:24:04.290,0:24:06.919
That if you use this signature system

0:24:06.919,0:24:09.960
to sign two different messages,

0:24:09.960,0:24:13.360
then you might actually allow forgeries.

0:24:13.360,0:24:14.620
So let's look, for example,

0:24:14.620,0:24:18.100
suppose you sign 11 and you sign 7.

0:24:18.100,0:24:20.200
Now what is that signature of 11,

0:24:20.200,0:24:22.799
11, uh-oh, I have to do 11 in binary now,

0:24:22.799,0:24:27.260
so 11 sounds like 8+2+1.

0:24:27.260,0:24:30.990
And you sign 7, which is 4+2+1.

0:24:30.990,0:24:32.679
So what if you revealed now?

0:24:32.679,0:24:35.510
You reveal the signature on that 8,

0:24:35.510,0:24:38.090
so the 3rd bit you revealed

0:24:38.090,0:24:41.330
a signature saying, "the 3rd bit is 1"

0:24:41.330,0:24:43.390
as part of the signature of 11.

0:24:43.390,0:24:45.350
But as part of the signature of 7,

0:24:45.350,0:24:47.330
you revealed, you signed a message

0:24:47.330,0:24:50.419
saying "the 3rd bit is 0".

0:24:50.419,0:24:52.600
And now you can just mix and match[br]those messages,

0:24:52.600,0:24:53.830
wherever the bits were different.

0:24:53.830,0:24:56.120
So for instance if you take the top bit[br]from the 11

0:24:56.120,0:24:58.970
and the bottom 3 bits from the 7

0:24:58.970,0:25:00.830
then you end up signing 15.

0:25:00.830,0:25:02.990
So this signature system,

0:25:02.990,0:25:05.870
it's totally safe[br]if you're signing one message.

0:25:05.870,0:25:07.200
But if you think about the data flow,

0:25:07.200,0:25:09.510
what does it mean[br]to sign the individual bits

0:25:09.510,0:25:11.270
of two different messages,

0:25:11.270,0:25:12.669
then you can get in big trouble.

0:25:12.669,0:25:15.809
So this is a one-time signature system.

0:25:15.809,0:25:19.140
Alright. Here's how Lamport's[br]signature system

0:25:19.140,0:25:21.110
works for one-time signatures

0:25:21.110,0:25:22.919
of any length of message.

0:25:22.919,0:25:26.559
First of all, you scale that 4 bits[br]up to 256 bits.

0:25:26.559,0:25:28.600
And then, if you want to sign[br]whatever length of message,

0:25:28.600,0:25:32.460
you just hash the message to 256 bits.

0:25:32.460,0:25:34.690
And the code for it is very simple.

0:25:34.690,0:25:36.299
This is not quite the state of the art

0:25:36.299,0:25:37.540
for one-time signatures,

0:25:37.540,0:25:38.630
there's fancier things you can do,

0:25:38.630,0:25:41.160
you can sign with Winternitz signatures

0:25:41.160,0:25:46.260
and get instead of something[br]like 256 or 512 hash values

0:25:46.260,0:25:47.740
you can compress that down to like

0:25:47.740,0:25:49.760
50 or even fewer hash values.

0:25:49.760,0:25:52.410
There's all sorts of tricks to[br]trade space for time

0:25:52.410,0:25:53.049
in these systems

0:25:53.049,0:25:56.010
but it's totally feasible to deploy[br]Lamport signatures

0:25:56.010,0:26:00.270
and, well, Winternitz makes it[br]even more practical.

0:26:00.270,0:26:02.690
Alright. What about this[br]one-time restriction?

0:26:02.690,0:26:04.110
So these last, the 4-bit,

0:26:04.110,0:26:05.980
and the Lamport bigger message system,

0:26:05.980,0:26:07.309
these are only usable for,

0:26:07.309,0:26:08.790
you can only use your key

0:26:08.790,0:26:10.620
to sign one message.

0:26:10.620,0:26:13.030
And this was fixed by Merkle.

0:26:13.030,0:26:14.690
What Merkle said was,

0:26:14.690,0:26:18.980
you take 8 Lamport, for example 8,[br]it can be any number,

0:26:18.980,0:26:20.299
here's how we'll make a public key

0:26:20.299,0:26:22.510
that can sign 8 different messages.

0:26:22.510,0:26:24.990
You make, well, 8 different Lamport keys

0:26:24.990,0:26:26.620
and you concatenate them together

0:26:26.620,0:26:28.299
and you use each one just once.

0:26:28.299,0:26:31.410
But it's actually more space-efficient[br]than that sounds.

0:26:31.410,0:26:33.130
So here's what you send along.

0:26:33.130,0:26:38.780
You make 8 Ss there, those are the secret[br]Lamport keys,

0:26:38.780,0:26:41.130
that are able to each sign one message,

0:26:41.130,0:26:43.400
and then you have 8[br]corresponding public keys,

0:26:43.400,0:26:45.490
P1 through P8,

0:26:45.490,0:26:48.040
and then you hash together in a tree,

0:26:48.040,0:26:52.049
you hash together P1 and P2,[br]and P3 and P4

0:26:52.049,0:26:53.380
to form P9 and P10,

0:26:53.380,0:26:55.059
and hash those together to get P13,

0:26:55.059,0:26:58.510
and same over here to get[br]a final public key P15.

0:26:58.510,0:27:01.330
So just one hash value, that's your whole[br]public key.

0:27:01.330,0:27:03.679
And then you have to remember[br]lots of secrets,

0:27:03.679,0:27:06.040
but, okay, nobody has to see[br]those secrets,

0:27:06.040,0:27:08.150
you just keep them on your computer.

0:27:08.150,0:27:09.270
And now what does it look like to,

0:27:09.270,0:27:13.410
to hash, sorry, to sign one message?

0:27:13.410,0:27:17.140
Well, here's what it looks like signing[br]the first message.

0:27:17.140,0:27:18.760
That's when you use S1.

0:27:18.760,0:27:21.059
Once you use S1, you cross it out,

0:27:21.059,0:27:21.940
you never use it again,

0:27:21.940,0:27:23.419
you kill the secret.

0:27:23.419,0:27:25.910
You sign your message with S1,

0:27:25.910,0:27:27.200
and somebody can verify,

0:27:27.200,0:27:30.760
if they see the public key P1[br]for Lamport signatures.

0:27:30.760,0:27:32.309
Or whatever one-time signature system

0:27:32.309,0:27:33.709
you put at the top.

0:27:33.709,0:27:36.870
But, well, your public key[br]in Merkle systems is P15.

0:27:36.870,0:27:40.050
And how does somebody verify that[br]P1 and P15 are related?

0:27:40.050,0:27:44.770
Well, you show them the P2 and the P10[br]and the P14

0:27:44.770,0:27:47.049
that they need to hash together with P1

0:27:47.049,0:27:49.990
to get your public key, P15.

0:27:49.990,0:27:52.210
Alright, and that's as complicated

0:27:52.210,0:27:53.809
as the Merkle signature system gets,

0:27:53.809,0:27:55.880
if you want to be able to sign[br]a million messages,

0:27:55.880,0:27:57.340
you have to have a million secrets,

0:27:57.340,0:27:59.350
but, again, just put it on[br]your local hard drive,

0:27:59.350,0:28:00.900
you're not worried about the space.

0:28:00.900,0:28:03.580
It takes a few moments to generate the key,

0:28:03.580,0:28:06.059
but that's also not a problem.

0:28:06.059,0:28:07.620
Okay.

0:28:07.620,0:28:09.160
Good things about hash-based signatures,

0:28:09.160,0:28:10.490
and a few bad things.

0:28:10.490,0:28:12.309
Good things: It's post-quantum secure,

0:28:12.309,0:28:15.610
we totally understand what hash function[br]security looks like,

0:28:15.610,0:28:19.080
after quantum computers[br]and before quantum computers,

0:28:19.080,0:28:20.730
all you need is a good hash function,

0:28:20.730,0:28:21.830
and there's lots of hash functions

0:28:21.830,0:28:23.330
which have been thoroughly studied,

0:28:23.330,0:28:25.110
so, we're confident they're secure,

0:28:25.110,0:28:27.460
SHA-3 was the result of a long competition

0:28:27.460,0:28:28.990
with lots of people bashing on it,

0:28:28.990,0:28:30.850
and really has no problems.

0:28:30.850,0:28:32.220
The public key is very small,

0:28:32.220,0:28:34.419
just one hash value.

0:28:34.419,0:28:37.360
The security, as I said,[br]is well-understood.

0:28:37.360,0:28:39.840
All the computations are very fast,

0:28:39.840,0:28:41.860
and you can already find[br]standard proposals

0:28:41.860,0:28:42.900
for this system.

0:28:42.900,0:28:45.679
This is going to be the first standardised

0:28:45.679,0:28:50.470
and the first deployed[br]post-quantum public key system.

0:28:50.470,0:28:54.000
On the other hand,[br]if you look at the signature size,

0:28:54.000,0:28:55.380
it's kind of big,

0:28:55.380,0:28:56.740
and then the more scary thing

0:28:56.740,0:28:59.210
is the statefulness.

0:28:59.210,0:29:01.030
That you can only use S1 once,

0:29:01.030,0:29:02.850
and then you have to cross it out.

0:29:02.850,0:29:05.039
You can only use S2 once, and you have to[br]cross it out.

0:29:05.039,0:29:06.330
What if you clone your VM?

0:29:06.330,0:29:08.220
What if you have a backup and restore?

0:29:08.220,0:29:11.250
Then, you've forgotten that you've[br]used S2.

0:29:11.250,0:29:12.179
And then you use it again,

0:29:12.179,0:29:14.470
and then somebody can forge messages,

0:29:14.470,0:29:17.010
just like I was saying before.

0:29:17.010,0:29:18.760
Alright, so state is a problem,

0:29:18.760,0:29:20.130
actually some of you I'm sure were

0:29:20.130,0:29:22.289
in Rutkowska's talk earlier today

0:29:22.289,0:29:24.520
you also heard that[br]state is harmful there.

0:29:24.520,0:29:26.910
And the solution:

0:29:26.910,0:29:29.969
Eliminate the state!

0:29:29.969,0:29:36.360
<i>applause</i>

0:29:36.360,0:29:38.360
I think I only have[br]about three minutes left

0:29:38.360,0:29:41.210
for this, this section, well,[br]this slide,

0:29:41.210,0:29:45.450
but, let me try to briefly say, the idea[br]for getting rid of the state

0:29:45.450,0:29:47.929
is, you have, instead of signatures,

0:29:47.929,0:29:49.860
you have certificate chains.

0:29:49.860,0:29:53.110
So you have whole chain of CAs,

0:29:53.110,0:29:55.730
like, as a signer, you build[br]a whole bunch of CAs,

0:29:55.730,0:29:59.300
you build, say, 2^256[br]certificate authorities.

0:29:59.300,0:30:00.990
Now, that's too much computation to do,

0:30:00.990,0:30:03.010
but you do it on the fly,[br]as you need them.

0:30:03.010,0:30:04.900
So you say, I'm going to sign

0:30:04.900,0:30:08.450
using one of these bottom-level[br]certificate authorities,

0:30:08.450,0:30:10.580
that will sign my actual message.

0:30:10.580,0:30:13.200
And now, you don't have to know[br]anything about any of the others,

0:30:13.200,0:30:16.809
you just pick one and use that to[br]sign your message.

0:30:16.809,0:30:19.570
And then it has to be signed[br]by the parent CA,

0:30:19.570,0:30:20.850
and that's signed by the next parent,

0:30:20.850,0:30:22.870
and so on, up the tree, to the top level,

0:30:22.870,0:30:24.460
only 256 levels.

0:30:24.460,0:30:28.200
And then, okay, you have your[br]certificate chain,

0:30:28.200,0:30:30.950
how do you manufacture these[br]certificate authorities?

0:30:30.950,0:30:35.950
Well, a certificate authority is just[br]some bytes of code on disk,

0:30:35.950,0:30:37.450
that's what real CAs are like,

0:30:37.450,0:30:39.120
and you do the same thing signing,

0:30:39.120,0:30:41.330
and, those bytes of code, you can,

0:30:41.330,0:30:46.030
instead of storing the CA as a program[br]in a configuration file on disk,

0:30:46.030,0:30:48.590
you just generate it on the fly[br]when you need it,

0:30:48.590,0:30:52.370
by taking the position of the CA[br]within this huge tree

0:30:52.370,0:30:56.210
and then hashing that together with[br]some long-term secret.

0:30:56.210,0:30:59.419
That one long-term secret[br]is the only thing you remember.

0:30:59.419,0:31:01.809
So you can manufacture CAs on demand

0:31:01.809,0:31:03.100
in some huge tree

0:31:03.100,0:31:05.570
and have them sign[br]certificates for each other

0:31:05.570,0:31:08.020
only looking at a few CAs that you need

0:31:08.020,0:31:11.000
for the particular signature[br]that you want.

0:31:11.000,0:31:12.409
The reason for having this big tree

0:31:12.409,0:31:14.030
is that then you're never going

0:31:14.030,0:31:17.880
to randomly use the same CA[br]at the bottom twice.

0:31:17.880,0:31:20.470
So the problem of having[br]one-time signatures

0:31:20.470,0:31:21.690
is no longer a problem.

0:31:21.690,0:31:24.690
Each CA will only sign one message.

0:31:24.690,0:31:26.500
Okay, and this is something where

0:31:26.500,0:31:30.309
the original proposal[br]from Goldreich in 87,

0:31:30.309,0:31:32.440
if you use good one-time signatures,

0:31:32.440,0:31:33.809
Winternitz and all that stuff,

0:31:33.809,0:31:38.250
you get something like 0.6 megs[br]for a signature.

0:31:38.250,0:31:40.760
Now that's a little bit inconvenient,

0:31:40.760,0:31:43.130
for comparison, if you do an OS update,

0:31:43.130,0:31:45.580
you look at the average[br]Debian packet size,

0:31:45.580,0:31:47.700
then it's 1.2 megs.

0:31:47.700,0:31:49.900
And then, there is some[br]number of signatures

0:31:49.900,0:31:53.419
with each update, and some[br]of them are in packages,

0:31:53.419,0:31:55.490
and well, it's not inconceivable

0:31:55.490,0:31:57.460
to send 0.6 megs for each signature,

0:31:57.460,0:31:58.799
but it's kind of big.

0:31:58.799,0:32:00.940
And then if you look at, well,

0:32:00.940,0:32:03.470
web pages, say the Alexa top[br]million web pages,

0:32:03.470,0:32:06.860
that average is 1.8 megs.

0:32:06.860,0:32:09.150
And again there's several[br]signatures on the web page,

0:32:09.150,0:32:13.159
depending how many sites are providing[br]graphics for it and so on.

0:32:13.159,0:32:14.860
So, 0.6 megs is maybe a problem.

0:32:14.860,0:32:17.720
But, okay, we took a look at this and

0:32:17.720,0:32:21.520
a bunch of people[br]made the signature a lot smaller,

0:32:21.520,0:32:24.020
0.041 megabytes.

0:32:24.020,0:32:27.059
You know how to make a 41-kilobyte[br]signature sound small:

0:32:27.059,0:32:34.250
only 0.041 megabytes for a sphincs 2^128[br]post-quantum secure signature system.

0:32:34.250,0:32:36.080
If you're interested in more about[br]what sphincs does,

0:32:36.080,0:32:39.830
go to sphincs.cr.yp.to

0:32:39.830,0:32:41.500
Lange: Alright, so.

0:32:41.500,0:32:44.970
Now we have some idea of[br]how we can do signatures.

0:32:44.970,0:32:46.819
And signature's just the thing

0:32:46.819,0:32:48.760
that quantum crypto really[br]really can't do,

0:32:48.760,0:32:51.549
I mean, also, locked briefcases,

0:32:51.549,0:32:56.039
how do you trust that this is[br]actually your locked briefcase?

0:32:56.039,0:32:58.940
But also, public key crypto is a problem.

0:32:58.940,0:33:01.820
So, the one that we recommend

0:33:01.820,0:33:03.340
is code-based cryptography,

0:33:03.340,0:33:05.250
and code, in this context, is not like

0:33:05.250,0:33:07.309
code as in writing a program

0:33:07.309,0:33:10.220
but it comes from error-correcting codes.

0:33:10.220,0:33:12.140
So when you think about,[br]say, your computer,

0:33:12.140,0:33:13.960
you have RAM in there

0:33:13.960,0:33:17.750
and this RAM might get cosmic radiation

0:33:17.750,0:33:19.610
or just a bump somewhere,

0:33:19.610,0:33:20.730
might forget something.

0:33:20.730,0:33:22.280
Or, a more trivial example,

0:33:22.280,0:33:25.090
if you order a book, or, nowadays,

0:33:25.090,0:33:26.739
order any media,

0:33:26.739,0:33:29.280
it has an ISBN number.

0:33:29.280,0:33:32.950
This last digit is dependent on[br]the previous digits.

0:33:32.950,0:33:35.080
So they can figure out whether any[br]of the digits before

0:33:35.080,0:33:37.549
was mistransmitted

0:33:37.549,0:33:39.360
then then go like, hmm,

0:33:39.360,0:33:41.390
that number doesn't exist, try again.

0:33:41.390,0:33:44.990
With your ECC RAM it's actually[br]a little more sophisticated.

0:33:44.990,0:33:46.919
So you have your RAM sitting there,

0:33:46.919,0:33:50.190
and it stores 64 bits.

0:33:50.190,0:33:53.950
But it stores these 64 bits[br]with some redundancy.

0:33:53.950,0:33:57.360
Internally, it has some extra check bits.

0:33:57.360,0:34:00.600
It stores 8 extra bits

0:34:00.600,0:34:02.080
and those 8 extra bits allow you

0:34:02.080,0:34:05.850
to recover the 64[br]that you're interested in

0:34:05.850,0:34:08.190
in case there was some error.

0:34:08.190,0:34:09.339
Not in case of a massive error,

0:34:09.339,0:34:12.619
not in case somebody[br]took a screwdriver and hit it,

0:34:12.619,0:34:14.639
but if there was just one random bit flip,

0:34:14.639,0:34:16.268
you can recover it.

0:34:16.268,0:34:18.210
Also, if two bits flip,

0:34:18.210,0:34:20.289
you can at least figure out[br]that there was something

0:34:20.289,0:34:22.190
and raise a flag.

0:34:22.190,0:34:24.079
So the common scenario in error correction

0:34:24.079,0:34:30.319
is that we have a certain number, say, k[br]bits that we care about

0:34:30.319,0:34:34.199
and then in order to be able[br]to recover those,

0:34:34.199,0:34:35.199
to correct those,

0:34:35.199,0:34:37.248
we add some redundancy.

0:34:37.248,0:34:39.869
So we encapsulate, we encode those k bits

0:34:39.869,0:34:41.569
into n bits.

0:34:41.569,0:34:44.859
Now, we would like to have those n bits

0:34:44.859,0:34:48.109
be not too much larger than k.

0:34:48.109,0:34:50.029
We call those the parity check,

0:34:50.029,0:34:52.239
so this is like from the old days[br]where you check

0:34:52.239,0:34:55.599
"those two add up to zero,[br]zero zero zero...

0:34:55.599,0:34:58.819
oops! there's one, aha, there must[br]have been one bit flip."

0:34:58.819,0:35:03.630
So parity as in, it has to be[br]an even number at the end.

0:35:03.630,0:35:04.960
If you're talking about more positions

0:35:04.960,0:35:07.160
then it's obviously more[br]than just the parity

0:35:07.160,0:35:10.479
but it's parity of some[br]more complicated equations.

0:35:10.479,0:35:17.009
So, if no error occurred, if those 64 bits[br]in your ECC RAM are just fine,

0:35:17.009,0:35:21.969
then all those extra n-k[br]checks will be okay.

0:35:21.969,0:35:25.589
If there was an error,[br]then something will fail,

0:35:25.589,0:35:26.309
raise a flag,

0:35:26.309,0:35:29.180
1, 2, 3 of those will not be satisfied,

0:35:29.180,0:35:32.170
and depending on this error pattern,

0:35:32.170,0:35:36.619
you will be able to recover what[br]was going wrong in those bits.

0:35:36.619,0:35:39.289
It might actually be that[br]it was your parity check bits.

0:35:39.289,0:35:42.289
It might be that one of[br]those 8 extra bits flipped.

0:35:42.289,0:35:45.729
In which case, your 64 bits were just fine

0:35:45.729,0:35:49.649
but you don't know this when[br]you get the error message.

0:35:49.649,0:35:51.759
And, if you have a good code,

0:35:51.759,0:35:54.359
so the kind of code[br]that coding theorists study,

0:35:54.359,0:35:55.339
then you would like to have

0:35:55.339,0:35:59.890
your k pretty large, and the n[br]not too much larger.

0:35:59.890,0:36:02.549
Because that's the amount of storage

0:36:02.549,0:36:03.519
you actually have to afford

0:36:03.519,0:36:07.339
for just getting this much data out of it.

0:36:07.339,0:36:11.400
Now, we get some guarantees[br]when we design these,

0:36:11.400,0:36:14.269
there's a guarantee of getting t errors,

0:36:14.269,0:36:15.729
but for most of the codes that we know,

0:36:15.729,0:36:17.489
the guarantees are actually worse

0:36:17.489,0:36:19.029
than we get in practice,

0:36:19.029,0:36:21.729
so if something guarantees you 100 errors,

0:36:21.729,0:36:25.750
most of the time,[br]you can actually correct 203.

0:36:25.750,0:36:27.249
Um, to get a little bit further

0:36:27.249,0:36:32.930
we actually did to, um, represent[br]those equations with matrix,

0:36:32.930,0:36:37.349
um, not quite this one, sorry.

0:36:37.349,0:36:40.569
So, here's our equations.

0:36:40.569,0:36:45.440
So, small example,[br]we would like to encode 4 bits,

0:36:45.440,0:36:46.900
k is 4,

0:36:46.900,0:36:49.479
and we're adding 3 extra bits.

0:36:49.479,0:36:50.809
That's not very efficient,

0:36:50.809,0:36:54.789
but it's a very nice example[br]that one can see.

0:36:54.789,0:37:01.339
So, those rows there are[br]our parity equations.

0:37:01.339,0:37:03.160
So let's assume we have those 7 bits,

0:37:03.160,0:37:05.549
which add redundancy to it,

0:37:05.549,0:37:07.499
then let's translate this first row,

0:37:07.499,0:37:10.410
which is 1 0 0 1 1 0 1,

0:37:10.410,0:37:13.130
that means we take the first bit,

0:37:13.130,0:37:14.690
skip the second and third,

0:37:14.690,0:37:16.769
so, have be 0,

0:37:16.769,0:37:19.469
and then, bit 3, then the next bit is set

0:37:19.469,0:37:23.119
so bit 4, and then bit 6.

0:37:23.119,0:37:24.969
Second row, similarly,[br]we skip the first one,

0:37:24.969,0:37:26.859
so there's no bit 0, there's a bit 1,

0:37:26.859,0:37:28.479
no bit 2, there's a bit 3,

0:37:28.479,0:37:30.759
it was a 1 1 0 column,

0:37:30.759,0:37:32.979
and then bit 5 and bit 6,

0:37:32.979,0:37:33.930
and similarly.

0:37:33.930,0:37:38.279
So we have a nice diagonal[br]on the left-hand side,

0:37:38.279,0:37:41.589
and then the rest is determined[br]by these equations.

0:37:41.589,0:37:44.140
Now let's assume that[br]something went wrong.

0:37:44.140,0:37:46.049
So we have our 7 bits here,

0:37:46.049,0:37:48.509
and a few hours later we come back

0:37:48.509,0:37:50.630
and want to look at those 7 bits,

0:37:50.630,0:37:52.160
we check whether anything went wrong,

0:37:52.160,0:37:55.619
we run through this parity check program,

0:37:55.619,0:37:58.869
and we actually get a failure pattern.

0:37:58.869,0:38:01.790
If everything was fine,[br]we would have gotten 0 0 0,

0:38:01.790,0:38:05.900
but we're getting 1 0 1.

0:38:05.900,0:38:08.229
So the first equation doesn't hold,

0:38:08.229,0:38:10.219
the second one does hold,

0:38:10.219,0:38:13.349
and the third one does not hold.

0:38:13.349,0:38:17.239
Okay. Where could this come from?

0:38:17.239,0:38:19.239
We're pretty sure that b1 is okay

0:38:19.239,0:38:21.569
because otherwise the second[br]equation would be wrong

0:38:21.569,0:38:24.509
because b1 only appears there,

0:38:24.509,0:38:25.880
and we're also making the promise

0:38:25.880,0:38:27.729
that it would be only one error.

0:38:27.729,0:38:29.339
If you have two errors, three errors,

0:38:29.339,0:38:31.420
then lots of other combinations[br]could occur.

0:38:31.420,0:38:33.289
But it's much more likely that[br]one bit flipped

0:38:33.289,0:38:36.319
than that a whole bunch[br]of bits flipped at once.

0:38:36.319,0:38:39.779
Okay, so, tracing this[br]a little bit further,

0:38:39.779,0:38:42.739
yes, so the b3 would get[br]the two first equations,

0:38:42.739,0:38:45.059
b4, yes! b4 actually would get

0:38:45.059,0:38:48.219
that the first and the third[br]equations are false.

0:38:48.219,0:38:50.809
So by seeing the error pattern 1 0 1,

0:38:50.809,0:38:53.229
we know it was b4.

0:38:53.229,0:38:55.539
Now this is a very nice and small example,

0:38:55.539,0:38:57.710
which doesn't even cover like the ECC RAM,

0:38:57.710,0:39:00.680
but it gives you an idea of how to try it.

0:39:00.680,0:39:02.089
On the other hand, it also gives you

0:39:02.089,0:39:04.549
the idea that you need to do kind of

0:39:04.549,0:39:07.369
brute force search it.

0:39:07.369,0:39:10.549
So for just n=7, you have to[br]try up to 7 times.

0:39:10.549,0:39:12.410
If you now have two errors,

0:39:12.410,0:39:16.309
I would need to try every combination of 2

0:39:16.309,0:39:18.090
out of those n.

0:39:18.090,0:39:23.880
If I have a n which is like 2000 bits,[br]really long,

0:39:23.880,0:39:27.229
and I tell you there's 100 errors,

0:39:27.229,0:39:28.930
so you would need to try every combination

0:39:28.930,0:39:31.089
of 100 positions in there.

0:39:31.089,0:39:33.569
So that would be a huge number.

0:39:33.569,0:39:36.599
That's obviously not a good way[br]of error correction,

0:39:36.599,0:39:37.849
and that's certainly not how

0:39:37.849,0:39:39.690
DVDs and whatever else works.

0:39:39.690,0:39:41.859
Oh yeah, one bit of maths notation,

0:39:41.859,0:39:46.449
so, we call these things,[br]the parentheses up there, matrix,

0:39:46.449,0:39:47.869
and in order to have a shorthand,

0:39:47.869,0:39:54.589
because I can't quite put my 2000 bits[br]times 1000 bits matrix on the page,

0:39:54.589,0:39:57.480
I call this thing H,

0:39:57.480,0:40:01.239
and boldface b is such a bit vector.

0:40:01.239,0:40:04.839
So boldface b is that[br]bits that I'm storing,

0:40:04.839,0:40:08.519
and the combination of[br]applying this matrix,

0:40:08.519,0:40:11.130
wherever is 1, I take the variable,

0:40:11.130,0:40:13.059
where there's a 0, I don't write it,

0:40:13.059,0:40:15.380
that I write as H times b.

0:40:15.380,0:40:16.499
So in maths, if you have seen this,

0:40:16.499,0:40:19.549
this is just a matrix times[br]vector multiplication,

0:40:19.549,0:40:24.069
otherwise, just take this as[br]the instruction of evaluating

0:40:24.069,0:40:28.710
this, each row, as a set of equations.

0:40:28.710,0:40:31.089
Alright, so, to give this some names,

0:40:31.089,0:40:33.920
in coding theory we call c the code word,

0:40:33.920,0:40:37.209
so that's an element[br]which is not compromised,

0:40:37.209,0:40:38.299
which will give you 0,

0:40:38.299,0:40:40.229
then there might be an error vector,

0:40:40.229,0:40:42.180
that's the bits that flip,

0:40:42.180,0:40:44.059
and so, when you retrieve the memory

0:40:44.059,0:40:45.779
or when you have a transmission,

0:40:45.779,0:40:47.089
we call this the received word,

0:40:47.089,0:40:50.239
and that's my b from the previous slide.

0:40:50.239,0:40:52.259
We do like to save on space,

0:40:52.259,0:40:53.420
so when there's this diagonal

0:40:53.420,0:40:55.779
which has all 0s down there

0:40:55.779,0:40:58.019
we just skip it.

0:40:58.019,0:41:05.959
So instead of writing a 7-by-3,[br]we just write 4 columns and 3 rows.

0:41:05.959,0:41:08.200
Now there's lots of stuff[br]happening in coding theory,

0:41:08.200,0:41:10.660
it's a, well, 65 years old topic,

0:41:10.660,0:41:13.200
and we can go up to very large matrices,

0:41:13.200,0:41:16.119
and for some special codes,

0:41:16.119,0:41:17.799
these are the ones that coding theorists[br]come up with,

0:41:17.799,0:41:19.799
we actually have efficient methods.

0:41:19.799,0:41:23.359
Much much nicer than taking[br]every combination of 100 positions

0:41:23.359,0:41:26.549
out of 2000 positions.

0:41:26.549,0:41:29.200
Of course, if you get too many errors,

0:41:29.200,0:41:29.859
you can't correct.

0:41:29.859,0:41:32.680
You can only correct up to[br]whatever the promise is,

0:41:32.680,0:41:34.640
plus maybe a little bit later.

0:41:34.640,0:41:36.549
But if you don't know[br]any of the structure,

0:41:36.549,0:41:39.380
if you don't know what[br]the coding theorists put into it,

0:41:39.380,0:41:42.729
or if this H matrix got somewhat perturbed

0:41:42.729,0:41:47.439
by me giving a slightly[br]different representation,

0:41:47.439,0:41:50.709
I don't call this b1 anymore,[br]I call it now b17,

0:41:50.709,0:41:52.150
and let's flip those and so on,

0:41:52.150,0:41:55.250
suddenly it doesn't look like[br]the code that you're used to.

0:41:55.250,0:41:58.289
If it's a random matrix,

0:41:58.289,0:42:00.200
the best attacks are not quite as bad

0:42:00.200,0:42:02.999
as picking 100 out of 2000,

0:42:02.999,0:42:04.670
but they are close to that,

0:42:04.670,0:42:05.980
they're pretty slow attacks,

0:42:05.980,0:42:08.959
it's an exponential-time algorithm,

0:42:08.959,0:42:11.279
if you have a random matrix.

0:42:11.279,0:42:12.999
And so what we're doing[br]in code-based crypto

0:42:12.999,0:42:16.009
is to use this difference for encryption.

0:42:16.009,0:42:17.599
Now going back again to the 70s,

0:42:17.599,0:42:21.009
so, basically, yes, the stuff that we're[br]really confident in

0:42:21.009,0:42:22.829
that it will last another 100 years,

0:42:22.829,0:42:25.299
is the stuff from the 70s that lots of[br]people have looked at,

0:42:25.299,0:42:27.299
so, McEliece in 1978,

0:42:27.299,0:42:29.779
so just the year after RSA,

0:42:29.779,0:42:35.719
came up with a system[br]which is using encoding as encryption.

0:42:35.719,0:42:38.369
So your method is,

0:42:38.369,0:42:40.930
you just encode a vector, your message,

0:42:40.930,0:42:42.900
and then you add some errors to it.

0:42:42.900,0:42:44.880
And, if the other side doesn't have

0:42:44.880,0:42:47.379
an efficient algorithm to decode,

0:42:47.379,0:42:49.459
they actually can't break it.

0:42:49.459,0:42:51.700
They're using a special code in there,

0:42:51.700,0:42:53.449
so there's a code from Goppa

0:42:53.449,0:42:56.059
from a few years earlier than that,

0:42:56.059,0:42:58.029
and that code, so far, nobody has found

0:42:58.029,0:43:00.819
any way to take the perturbed,

0:43:00.819,0:43:03.119
this complicated way of representing it,

0:43:03.119,0:43:06.549
and coming up with[br]efficient decoding algorithm.

0:43:06.549,0:43:10.660
1986, Niederreither came up with[br]a version of McEliece

0:43:10.660,0:43:13.359
which is smaller,[br]the code size is smaller,

0:43:13.359,0:43:15.529
the public key size is smaller,

0:43:15.529,0:43:19.180
and we have similar things to

0:43:19.180,0:43:21.239
what you've seen before,[br]so we have those H matrix,

0:43:21.239,0:43:22.619
we skip the diagonal,

0:43:22.619,0:43:28.499
we just represent this H as our public key[br]as the remaining part of the matrix,

0:43:28.499,0:43:33.139
the secret key, that's the algorithm[br]that only I know.

0:43:33.139,0:43:34.769
It's a Goppa code,

0:43:34.769,0:43:35.890
but it's a Goppa code

0:43:35.890,0:43:39.259
and there's many many Goppa codes[br]for the same size.

0:43:39.259,0:43:40.549
So that's something that Goppa says,

0:43:40.549,0:43:41.829
well, if you want to have Goppa codes

0:43:41.829,0:43:46.969
with 2000 bits[br]that can correct 200 errors,

0:43:46.969,0:43:47.829
here's how you set it up,

0:43:47.829,0:43:51.200
but there's lots and lots and lots[br]of choices in there.

0:43:51.200,0:43:52.469
And your encryption is just,

0:43:52.469,0:43:54.910
take an error vector,

0:43:54.910,0:43:57.269
with a fixed number of bits,

0:43:57.269,0:43:59.479
and send me the error pattern of it.

0:43:59.479,0:44:04.049
So the outcome of multiplying H by this e.

0:44:04.049,0:44:05.509
And then we want to use this in crypto,

0:44:05.509,0:44:08.209
so we use the hash of this to encrypt it.

0:44:08.209,0:44:12.329
Um, then Peter Schwabe and[br]Tung Chou, our PhD student,

0:44:12.329,0:44:14.349
wrote a very efficient[br]implementation of this

0:44:14.349,0:44:15.729
called mcbits,

0:44:15.729,0:44:17.380
so if you want to have more detail

0:44:17.380,0:44:19.619
on how you could really[br]use this in practice,

0:44:19.619,0:44:21.350
then go to that url.

0:44:21.350,0:44:23.339
Um, but let me talk a little bit

0:44:23.339,0:44:26.130
about why we are confident in this.

0:44:26.130,0:44:28.180
Code-based crypto is less obvious[br]than hash-based,

0:44:28.180,0:44:30.420
I mean with hash-based it's like,

0:44:30.420,0:44:32.079
the, all we're doing is, hash.

0:44:32.079,0:44:35.569
A hash function by definition is[br]something which is one-way.

0:44:35.569,0:44:39.559
For this code-based crypto,[br]you need to think a little more,

0:44:39.559,0:44:41.170
to have people studying it

0:44:41.170,0:44:44.630
to figure out why this[br]actually can be secure.

0:44:44.630,0:44:47.619
Now, the attacks, if I may say so,

0:44:47.619,0:44:49.390
started before the cryptosystem[br]was proposed,

0:44:49.390,0:44:50.999
so it was another hard problem

0:44:50.999,0:44:53.410
that coding theorists were[br]studying naturally,

0:44:53.410,0:44:56.219
and then McEliece said, hey, we have[br]this hard problem here,

0:44:56.219,0:44:58.940
decoding a random code is not easy,

0:44:58.940,0:45:01.539
well, actually, afterwards, figuring out,

0:45:01.539,0:45:05.039
well, if you have a really random code,

0:45:05.039,0:45:07.569
even finding out whether there is[br]a smaller code word is NP-hard.

0:45:07.569,0:45:12.240
And then, once it was a cryptosystem,

0:45:12.240,0:45:14.890
so, Omura, Lee-Brickell, all of those,

0:45:14.890,0:45:17.519
those come after[br]it was proposed for crypto.

0:45:17.519,0:45:20.529
There's some which have an extra[br]parenthetic comment,

0:45:20.529,0:45:23.930
those are papers which study[br]the security of McEliece

0:45:23.930,0:45:25.420
if the attacker has a quantum computer,

0:45:25.420,0:45:27.329
so there's been lots and lots of work

0:45:27.329,0:45:30.420
for studying it[br]against a classical computer,

0:45:30.420,0:45:31.849
and there's been some work

0:45:31.849,0:45:33.719
studying it against quantum computers.

0:45:33.719,0:45:36.170
It's pretty clear that we can't use Shor,

0:45:36.170,0:45:37.390
but we can use Grover,

0:45:37.390,0:45:42.180
and it's not so easily obvious[br]how much Grover can give us.

0:45:42.180,0:45:44.359
However, the best that Grover can do

0:45:44.359,0:45:46.519
is basically halve the bit size.

0:45:46.519,0:45:49.140
So we had this AES-128,[br]leading to 64-bit security,

0:45:49.140,0:45:50.769
so if you're conservative,

0:45:50.769,0:45:54.430
if you want to be like really really[br]on the secure size,

0:45:54.430,0:45:58.559
then let's assume that we want to go for[br]pre-quantum security at least 256

0:45:58.559,0:46:02.469
in order to get post-quantum security 128.

0:46:02.469,0:46:04.440
So here are some key sizes,

0:46:04.440,0:46:07.759
so if you're okay with 1000 kilobytes,

0:46:07.759,0:46:14.690
then you're getting something[br]which is at least 131 post-quantum secure,

0:46:14.690,0:46:17.170
and that's actually very conservative,

0:46:17.170,0:46:20.289
most likely we can go much down[br]on the key size.

0:46:20.289,0:46:22.049
But that's where more research is needed.

0:46:22.049,0:46:25.660
If you need something where you can get[br]a guarantee of 100 years security,

0:46:25.660,0:46:27.349
take this one,

0:46:27.349,0:46:28.809
it's not small,

0:46:28.809,0:46:31.650
it's fast, but it's not small,

0:46:31.650,0:46:34.479
and hopefully in 5 years,[br]less than 5 years,

0:46:34.479,0:46:37.249
they can give you something[br]which is smaller

0:46:37.249,0:46:39.669
and still as secure.

0:46:39.669,0:46:40.380
djb: Okay.

0:46:40.380,0:46:45.079
There are lots of possibilities for[br]what the smaller things might be,

0:46:45.079,0:46:47.919
for instance, there's something[br]called QC-MDPC,

0:46:47.919,0:46:48.930
there's actually lots and lots

0:46:48.930,0:46:50.680
of variations of McEliece

0:46:50.680,0:46:51.599
that people have proposed,

0:46:51.599,0:46:53.849
and some of those variations have held up,

0:46:53.849,0:46:55.109
some of them haven't.

0:46:55.109,0:46:58.479
QC-MDPC is something that has[br]held up so far,

0:46:58.479,0:47:00.339
but how many people've looked at it,

0:47:00.339,0:47:03.539
and what's going to happen when[br]more attacks get optimised?

0:47:03.539,0:47:06.039
You can't be trusting something which

0:47:06.039,0:47:09.140
is new or hasn't been studied enough,

0:47:09.140,0:47:10.849
or hasn't been studied[br]in the right directions,

0:47:10.849,0:47:13.089
you also have to be sceptical[br]about crypto.

0:47:13.089,0:47:14.949
There's, well, lots of proposals,

0:47:14.949,0:47:17.759
QC-MDPC looks like one of the most[br]interesting ones,

0:47:17.759,0:47:20.930
that nobody's been able to damage[br]its security,

0:47:20.930,0:47:23.680
for 2^80 pre-quantum security,

0:47:23.680,0:47:24.819
which is not very good,

0:47:24.819,0:47:26.479
but, just as an example,

0:47:26.479,0:47:30.160
they have 0.6 kilobytes, or 600 bytes,

0:47:30.160,0:47:31.789
for the public key,

0:47:31.789,0:47:34.329
and that's a very reasonable size[br]for a public key,

0:47:34.329,0:47:35.449
not as small as ECC

0:47:35.449,0:47:37.039
but it's quite tolerable.

0:47:37.039,0:47:38.910
Um, lattice-based crypto,

0:47:38.910,0:47:40.009
there's NTRU, for example,

0:47:40.009,0:47:42.099
that's been around since the 1990s,

0:47:42.099,0:47:44.729
and maybe that's enough time to start[br]getting confident,

0:47:44.729,0:47:46.690
but, well, again, there's[br]lattice-based systems

0:47:46.690,0:47:48.079
that get proposed and broken,

0:47:48.079,0:47:52.009
for instance, there's a system from[br]Smart-Vercauteren in 2009,

0:47:52.009,0:47:54.699
that was, it's not broken pre-quantum,

0:47:54.699,0:47:58.749
but it was shown in 2014-2015,[br]some follow-up papers,

0:47:58.749,0:48:02.029
to be broken in polynomial time[br]by a quantum computer.

0:48:02.029,0:48:05.130
So, it's a lattice-based system which[br]sounded good at the beginning,

0:48:05.130,0:48:08.469
but is definitely not going to be part of[br]post-quantum cryptography.

0:48:08.469,0:48:09.529
There's multivariate-quadratic,

0:48:09.529,0:48:12.150
now those have[br]the interesting feature that

0:48:12.150,0:48:15.109
the signatures they provide[br]can be very very small,

0:48:15.109,0:48:17.289
like, you can have 100-bit signatures

0:48:17.289,0:48:19.239
and still get some reasonable security

0:48:19.239,0:48:20.989
that nobody knows how to break these,

0:48:20.989,0:48:22.759
well, there's lots and lots[br]of these proposals

0:48:22.759,0:48:24.819
and some of them are broken,[br]some of them...

0:48:24.819,0:48:27.680
HFEv-, that's a multivariate[br]quadratic system

0:48:27.680,0:48:31.140
that's been unbroken for 20 years.

0:48:31.140,0:48:32.489
Maybe it will continue holding up,

0:48:32.489,0:48:34.190
but, well, how many people have looked?

0:48:34.190,0:48:36.839
You have to make sure enough people[br]look at these things.

0:48:36.839,0:48:39.469
The reason we like these[br]simple systems from the 70s is

0:48:39.469,0:48:40.229
enough people have looked

0:48:40.229,0:48:42.910
but maybe if you've got more serious[br]performance constraints

0:48:42.910,0:48:44.319
you should look at these other things,

0:48:44.319,0:48:46.359
and of course we are looking at[br]these other things,

0:48:46.359,0:48:47.660
trying to figure out what's secure,

0:48:47.660,0:48:51.799
and how well we can actually, er,

0:48:51.799,0:48:54.179
choose among all these[br]different possibilities.

0:48:54.179,0:48:56.139
Something else, just last mention here,

0:48:56.139,0:48:57.299
is isogeny-based,

0:48:57.299,0:48:59.469
this is for people who like[br]elliptic curves,

0:48:59.469,0:49:02.930
that there is maybe a way to use[br]elliptic curves post-quantum,

0:49:02.930,0:49:04.289
and this has the interesting feature

0:49:04.289,0:49:07.690
that it does exactly the same data flows[br]as Diffie-Hellman.

0:49:07.690,0:49:09.599
So everything you're used to doing[br]with Diffie-Hellman,

0:49:09.599,0:49:11.709
and having, like, a secret key over here

0:49:11.709,0:49:13.109
and a public key over there,

0:49:13.109,0:49:15.940
agree on a shared secret,

0:49:15.940,0:49:18.279
that you can also do with[br]isogeny-based systems,

0:49:18.279,0:49:20.519
but only a few people[br]have studied the security

0:49:20.519,0:49:21.999
and maybe this'll also get broken.

0:49:21.999,0:49:25.000
So, a lots more work,[br]lots more possibilities.

0:49:25.000,0:49:27.969
Last slide, if you're interested[br]in more information

0:49:27.969,0:49:29.909
here are a few places to look,

0:49:29.909,0:49:32.209
first of all you can go to pqcrypto.org,

0:49:32.209,0:49:36.640
so this is our first survey site[br]for post-quantum cryptography,

0:49:36.640,0:49:38.269
and the biggest chunk of information there

0:49:38.269,0:49:42.369
is bibliography, and if anybody has[br]newer papers,

0:49:42.369,0:49:45.539
if you happen to write papers on[br]post-quantum crypto,

0:49:45.539,0:49:46.989
and you'd like us to add those,

0:49:46.989,0:49:48.119
then just let us know,

0:49:48.119,0:49:51.170
um, and then, well,[br]we also have on the front page

0:49:51.170,0:49:53.849
things like pointers to all[br]the PQCrypto conferences,

0:49:53.849,0:49:54.769
that's the main place to look,

0:49:54.769,0:49:57.150
go to pqcrypto.org and follow links to,

0:49:57.150,0:49:59.819
for instance, the February[br]Japan conference.

0:49:59.819,0:50:02.390
Then pqcrypto.eu.org, that's the main page

0:50:02.390,0:50:05.459
for the EU project that Tanja mentioned,

0:50:05.459,0:50:08.229
which is putting out as it progresses,

0:50:08.229,0:50:09.640
well, it just started this year, but

0:50:09.640,0:50:13.499
it's putting out, soon, free libraries!

0:50:13.499,0:50:16.439
Software libraries, for actually doing[br]post-quantum cryptography.

0:50:16.439,0:50:18.309
And benchmarking results,

0:50:18.309,0:50:19.199
so you can actually say

0:50:19.199,0:50:21.420
"Yeah, I've got the following performance[br]constraints here,

0:50:21.420,0:50:23.070
that's what I'm able to use."

0:50:23.070,0:50:25.039
And then in 2017, there's going to be

0:50:25.039,0:50:28.920
a workshop, and a summer school, maybe[br]it'll be a spring school, we'll see,

0:50:28.920,0:50:34.239
if you're interested in the Twitter feed[br]for that, then twitter.com/pqc_eu

0:50:34.239,0:50:37.190
and final resource on the slide is you.

0:50:37.190,0:50:40.130
You have the responsibility[br]if you care about crypto,

0:50:40.130,0:50:42.440
then you have to get used to this stuff.

0:50:42.440,0:50:43.699
You have to learn about hash-based,

0:50:43.699,0:50:47.029
code-based, maybe lattice-based,[br]multivariate quadratics,

0:50:47.029,0:50:49.529
these are the things which will be[br]the future of crypto.

0:50:49.529,0:50:53.819
In the future, all of crypto will be[br]post-quantum crypto,

0:50:53.819,0:50:56.569
because eventually the attackers[br]will have quantum computers.

0:50:56.569,0:50:58.479
If you want to adapt to that future,

0:50:58.479,0:51:00.369
then, well, take a look at these sytems

0:51:00.369,0:51:02.229
and see, maybe find improvements,

0:51:02.229,0:51:03.519
then, cool, then let us know,

0:51:03.519,0:51:05.539
and, you know, publish papers,

0:51:05.539,0:51:08.299
integrate them into real applications,[br]networking applications,

0:51:08.299,0:51:09.969
implement the things[br]that aren't implemented,

0:51:09.969,0:51:10.779
speed them up,

0:51:10.779,0:51:12.840
there's lots of work that[br]still has to be done.

0:51:12.840,0:51:15.050
That's it, thank you for your attention.

0:51:15.050,0:51:28.799
<i>applause</i>

0:51:28.799,0:51:33.589
Herald: Wow. Now we'll have some[br]short questions please.

0:51:33.589,0:51:35.660
Because we're a bit late on time.

0:51:35.660,0:51:39.559
Questioners, go around ahead,[br]there's a mike there,

0:51:39.559,0:51:41.749
talk into it please.

0:51:41.749,0:51:42.910
Can we have mike 1?

0:51:42.910,0:51:45.869
Q: Oh, okay. Uh, quick question.

0:51:45.869,0:51:50.239
So there was this result of[br]Laszlo Babai that there's a,

0:51:50.239,0:51:56.059
that graph isomorphism has a[br]quasipolynomial time algorithm,

0:51:56.059,0:52:00.219
um, not really knowing the subject at all,

0:52:00.219,0:52:04.260
there's some very, very[br]superficial similarities,

0:52:04.260,0:52:08.709
like, that is a hidden subgroup [br]problem, basically.

0:52:08.709,0:52:11.849
Um, is there going to be any, like,

0:52:11.849,0:52:14.289
is there any indication that the methods[br]he used in that proof

0:52:14.289,0:52:16.989
are relevant to breaking, like,

0:52:16.989,0:52:20.279
to weakening NTRU or things like this?

0:52:20.279,0:52:25.729
djb: That's a good question. So, the, um,[br]the graph isomorphism advance now,

0:52:25.729,0:52:27.069
is basically saying,

0:52:27.069,0:52:30.229
so, graph isomorphism is a problem[br]which was famous as being

0:52:30.229,0:52:32.619
not know to be solvable in polynomial

0:52:32.619,0:52:35.160
or even, like you said,[br]quasipolynomial time.

0:52:35.160,0:52:38.209
Um, except there were some really good[br]software algorithms

0:52:38.209,0:52:41.069
which would solve most cases of it,[br]really quickly.

0:52:41.069,0:52:42.680
There were just some really weird,

0:52:42.680,0:52:43.849
highly symmetric cases,

0:52:43.849,0:52:44.630
that were hard to solve

0:52:44.630,0:52:47.249
and that's what Babai managed[br]to completely kill now,

0:52:47.249,0:52:49.349
so he's handled all the cases.

0:52:49.349,0:52:51.949
But we try to stay away from[br]problems like that in crypto,

0:52:51.949,0:52:54.660
so, an example that's very closely[br]analogous to that is

0:52:54.660,0:52:56.589
what's called support splitting,

0:52:56.589,0:52:58.640
which is a certain type of attack strategy

0:52:58.640,0:53:00.599
against code-based crypto

0:53:00.599,0:53:03.190
if somebody gives away lots of information

0:53:03.190,0:53:05.039
from the legitimate user.

0:53:05.039,0:53:07.199
And that's something where the[br]support-splitting algorithm

0:53:07.199,0:53:09.420
works in most cases,

0:53:09.420,0:53:12.529
but it kind of fails in some corner cases,

0:53:12.529,0:53:16.079
and, well, we try to stay away from[br]thinking about this anyway,

0:53:16.079,0:53:18.690
because you just don't want to give[br]somebody that extra information,

0:53:18.690,0:53:23.249
but if you did, then maybe Babai's[br]technique could be useful there.

0:53:23.249,0:53:25.739
Herald: Thank you. This talk is not over.

0:53:25.739,0:53:30.009
If you're leaving, which is okay,[br]please be silent.

0:53:30.009,0:53:33.670
Next question, number 3, no, number 1.

0:53:33.670,0:53:35.779
Q: Uh, hello, thank you for the talk.

0:53:35.779,0:53:40.430
Um, how are the chances to have something[br]like forward secrecy with that?

0:53:40.430,0:53:43.729
I recognise the last algorithm[br]has a chance

0:53:43.729,0:53:45.339
to reuse Diffie-Hellman,

0:53:45.339,0:53:47.739
that's possibly the only one?

0:53:47.739,0:53:51.619
Lange: So, if you think that[br]forward secrecy means Diffie-Hellman,

0:53:51.619,0:53:55.759
you can have forward secrecy[br]from normal encryption algorithms,

0:53:55.759,0:53:58.249
at the expense of generating[br]a new key each time.

0:53:58.249,0:54:00.670
You can have forward secrecy with RSA,

0:54:00.670,0:54:03.140
if Alice talking to Bob starts by saying

0:54:03.140,0:54:06.440
"Okay, this is my one-time RSA key,

0:54:06.440,0:54:08.459
and I send this to Bob,

0:54:08.459,0:54:12.609
with a request to encrypt to this key."

0:54:12.609,0:54:16.099
If Alice never reuses this key,

0:54:16.099,0:54:18.170
then this method is forward-secure.

0:54:18.170,0:54:21.039
And similar to how you can[br]do this with RSA keys,

0:54:21.039,0:54:23.420
you can also do this with McEliece keys.

0:54:23.420,0:54:25.489
At the moment, there is a difficulty

0:54:25.489,0:54:29.449
that the keys are very large.

0:54:29.449,0:54:32.719
It is inconvenient when you want[br]to start talking,

0:54:32.719,0:54:35.849
"Hey, I'm a client, hello server,[br]please talk to me",

0:54:35.849,0:54:37.289
and the first thing you have to do

0:54:37.289,0:54:41.900
is transmit a megabyte of key.

0:54:41.900,0:54:44.229
On the other hand, you can do it.

0:54:44.229,0:54:47.719
It just requires you to engineer[br]your protocol to expect,

0:54:47.719,0:54:50.999
yes, you have to send a few packages.

0:54:50.999,0:54:53.959
And then it has all the[br]forward secrecy that you want.

0:54:53.959,0:54:58.180
Q: But, uh, a way without[br]transferring the key,

0:54:58.180,0:54:59.449
like Diffie-Hellman?

0:54:59.449,0:55:02.509
Lange: But, Diffie-Hellman[br]is transferring a key.

0:55:02.509,0:55:03.259
Q: Okay.

0:55:03.259,0:55:04.989
Lange: I mean, you're basically[br]transferring

0:55:04.989,0:55:07.349
the first part of a discrete log pair.

0:55:07.349,0:55:10.299
If Alice sends a*p, and there is[br]some one-time key,

0:55:10.299,0:55:12.219
she's sending a public key.

0:55:12.219,0:55:16.029
It's just that the method of how[br]those two public keys interact

0:55:16.029,0:55:19.279
is slightly different from how[br]RSA encryption works.

0:55:19.279,0:55:20.980
Q: Okay, thank you.

0:55:20.980,0:55:25.049
Herald: Thank you. Do we have[br]an Internet message? Question?

0:55:25.049,0:55:30.170
Signal Angel: Actually, we do. There are[br]two questions that are somehow related.

0:55:30.170,0:55:31.479
The first one is:

0:55:31.479,0:55:37.299
Given that there is no actual working[br]quantum computer,

0:55:37.299,0:55:40.619
how do you start developing[br]a crypto algorithm?

0:55:40.619,0:55:42.410
Where do you start, how do you design it,

0:55:42.410,0:55:46.140
how do you test it? Is there a way[br]to prove that it's secure?

0:55:46.140,0:55:49.349
And the second question is related:

0:55:49.349,0:55:55.079
The whole thing is based on the property[br]of the hash functions being one-way,

0:55:55.079,0:55:57.969
how does one know that there is no[br]quantum algorithm

0:55:57.969,0:55:59.920
that breaks this property?

0:55:59.920,0:56:01.859
Can you prove this?

0:56:01.859,0:56:03.729
djb: Okay. For both of these questions,

0:56:03.729,0:56:06.079
the technique that the community[br]goes through,

0:56:06.079,0:56:08.189
that we all go through,[br]is cryptanalysis.

0:56:08.189,0:56:11.219
So we have as many smart people as[br]we can find

0:56:11.219,0:56:12.989
focusing on these problems and saying

0:56:12.989,0:56:16.549
"Can you find an algorithm which is[br]breaking these problems

0:56:16.549,0:56:19.069
better than any previous algorithms can?"

0:56:19.069,0:56:20.999
and we put as many incentives as we can

0:56:20.999,0:56:23.099
so that we try to get as many smart people

0:56:23.099,0:56:25.299
to stay ahead of the bad guys,

0:56:25.299,0:56:27.299
and hopefully find the best algorithms.

0:56:27.299,0:56:28.709
But there's no guarantees in this.

0:56:28.709,0:56:30.449
And you do always have to be sceptical

0:56:30.449,0:56:33.140
about whether people have[br]actually looked at, for instance

0:56:33.140,0:56:35.359
quantum algorithms to attack systems.

0:56:35.359,0:56:36.829
And there is that extra difficulty

0:56:36.829,0:56:39.819
that the first part of the question,[br]at the beginning, was saying,

0:56:39.819,0:56:41.809
that we don't have a quantum computer.

0:56:41.809,0:56:45.339
So if we're trying to verify quantum[br]algorithms that we're developing,

0:56:45.339,0:56:47.589
we don't get to experiment with them.

0:56:47.589,0:56:50.549
That's the usual procedure for[br]making sure your algorithms work.

0:56:50.549,0:56:52.559
In state-of-the-art cryptanalysis,

0:56:52.559,0:56:55.029
like the number field sieve for factoring,

0:56:55.029,0:56:57.880
that does not have a proof that[br]it works in any particular,

0:56:57.880,0:56:59.789
well, at the speed that we think,

0:56:59.789,0:57:01.349
it works out from experiment.

0:57:01.349,0:57:03.329
So experiments are really important,

0:57:03.329,0:57:05.829
because we don't have proofs[br]for state-of-the-art cryptanalysis,

0:57:05.829,0:57:09.759
and that's something where it's actually[br]really tough for quantum computers.

0:57:09.759,0:57:11.859
Of course eventually we'll all have[br]quantum computers,

0:57:11.859,0:57:14.869
and there's ideas for simulating[br]quantum algorithms

0:57:14.869,0:57:18.359
which have had some success[br]at verifying that algorithms work

0:57:18.359,0:57:20.579
even though we can't actually[br]run them yet.

0:57:20.579,0:57:25.050
That we're actually able to verify[br]a simulation of those algorithms.

0:57:25.050,0:57:27.530
Lange: Let me do a second part of this.

0:57:27.530,0:57:30.769
Um, when we use quantum cryptanalysis,

0:57:30.769,0:57:33.189
for estimates, we usually go[br]for the worst-case estimate.

0:57:33.189,0:57:39.230
So we say, well, McEliece, at worst,[br]gets broken to half the security level.

0:57:39.230,0:57:41.380
Most likely it won't be that fast,

0:57:41.380,0:57:45.609
but we're staying on the side[br]where we're very confident.

0:57:45.609,0:57:48.349
Um, if I understood correctly[br]there was also the part of the question,

0:57:48.349,0:57:50.099
how can we test the algorithms?

0:57:50.099,0:57:52.670
If this is for[br]the constructive algorithms,

0:57:52.670,0:57:54.369
then all the algorithms we analyse,

0:57:54.369,0:57:56.900
all the algorithms we propose[br]for post-quantum crypto,

0:57:56.900,0:57:59.939
are algorithms that you can run on[br]your normal computer.

0:57:59.939,0:58:02.309
So, you can test those, you can run those,

0:58:02.309,0:58:04.189
we have benchmarking numbers from those,

0:58:04.189,0:58:07.219
on our current hardware.

0:58:07.219,0:58:12.019
Herald: We'll do two more questions,[br]please. Number 1.

0:58:12.019,0:58:15.630
Q: Yeah, I got a question on[br]the practicality of the attacks.

0:58:15.630,0:58:19.150
So, um, if we assume there is[br]a quantum computer,

0:58:19.150,0:58:21.729
how much time will it take in practice,

0:58:21.729,0:58:22.900
order of magnitude,

0:58:22.900,0:58:25.729
to break, let's say, RSA 2048-bit key?

0:58:25.729,0:58:28.829
Is it on the order of hours,[br]weeks, months, years?

0:58:28.829,0:58:31.169
Lange: <i>snaps fingers</i> Done.

0:58:31.169,0:58:32.349
Q: Okay, thanks.

0:58:32.349,0:58:32.939
<i>laughter</i>

0:58:32.939,0:58:36.289
djb: That was easy![br]Herald: Number 3.

0:58:36.289,0:58:36.869
Q: Okay.

0:58:36.869,0:58:38.599
Herald: Talk into the mike, please.

0:58:38.599,0:58:41.369
Q: Thank you. So, it's very,[br]very nice to have

0:58:41.369,0:58:45.789
both quantum encryption and signing,

0:58:45.789,0:58:48.650
but do you know anything about[br]some other cryptographic primitives,

0:58:48.650,0:58:52.499
such as zero-knowledge proofs?

0:58:52.499,0:58:53.499
Lange: Well, I mean, zero-knowledge proofs

0:58:53.499,0:58:56.920
are basically signatures[br]which are not interactive.

0:58:56.920,0:58:59.580
So if you have something which is, um,

0:58:59.580,0:59:02.249
a primitive for a signature is usually[br]very closely related

0:59:02.249,0:59:03.789
to zero-knowledge proofs.

0:59:03.789,0:59:05.739
So, there is work going on,

0:59:05.739,0:59:07.680
we are focusing on[br]the most important things

0:59:07.680,0:59:10.049
that we see on the Internet,

0:59:10.049,0:59:12.579
but, that shouldn't mean that people[br]shouldn't do research on it.

0:59:12.579,0:59:17.060
Please do research on[br]zero-knowledge proofs!

0:59:17.060,0:59:21.539
Herald: Okay. Last question. Number 1.

0:59:21.539,0:59:24.859
Q: So, why do you put so much emphasis

0:59:24.859,0:59:28.549
on smaller key sizes and[br]on performance in encryption,

0:59:28.549,0:59:34.529
um, especially in a delicate topic like[br]post-quantum computing?

0:59:34.529,0:59:37.269
Why can't we just use 1-megabyte keys

0:59:37.269,0:59:41.859
and why can't we just use a few seconds[br]instead of miliseconds

0:59:41.859,0:59:43.599
to compute those?[br]Lange: So...

0:59:43.599,0:59:44.949
Q: What's the the problem here?

0:59:44.949,0:59:47.660
Lange: We are suggesting[br]to use a key of 1 megabyte.

0:59:47.660,0:59:51.809
So, our recommendation that we have on[br]the Internet on the pqcrypto.org page

0:59:51.809,0:59:56.180
are precisely using this system[br]which has a 1-megabyte key.

0:59:56.180,0:59:58.329
The nice thing is, that actually

0:59:58.329,1:00:02.449
encryption and decryption[br]are very efficient.

1:00:02.449,1:00:03.579
But that was not our main goal,

1:00:03.579,1:00:06.430
our main goal was to get something[br]which is very secure,

1:00:06.430,1:00:11.329
and where we have a high confidence[br]that we actually understand the attack.

1:00:11.329,1:00:14.009
And then, well, once we have this system,

1:00:14.009,1:00:17.520
then you try to optimise[br]how to implement it,

1:00:17.520,1:00:19.279
and the implementation,[br]when we looked at the numbers

1:00:19.279,1:00:22.039
is actually faster than[br]elliptic curve implementations

1:00:22.039,1:00:23.910
except for the size.

1:00:23.910,1:00:26.329
So, you get a very nice speed,

1:00:26.329,1:00:31.790
even though it was not our[br]target for optimisation.

1:00:31.790,1:00:33.379
Herald: Okay, this is it.

1:00:33.379,1:00:35.430
Thank you very much,[br]let's have a final hand

1:00:35.430,1:00:38.479
for Tanja Lange and djb Bernstein!

1:00:38.479,1:00:46.360
<i>applause</i>

1:00:46.360,1:00:51.397
<i>postroll music</i>

1:00:51.397,1:00:58.000
Untertitel erstellt von c3subtitles.de[br]im Jahr 2016. Mach mit und hilf uns!