ABOUT THE SPEAKER
Craig Costello - Cryptographer
Craig Costello uses mathematics to secure the digital world, both against the threats that exist today and those that may exist in the future.

Why you should listen
Together with his colleagues, Craig Costello builds software with the goal of safeguarding the internet before large-scale quantum computing becomes a reality. He is a senior researcher in the Cryptography and Security Group at Microsoft Research in the USA. He is primarily interested in the cryptographic applications of computational number theory, in particular curve-, pairing- and lattice-based cryptography.
More profile about the speaker
Craig Costello | Speaker | TED.com
TEDxSydney

Craig Costello: In the war for information, will quantum computers defeat cryptographers?

Filmed:
1,426,098 views

In this glimpse into our technological future, cryptographer Craig Costello discusses the world-altering potential of quantum computers, which could shatter the limits set by today's machines -- and give code breakers a master key to the digital world. See how Costello and his fellow cryptographers are racing to reinvent encryption and secure the internet.
- Cryptographer
Craig Costello uses mathematics to secure the digital world, both against the threats that exist today and those that may exist in the future. Full bio

Double-click the English transcript below to play the video.

00:12
I'm in the business
of safeguarding secrets,
0
782
3275
00:16
and this includes your secrets.
1
4081
2172
00:19
Cryptographers are
the first line of defense
2
7206
2134
00:21
in an ongoing war that's been
raging for centuries:
3
9364
3582
00:24
a war between code makers
4
12970
2263
00:27
and code breakers.
5
15257
1252
00:29
And this is a war on information.
6
17030
2094
00:32
The modern battlefield
for information is digital.
7
20227
3484
00:35
And it wages across your phones,
8
23735
2162
00:37
your computers
9
25921
1176
00:39
and the internet.
10
27121
1169
00:41
Our job is to create systems that scramble
your emails and credit card numbers,
11
29299
4979
00:46
your phone calls and text messages --
12
34302
2259
00:48
and that includes those saucy selfies --
13
36585
2192
00:50
(Laughter)
14
38801
1222
00:52
so that all of this information
can only be descrambled
15
40047
2753
00:54
by the recipient that it's intended for.
16
42824
2121
00:58
Now, until very recently,
17
46017
2313
01:00
we thought we'd won this war for good.
18
48354
2555
01:03
Right now, each of your smartphones
is using encryption
19
51694
2945
01:06
that we thought was unbreakable
and that was going to remain that way.
20
54663
3700
01:11
We were wrong,
21
59654
1940
01:13
because quantum computers are coming,
22
61618
2386
01:16
and they're going to change
the game completely.
23
64028
2790
01:20
Throughout history,
cryptography and code-breaking
24
68445
2456
01:22
has always been this game
of cat and mouse.
25
70925
2070
01:25
Back in the 1500s,
26
73598
1677
01:27
Queen Mary of the Scots thought
she was sending encrypted letters
27
75299
3179
01:30
that only her soldiers could decipher.
28
78502
1977
01:33
But Queen Elizabeth of England,
29
81074
2046
01:35
she had code breakers
that were all over it.
30
83144
2400
01:38
They decrypted Mary's letters,
31
86116
2005
01:40
saw that she was attempting
to assassinate Elizabeth
32
88145
3173
01:43
and, subsequently,
they chopped Mary's head off.
33
91342
2431
01:47
A few centuries later, in World War II,
34
95729
2352
01:50
the Nazis communicated
using the Engima code,
35
98987
2884
01:53
a much more complicated encryption scheme
that they thought was unbreakable.
36
101895
3641
01:58
But then good old Alan Turing,
37
106274
1930
02:00
the same guy who invented
what we now call the modern computer,
38
108228
3035
02:03
he built a machine and used it
to break Enigma.
39
111287
2615
02:06
He deciphered the German messages
40
114545
1605
02:08
and helped to bring Hitler
and his Third Reich to a halt.
41
116174
2715
02:11
And so the story has gone
throughout the centuries.
42
119772
2559
02:14
Cryptographers improve their encryption,
43
122821
2502
02:17
and then code breakers fight back
and they find a way to break it.
44
125347
3138
02:20
This war's gone back and forth,
and it's been pretty neck and neck.
45
128969
3387
02:25
That was until the 1970s,
46
133533
2715
02:28
when some cryptographers
made a huge breakthrough.
47
136272
2660
02:31
They discovered an extremely
powerful way to do encryption
48
139781
3561
02:35
called "public-key cryptography."
49
143366
1752
02:37
Unlike all of the prior methods used
throughout history, it doesn't require
50
145839
4275
02:42
that the two parties that want to send
each other confidential information
51
150138
3607
02:45
have exchanged the secret key beforehand.
52
153769
2059
02:48
The magic of public-key cryptography
is that it allows us to connect securely
53
156602
4112
02:52
with anyone in the world,
54
160738
1544
02:55
whether we've exchanged
data before or not,
55
163481
2869
02:58
and to do it so fast that you and I
don't even realize it's happening.
56
166374
3662
03:03
Whether you're texting your mate
to catch up for a beer,
57
171001
3238
03:06
or you're a bank that's transferring
billions of dollars to another bank,
58
174263
4247
03:10
modern encryption enables us
to send data that can be secured
59
178534
3051
03:13
in a matter of milliseconds.
60
181609
2021
03:17
The brilliant idea that makes
this magic possible,
61
185502
2882
03:20
it relies on hard mathematical problems.
62
188408
2527
03:23
Cryptographers are deeply interested
in things that calculators can't do.
63
191623
3834
03:29
For example, calculators can multiply
any two numbers you like,
64
197250
3401
03:32
no matter how big the size.
65
200675
1686
03:35
But going back the other way --
66
203175
1941
03:37
starting with the product and then asking,
67
205140
2218
03:39
"Which two numbers multiply
to give this one?" --
68
207382
2365
03:41
that's actually a really hard problem.
69
209771
2381
03:45
If I asked you to find which two-digit
numbers multiply to give 851,
70
213358
4591
03:51
even with a calculator,
71
219051
1192
03:52
most people in this room would have
a hard time finding the answer
72
220267
3107
03:55
by the time I'm finished with this talk.
73
223398
1916
03:57
And if I make the numbers a little larger,
74
225338
2661
04:00
then there's no calculator on earth
that can do this.
75
228023
3657
04:03
In fact, even the world's
fastest supercomputer
76
231704
2883
04:06
would take longer
than the life age of the universe
77
234611
2490
04:09
to find the two numbers
that multiply to give this one.
78
237125
2872
04:13
And this problem,
called "integer factorization,"
79
241029
3341
04:16
is exactly what each of your smartphones
and laptops is using right now
80
244394
3626
04:20
to keep your data secure.
81
248044
1534
04:22
This is the basis of modern encryption.
82
250254
2417
04:26
And the fact that all the computing power
on the planet combined can't solve it,
83
254266
4210
04:30
that's the reason we cryptographers
thought we'd found a way
84
258500
2873
04:33
to stay ahead of the code
breakers for good.
85
261397
2258
04:37
Perhaps we got a little cocky
86
265131
1652
04:39
because just when we thought
the war was won,
87
267902
2346
04:42
a bunch of 20th-century physicists
came to the party,
88
270272
2938
04:45
and they revealed
that the laws of the universe,
89
273234
2679
04:47
the same laws that modern
cryptography was built upon,
90
275937
2595
04:51
they aren't as we thought they were.
91
279422
1815
04:54
We thought that one object couldn't be
in two places at the same time.
92
282205
3511
04:58
It's not the case.
93
286262
1541
04:59
We thought nothing can possibly spin
clockwise and anticlockwise
94
287827
3712
05:03
simultaneously.
95
291563
1285
05:05
But that's incorrect.
96
293265
1387
05:07
And we thought that two objects
on opposite sides of the universe,
97
295173
3710
05:10
light years away from each other,
98
298907
2301
05:13
they can't possibly influence
one another instantaneously.
99
301232
3566
05:17
We were wrong again.
100
305932
1247
05:20
And isn't that always the way
life seems to go?
101
308403
2209
05:22
Just when you think you've got
everything covered, your ducks in a row,
102
310636
3396
05:26
a bunch of physicists come along
103
314056
1555
05:27
and reveal that the fundamental laws
of the universe are completely different
104
315635
3692
05:31
to what you thought?
105
319351
1161
05:32
(Laughter)
106
320536
1058
05:33
And it screws everything up.
107
321618
1356
05:34
See, in the teeny tiny subatomic realm,
108
322998
4526
05:39
at the level of electrons and protons,
109
327548
3012
05:42
the classical laws of physics,
110
330584
1822
05:44
the ones that we all know and love,
111
332430
1840
05:46
they go out the window.
112
334294
1238
05:48
And it's here that the laws
of quantum mechanics kick in.
113
336023
2811
05:51
In quantum mechanics,
114
339688
1186
05:52
an electron can be spinning clockwise
and anticlockwise at the same time,
115
340898
4478
05:57
and a proton can be in two places at once.
116
345400
2564
06:01
It sounds like science fiction,
117
349940
2123
06:04
but that's only because
the crazy quantum nature of our universe,
118
352087
4195
06:08
it hides itself from us.
119
356306
1671
06:10
And it stayed hidden from us
until the 20th century.
120
358884
3292
06:15
But now that we've seen it,
the whole world is in an arms race
121
363494
3769
06:19
to try to build a quantum computer --
122
367287
2276
06:22
a computer that can harness the power
of this weird and wacky quantum behavior.
123
370455
4339
06:28
These things are so revolutionary
124
376375
2456
06:30
and so powerful
125
378855
1766
06:32
that they'll make today's
fastest supercomputer
126
380645
2353
06:35
look useless in comparison.
127
383022
2080
06:37
In fact, for certain problems
that are of great interest to us,
128
385868
3018
06:41
today's fastest supercomputer
is closer to an abacus
129
389633
2611
06:44
than to a quantum computer.
130
392268
1675
06:45
That's right, I'm talking about
those little wooden things with the beads.
131
393967
3536
06:50
Quantum computers can simulate
chemical and biological processes
132
398477
4268
06:54
that are far beyond the reach
of our classical computers.
133
402769
2906
06:58
And as such, they promise to help us solve
some of our planet's biggest problems.
134
406812
5591
07:05
They're going to help us
combat global hunger;
135
413492
2272
07:09
to tackle climate change;
136
417074
2317
07:11
to find cures for diseases and pandemics
for which we've so far been unsuccessful;
137
419415
3960
07:16
to create superhuman
artificial intelligence;
138
424213
2909
07:20
and perhaps even more important
than all of those things,
139
428034
2904
07:22
they're going to help us understand
the very nature of our universe.
140
430962
3726
07:28
But with this incredible potential
141
436376
2214
07:31
comes an incredible risk.
142
439788
1631
07:34
Remember those big numbers
I talked about earlier?
143
442785
2384
07:38
I'm not talking about 851.
144
446152
2099
07:40
In fact, if anyone in here
has been distracted
145
448275
2181
07:42
trying to find those factors,
146
450480
1439
07:43
I'm going to put you out of your misery
and tell you that it's 23 times 37.
147
451943
3554
07:47
(Laughter)
148
455521
1194
07:48
I'm talking about the much
bigger number that followed it.
149
456739
2735
07:52
While today's fastest supercomputer
couldn't find those factors
150
460300
3500
07:55
in the life age of the universe,
151
463824
2333
07:58
a quantum computer
could easily factorize numbers
152
466181
2880
08:01
way, way bigger than that one.
153
469085
1567
08:03
Quantum computers will break
all of the encryption currently used
154
471882
3410
08:07
to protect you and I from hackers.
155
475316
1978
08:09
And they'll do it easily.
156
477318
1427
08:12
Let me put it this way:
157
480539
1333
08:13
if quantum computing was a spear,
158
481896
1770
08:16
then modern encryption,
159
484666
1535
08:18
the same unbreakable system
that's protected us for decades,
160
486225
3373
08:21
it would be like a shield
made of tissue paper.
161
489622
2658
08:25
Anyone with access to a quantum computer
will have the master key
162
493578
3988
08:29
to unlock anything they like
in our digital world.
163
497590
2688
08:33
They could steal money from banks
164
501293
1812
08:35
and control economies.
165
503129
1431
08:37
They could power off hospitals
or launch nukes.
166
505303
2897
08:40
Or they could just sit back
and watch all of us on our webcams
167
508224
3337
08:43
without any of us knowing
that this is happening.
168
511585
2358
08:49
Now, the fundamental unit of information
on all of the computers we're used to,
169
517314
3959
08:53
like this one,
170
521297
1505
08:54
it's called a "bit."
171
522826
1342
08:56
A single bit can be one of two states:
172
524651
2223
08:58
it can be a zero or it can be a one.
173
526898
2259
09:02
When I FaceTime my mum
from the other side of the world --
174
530157
2828
09:05
and she's going to kill
me for having this slide --
175
533746
2486
09:08
(Laughter)
176
536256
1395
09:09
we're actually just sending each other
long sequences of zeroes and ones
177
537675
3734
09:13
that bounce from computer to computer,
from satellite to satellite,
178
541433
3202
09:16
transmitting our data at a rapid pace.
179
544659
2146
09:18
Bits are certainly very useful.
180
546829
2003
09:20
In fact, anything
we currently do with technology
181
548856
2696
09:23
is indebted to the usefulness of bits.
182
551576
2062
09:26
But we're starting to realize
183
554840
1389
09:28
that bits are really poor at simulating
complex molecules and particles.
184
556253
4515
09:33
And this is because, in some sense,
185
561394
1976
09:35
subatomic processes can be doing
two or more opposing things
186
563394
3085
09:38
at the same time
187
566503
1188
09:39
as they follow these bizarre rules
of quantum mechanics.
188
567715
2986
09:43
So, late last century,
189
571232
1544
09:44
some really brainy physicists
had this ingenious idea:
190
572800
3217
09:48
to instead build computers
that are founded
191
576041
2001
09:50
on the principles of quantum mechanics.
192
578066
2090
09:54
Now, the fundamental unit of information
of a quantum computer,
193
582557
3219
09:57
it's called a "qubit."
194
585800
1248
09:59
It stands for "quantum bit."
195
587582
1800
10:02
Instead of having just two states,
like zero or one,
196
590986
3257
10:06
a qubit can be an infinite
number of states.
197
594267
2889
10:09
And this corresponds to it being
some combination of both zero and one
198
597849
3666
10:13
at the same time,
199
601539
1787
10:15
a phenomenon that we call "superposition."
200
603350
2189
10:18
And when we have two qubits
in superposition,
201
606569
2705
10:21
we're actually working across
all four combinations
202
609298
2382
10:23
of zero-zero, zero-one,
one-zero and one-one.
203
611704
2510
10:26
With three qubits,
204
614940
1346
10:28
we're working in superposition
across eight combinations,
205
616310
3241
10:31
and so on.
206
619575
1152
10:33
Each time we add a single qubit,
we double the number of combinations
207
621294
3950
10:37
that we can work with in superposition
208
625268
3602
10:40
at the same time.
209
628894
1179
10:43
And so when we scale up
to work with many qubits,
210
631005
2629
10:45
we can work with an exponential
number of combinations
211
633658
3622
10:49
at the same time.
212
637304
1319
10:51
And this just hints at where the power
of quantum computing is coming from.
213
639440
3635
10:56
Now, in modern encryption,
214
644964
1327
10:59
our secret keys, like the two factors
of that larger number,
215
647429
3928
11:03
they're just long sequences
of zeroes and ones.
216
651381
2277
11:06
To find them,
217
654539
1244
11:07
a classical computer must go through
every single combination,
218
655807
4444
11:12
one after the other,
219
660275
1151
11:13
until it finds the one that works
and breaks our encryption.
220
661450
3079
11:18
But on a quantum computer,
221
666191
1548
11:20
with enough qubits in superposition,
222
668779
3193
11:25
information can be extracted
from all combinations at the same time.
223
673001
4331
11:30
In very few steps,
224
678912
1254
11:32
a quantum computer can brush aside
all of the incorrect combinations,
225
680190
3974
11:36
home in on the correct one
226
684188
1413
11:37
and then unlock our treasured secrets.
227
685625
2061
11:44
Now, at the crazy quantum level,
228
692215
2566
11:47
something truly incredible
is happening here.
229
695900
2622
11:52
The conventional wisdom
held by many leading physicists --
230
700625
3674
11:56
and you've got to stay
with me on this one --
231
704323
2619
11:58
is that each combination is actually
examined by its very own quantum computer
232
706966
4423
12:03
inside its very own parallel universe.
233
711413
2549
12:07
Each of these combinations,
they add up like waves in a pool of water.
234
715303
3901
12:12
The combinations that are wrong,
235
720085
1986
12:14
they cancel each other out.
236
722095
1978
12:16
And the combinations that are right,
237
724097
1760
12:17
they reinforce and amplify each other.
238
725881
1859
12:20
So at the end of the quantum
computing program,
239
728241
2665
12:22
all that's left is the correct answer,
240
730930
2817
12:25
that we can then observe
here in this universe.
241
733771
2553
12:29
Now, if that doesn't make
complete sense to you, don't stress.
242
737575
3136
12:32
(Laughter)
243
740735
1048
12:33
You're in good company.
244
741807
1223
12:36
Niels Bohr, one of
the pioneers of this field,
245
744205
3166
12:39
he once said that anyone
who could contemplate quantum mechanics
246
747395
3007
12:42
without being profoundly shocked,
247
750426
2363
12:44
they haven't understood it.
248
752813
1456
12:46
(Laughter)
249
754293
1427
12:47
But you get an idea
of what we're up against,
250
755744
2155
12:49
and why it's now up to us cryptographers
251
757923
2062
12:52
to really step it up.
252
760009
1363
12:54
And we have to do it fast,
253
762674
2089
12:56
because quantum computers,
254
764787
2032
12:58
they already exist in labs
all over the world.
255
766843
3023
13:03
Fortunately, at this minute,
256
771248
1897
13:05
they only exist
at a relatively small scale,
257
773169
2670
13:07
still too small to break
our much larger cryptographic keys.
258
775863
3065
13:12
But we might not be safe for long.
259
780127
1684
13:14
Some folks believe that secret
government agencies
260
782968
2496
13:17
have already built a big enough one,
261
785488
1913
13:19
and they just haven't told anyone yet.
262
787425
1973
13:21
Some pundits say
they're more like 10 years off.
263
789961
2429
13:24
Some people say it's more like 30.
264
792414
1860
13:27
You might think that
if quantum computers are 10 years away,
265
795163
2857
13:30
surely that's enough time
for us cryptographers to figure it out
266
798044
3064
13:33
and to secure the internet in time.
267
801132
1694
13:34
But unfortunately, it's not that easy.
268
802850
1887
13:37
Even if we ignore
the many years that it takes
269
805521
2188
13:39
to standardize and deploy and then
roll out new encryption technology,
270
807733
3666
13:43
in some ways we may already be too late.
271
811423
2328
13:47
Smart digital criminals
and government agencies
272
815407
3172
13:50
may already be storing
our most sensitive encrypted data
273
818603
4279
13:54
in anticipation for
the quantum future ahead.
274
822906
2593
13:59
The messages of foreign leaders,
275
827069
1738
14:02
of war generals
276
830100
1355
14:04
or of individuals who question power,
277
832653
2162
14:07
they're encrypted for now.
278
835936
1550
14:10
But as soon as the day comes
279
838487
1601
14:12
that someone gets their hands
on a quantum computer,
280
840112
2776
14:14
they can retroactively break
anything from the past.
281
842912
3126
14:19
In certain government
and financial sectors
282
847078
2030
14:21
or in military organizations,
283
849132
1403
14:22
sensitive data has got to remain
classified for 25 years.
284
850559
3074
14:26
So if a quantum computer
really will exist in 10 years,
285
854273
3180
14:29
then these guys are already
15 years too late
286
857477
2290
14:31
to quantum-proof their encryption.
287
859791
1710
14:34
So while many scientists around the world
288
862858
1976
14:36
are racing to try to build
a quantum computer,
289
864858
2903
14:39
us cryptographers are urgently
looking to reinvent encryption
290
867785
3450
14:43
to protect us long before that day comes.
291
871259
2202
14:46
We're looking for new,
hard mathematical problems.
292
874718
2974
14:50
We're looking for problems that,
just like factorization,
293
878435
3011
14:53
can be used on our smartphones
and on our laptops today.
294
881470
3009
14:57
But unlike factorization,
we need these problems to be so hard
295
885596
4375
15:01
that they're even unbreakable
with a quantum computer.
296
889995
2846
15:06
In recent years, we've been digging around
a much wider realm of mathematics
297
894366
3606
15:09
to look for such problems.
298
897996
1526
15:12
We've been looking at numbers and objects
299
900205
1971
15:14
that are far more exotic
and far more abstract
300
902200
2168
15:16
than the ones that you and I are used to,
301
904392
1956
15:18
like the ones on our calculators.
302
906372
1597
15:19
And we believe we've found
some geometric problems
303
907993
2380
15:22
that just might do the trick.
304
910397
1399
15:24
Now, unlike those two-
and three-dimensional geometric problems
305
912383
3063
15:27
that we used to have to try to solve
with pen and graph paper in high school,
306
915470
3699
15:31
most of these problems are defined
in well over 500 dimensions.
307
919193
4229
15:36
So not only are they a little hard
to depict and solve on graph paper,
308
924453
3756
15:40
but we believe they're even
out of the reach of a quantum computer.
309
928233
3472
15:45
So though it's early days,
310
933392
1697
15:47
it's here that we are putting our hope
as we try to secure our digital world
311
935113
4505
15:51
moving into its quantum future.
312
939642
1970
15:55
Just like all of the other scientists,
313
943171
1853
15:57
we cryptographers are tremendously excited
314
945048
2163
15:59
at the potential of living in a world
alongside quantum computers.
315
947235
3857
16:04
They could be such a force for good.
316
952839
2153
16:09
But no matter what
technological future we live in,
317
957508
4248
16:16
our secrets will always be
a part of our humanity.
318
964867
4856
16:22
And that is worth protecting.
319
970637
2234
16:25
Thanks.
320
973559
1154
16:26
(Applause)
321
974737
3106
Translated by Joseph Geni
Reviewed by Camille Martínez

▲Back to top

ABOUT THE SPEAKER
Craig Costello - Cryptographer
Craig Costello uses mathematics to secure the digital world, both against the threats that exist today and those that may exist in the future.

Why you should listen
Together with his colleagues, Craig Costello builds software with the goal of safeguarding the internet before large-scale quantum computing becomes a reality. He is a senior researcher in the Cryptography and Security Group at Microsoft Research in the USA. He is primarily interested in the cryptographic applications of computational number theory, in particular curve-, pairing- and lattice-based cryptography.
More profile about the speaker
Craig Costello | Speaker | TED.com