We have Alice, we have Bob. And Alice wants
to talk to Bob, but they don't want to be
eavesdropped on by Eve. These are the technical
terms by the way. So, what should Alice do?
She can't just talk to Bob and say, "Hey,
what's up Bob?". No, she doesn't want Eve
to know that she's asking Bob what's up. So,
what she could do is, she could encrypt her
message and say *zybdguey* and then Eve would
be like, "What the heck?". And this is exactly
the ciphertext as we call it. So she wants
to send her message m, so she kinda encrypts
it, and then sends it to Bob and Bob can somehow
decrypt it. And we talk about these three
things: the message, this is the plaintext.
We have c, and this is the ciphertext, and
then we have a key, k, which is used in order
to encrypt this message. I will get into how
that functions but this is the basic setup.
And Eve doesn't have to necessarily be an
eavesdropper but can be active (I'll get into
that). Before we get that done, I'd just like
to talk a little bit about "Bits", because
I am not sure everyone knows what they are.
So, bits are basically 0s and 1s. These are
basically the things that computers they work
with and we have a "string" of bits, or "bitstring".
Could be 10110...1 and if this is n then there
are n of these. We have something called the
"bitwise exclusive-or". Which we also call,
well we write it like this, but we also call
it XOR. I am just going to call it that. And
basically, the way that it works is that we
have four possibilities: 0 XOR 0 = 0, 0 XOR
1 = 1, 1 XOR 0 = 1, and 1 XOR 1 = 0. For those
of you who have had some Algebra and so on,
you might know that this is simply "modulo
2", yeah? Addition modulo 2. So that's what
we basically use and if we have two bitstrings
and we want to XOR them then we do it bitwise
and then get something out of it. Ok, so,
(oh my bag), let's look at some classic cryptography.
This is the stuff that they used to do, in
order to encrypt their messages. Particularly,
Caesar had this one that we call the Caesar
shift, and basically it works like this: You
take the entire alphabet, and you shift it
by your key, in this case, I'm taking my key
to be 3, and so I am shifting my entire alphabet.
So A gets sent to D, B gets sent to E, and
so on and so forth, and it wraps around so
Z gets sent to C. If we want to encrypt the
message "BEGINTHEATTACKNOW", then B gets sent
to E, E gets sent to H, and so on and so forth.
And we have this message. This we can send
off and then decryption, basically you shift
your entire alphabet backwards by 3. So now,
D will get sent to A, E will get sent to B,
C will get sent to Z, and so on and so forth.
And we basically have the original message.
Ok, what's the downside? Well this can be
brute-forced. We can simply check all the
keys. There are only 26 of them, or, 27 of
them, in English, and in Latin it wasn't a
problem either, but back then, very few people
actually knew how to read and write, so then
it was kind of secure, because it was secure
through obscurity. Nowadays, we don't have
that luxury, pretty much everyone knows how
to read and write and, yeah, you can brute-force
it, as I was saying, in polynomial time. Polynomial
time, basically, means that we can write up
a polynomial and that's the amount of steps
for a message of length n, then it has p(n)
many steps in the algorithm which can be used
to decrypt it, or break it. There are different
variations of this: Something called substitution
ciphers where instead of using the alphabet,
we kinda write the message and then underneath,
we kinda write a word and just repeat it and
then we shift in some way. But the matter
of fact is it's still, we use the same words,
so we can break it in polynomial time, just
by brute-force. All the classical ones can
be broken by brute-force. So then the question
came up: What can we do to have something
be secure? Well, is it enough to say that
it should be impossible to recover the key?
Is it enough to say that it should be impossible
to recover entire plaintext? Or is it enough
just to say, "Well, as long as they don't
get, you know, as long as they only get a
little bit of it, that's fine, we'll still
have some kind of security because they don't
know everything we're saying." Well this is
a problem if it's a bit which kinda says whether
it's a thousand dollars or ten thousand dollars
you're sending to the bank, that's the kind
of information that you would not like them
to know. And what about additional information?
For example, you have the Enigma machine,
which pretty much everyone has heard of, that
the Nazi's used during WWII. It was an actual
machine, in order to encrypt and decrypt.
So basically, if you just got your hands on
that thing, you could basically decrypt it.
Or figure out how the encryption scheme worked.
That's pretty much what they did. We also
think, "Well what are the different scenarios
that we might have?" Like, what kind of adversary
are we against? Is it the one that only sees
our ciphertext? Is it one that knows what
Alice might want to send? m_0 and m_1 are
only two choices so it gets c out and it has
to determine which one it is. Or is it chosen-plaintext
in the way that Eve, or the adversary, can
tell A to encrypt m' and then checks what
comes out? Let give you a practical example.
Also during WWII, the Americans had kinda
broken the entire encryption scheme of the
Japanese. Except they didn't know how they
coded base names and names in general. So
basically, they got this message saying "Oh,
we're going to attack A very soon" and they
were like, "what the heck is A? We don't know
what A is". But they kinda traced it down
to three different bases and they were like,
"It's gotta be one of these so let's say that
Midway has water problems, the other one has
sanitation problems, and the third one is
missing bug repellent" or something. Then
they put those rumors out there and soon they
got a message, that they decrypted saying,
"A has water problems", so then they were
like, "Aha! Midway". So these are actual scenarios,
that we could have, you know? You might not
be able to directly encrypt something, but
you might be able to get Alice to encrypt
something for you, or trick her. Now, there's
also chosen-ciphertext, where you can actually
influence her to decrypt a ciphertext and
also show you what the message was. But I
don't have a rational argument for that one,
well, I haven't thought about it. Anyways,
this is the kernel of it, we need to actually
say what is an "encryption scheme", and when
is it something called "perfectly secret".
This is like the best way we can get something
secret. No one's ever going to break it, except
for God, but he already knows what the message
is. Everyone else can just go F themselves,
because there's no way they're gonna break
it. And I'll get into what it means to not
be able to break it. But let's see. So we
define an encryption scheme to be this Pi,
using these three algorithms: Generator, Encryption,
and Decryption. And we start with the message
space M and this is the message space of all
possible messages. So think, every combination
of words in the English dictionary. And we
kinda say it has to be strictly greater than
1, because if there's only one message, there's
not really anything to work on, you can kinda
guess the message. We have a key generation
algorithm, Gen, and it has to be a "probabilistic"
algorithm. We say probabilistic because if
it's deterministic, I can always figure out
what the key is going to be. The key needs
to be random, so to speak. It doesn't need
to be uniformly random, but we usually suppose
that. It's easier to work with and it does
some better things. Question from audience:
"What does uniformly mean?" That means that
each key is distributed with the same probability,
so if we have the bitstrings of length n,
then each message has the probability 1/2^n,
or each message has the same probability.
And then we take the encryption algorithm.
It takes k, and we affix it as an index, because
it needs to be fixed to the entirety of the
duration of the use of this encryption scheme
to talk between two people. And then encrypt
a message m, and we call this our ciphertext,
c. Then we also have the decryption algorithm,
again using the same key, but on some random
ciphertext, and (then get) m. There is a point
in the fact that these are definitely either
c or m, and this is definitely in the message
space or in the ciphertext space, because
we have something that we call perfect correctness.
Perfect correctness simply states that,
we have a kinda bijective correspondence here,
so that if I decrypt using the key k, on some
kind of encryption, also using the key k,
then this is going to give me the message
m, everytime. Later we have that the ciphertext
space could be larger, so then we don't necessarily
have the same thing, but I'll get into that
when we get to it. So with probability 1,
basically this always happens. Now let's get
to: what does it actually mean to be secret?
We've only defined an encryption scheme, now
we're defining what "perfectly secret" is.
Without getting too much into what it says,
we're saying, for every message m, and every
ciphertext c, this is a technicality, we have
that the probability distribution of us getting
a message m, when we have a ciphertext c,
is going to be equal to the probability that
the message is m. Basically that the ciphertext
and the message, or plaintext, are going to
be independent of each other. You can think
of it in the way that if the probability that
the message m is a die, so, this being 1,
well this doesn't impact if I have another
die, that we roll at the same time, and I
get 2 here, that this is necessarily connected.
No, they're two different die, why would they
be connected. Of course, there is this whole
encryption thing, so there is some connection,
but it should still seem like there isn't.
That is what this secrecy says, the perfect
secrecy. We have this experiment. Right now,
I've just given you this definition but how
do we prove this? How do we actually know
when something satisfies this? Well, we have
another definition. Lots of those in this
subject. Basically, we have an experiment.
We love running experiments and these experiments
are kind of "thought" experiments. Because
we say, we kind of idealize, we say, in
the best of conditions for the adversary,
what's the chance that he wins, that he can
guess which message he's sending? What we
do is, we simply let (I'm going to write it
up here in the bottom) We let the adversary
choose two message, how? No one knows, except
for him. They have to be the same length,
because otherwise it's going to be very easy
to distinguish between ciphertexts *automatic
curtains start rolling up* and then he basically
sends them to Alice, or us. We're playing
Alice's part in this case, because we kinda
wanna show that he can't break it. So Alice,
what she does is, she gets a random bit b,
which we would also sometimes denote like
this, it's a random element of 0 and 1. So
each have probability 1/2 and then she simply
chooses to encrypt, using her secret key,
which he doesn't know about, or the adversary
doesn't know about, m_b. So each of these
has 50% (Can someone close the window, Adrien,
could you roll down the blinds please? Thank
you) So each of these has 50% chance of being
encrypted, perfectly encrypted, alright? So
then, this is the c the adversary gets and
he basically has to say ... he has to output
some bit b' and if b'=b then he wins,
if b' \neq b, then he loses.
Exactly when the possibility
of him getting this right, versus the possibility
of him getting it wrong, is exactly 1/2, then
we have "perfectly indistinguishable". This
basically means that he is not able to distinguish
between encryption of m_0 and encryption of
m_1, which is what we want. Because we want
the ciphertext, the encryption, we want those
to be secret. We want him not to be able to
say which one we've sent. This is idealized,
but this is in essence what every single form
of security that we might cook up actually
boils down to. We have a lemma that gives
us that an encryption scheme is perfectly
secret if and only if it satisfies this probability.
We have an example, which is the one-time
pad: We have a message in bitstrings of length
n and you XOR it with bitstring, a random
bitstring, which is the key, of length n,
or greater. And then the product of the two,
or the sum, the XOR of the two, is going to
be perfectly distributed. Because the first
bitstring might not be random, but the second
one is, so you're XOR'ing with something random,
you get something random. Why is it called
the one-time pad? Because XOR is really stupid
and if we use the same key twice, we can just
XOR the two ciphertexts and the keys disappear,
and then we have something non-random and
we're gonna have a problem.  *Audience gets it*
It's called the one-time pad because
you can only use it once. We also have Shannon,
and Shannon's Theorem basically states that,
well, if you want perfectly secret, you're
gonna have a key space which has to be greater
than or equal to the message space. And this
is a problem, because you need random strings?
Those are kind of difficult to procure and
they're really expensive to make actually,
and if you have a large message, you're gonna
need a large key. So, that's a problem. So
we've kinda tried to find out, what else can
we do? Can we skip the perfect and make it,
you know, almost perfect? So we tried to relax
our secrecy. We have Kerckhoffs Principle,
and this is the guy that really... it's thanks
to him that we even started thinking of other
notions of secrecy than the classical, but
I am just bringing it here. He says: Everything
about the encryption scheme must be known.
Everything. Except for the key! The key should
be the only secret thing because you can lock
that up and keep it, but everything else could
be leaked, and it should still be secure.
This is really powerful. But at the same time,
he also says, let's only make it efficient
adversaries, because otherwise, they could
just check all possible keys and then they
could break it anyway. "Efficient" means polynomial
time, which means that whichever algorithm
we use to instantiate it, is going to be in
polynomially many steps. Quantum computers
don't have that problem, they're exponential.
So polynomial time is what we're talking about here.
And we want to say that they succeed
with only negligible probability.
"Negligible probability" is a function on n, which 1/p(n)
for some polynomial on n. So when I say negligible,
just think very small according to n. That's
basically what I've written there.
What about "private-key encryption schemes"? This is
analogous to what we had before, but that
was perfectly secret. Here we have private
key, so we need to relax a few things. But
it is more or less the same thing. We're still
gonna need a key generation algorithm, which
is random. We're still going to have that
k > n, where n is some "security parameter"
(Not going to get into that) The encryption
algorithm is still going to take a message,
and some key, do some stuff with it, and outputs
c. We also usually say that it has to be random,
or probabilistic, otherwise we can kind of
just compute all the possible things. But
the decryption algorithm is going to be deterministic,
and here you see we also have this "error",
and that is because we don't suppose the message
space and the ciphertext space have the same
length (size), so we could have some ciphertexts
that simply don't decrypt. That don't have
any message corresponding to it. What we do
say is that for every message, which we can
encrypt obviously, if we were to decrypt it,
we get m again. So it is still "correctness",
it's just not perfect correctness. It doesn't
exist for every ciphertext. This is the corresponding
experiment, it's the exact same. We have two
messages of equal length, again. We generate
a key and this random bit (I write uniform,
so it is random) and ciphertext is computed,
same thing. Same experiment and we also say
that A succeeds and loses in the same cases.
But here, here is where it differs. "Indistinguishable
encryptions in the presence of an eavesdropper"
(EAV-secure), we have a lot of shorthand,
then if you noticed here, we say that, first
of all, we have polynomial time adversaries,
probabilistic polynomial time adversaries.
Basically, the polynomial time is to say its
efficient and the probabilistic is to say
that it is allowed to guess. And it might
guess correctly on the first guess, who knows?
But it is a very slight possibility. What
we say is that the success probability is
going to be less that a half, remember that
before it was equal to a half, plus a negligible
probability. So it's slightly worse than before
but not a problematic amount worse.
This is a wall-of-text, I am going to explain this
wall-of-text now. This is the greatest tool
that we have, well one of them, we also have
something called a hybrid argument.
"Proofs by reduction", this is how we prove things
in cryptography, for the most part.
Basically, it is a contradiction proof, but it relies
on something that most mathematicians in here
would say is "really shaky" and "please don't
do that". Which is, we use something which
is unproven, in order to prove this. Let me
try and explain how that works. I am going
to draw a picture, because that is an easier
way to do this. We start by having some encryption
scheme. We have a generator, an encryption,
we have decryption. We want to prove that
this is secure. How do we do that? Well, we
take a problem X, which is "hard", and then
we make a reduction. Let me just explain ""hard"
problem". In cryptography, it means that a
lot of people have tried to prove/solve/break
it, but they haven't been successful. *Laughter*
And then we are like, "It's probably not going
to be solved, let's just use it." You know,
prime factorization and such things. But of
course quantum computers can totally solve
that. This is also the reason we really believe
that P is not equal to NP because if it were,
there are no more hard problems, and all cryptography
falls apart. Not gonna get into that but you
can ask me later if you want. So what do we
do? We draw a box. We always, we love diagrams
in cryptography. And we say have some distinguisher
D and D wants to solve X, he wants to do the "impossible".
Now D has access to something,
some "oracle", giving him some sort of information,
I don't know what, it depends on the problem.
But whatever he knows about the problem,
he can "talk" to this oracle, which he doesn't
necessarily how works, he actually never knows
how it works, but whenever he sends some element
g, he gets some element f back. He can use
that however he wants and he has queries to
it. But the interesting part is this: Inside
of the distinguisher he has this adversary
A which solves Pi. It simply breaks this encryption
scheme, that we cooked up, with some non-negligible
probability, \epsilon(n). The whole idea is
that D fakes Alice. D simply acts like it
is Alice and simulates an experiment for the
adversary, which the adversary then breaks.
D doesn't know how the adversary works at
all, he just gets a box. You could say that
it's an oracle inside of D. But he is able to
also send some element g and get some element
f. And in some kind of regard, they correspond
as many times as necessary, until the adversary
actually solves (breaks) Pi. Then Pi, if we
run this experiment with m_0 and m_1, then
outputs a bit b' and wins the experiment,
with probability \epsilon(n). Then D, which
has some already determined probability of
winning... just going to write it as... so
this is the probability that A succeeds and
then multiply it on to some negligible function
that says that D is going to solve this (X),
because this is the standard thing. But then
this is going to be non-negligible, because
we assumed \epsilon(n) was non-negligible.
And now we have that D actually solves X with
non-negligible probability, but we assumed
that X was hard, that it couldn't be solved
with non-negligible probability. We get a
contradiction, so Pi must be secure.
And that's basically "Proof by reduction", and you can
make variations on it and write it out, but
this is essentially what it all boils down
to, and once you understand this proof method,
it's so much fun, doing stuff in cryptography.
Audience question: So the contradiction arises when we solve the hard problem? Yes, exactly.
Now the problem then comes that, well, what
if you actually could solve it? Audience question:
So the contradiction that you get, comes from
the assumption that \epsilon(n) is non-negligible?
Yes. A solves Pi with some non-negligible
probability. Audience question: And so this
sort of contradiction proof will give us that
the probability is negligible, the probability of success? Yes, exactly.
I don't know about the time, 43, ok I am going
to try and hurry up. This is basically symmetric
cryptography, well, symmetric-key cryptography,
and we have different variations. We have
Multiple EAV, we have Indistinguishable encryptions
under chosen plaintext, you know, different
sorts of security and it gets stronger and
stronger, because if he can do plaintext and
ciphertext, then the adversary has more to
work with. In any case, we also have something
called "Authentication", or "Verification".
Before we just had encryption, but how do
you know, how does Bob know that he's not
talking to Eve? We need to make sure that
he's not talking to Eve and that's what we
do through authentication and these are the
MACs as we call them. You may have heard of
MAC-addresses in computers. It's basically
to say that you are who you say you are.
It works slightly like encryption. You have this
key, but then you have this tag generation
algorithm. It's also basically a ciphertext,
but not really. And then we a verification
algorithm, instead of a decryption one. Which
says whether, given a message, and given a
tag, whether it is correct, whether it really
is you. Is it really the correct tag which
corresponds to this message?
Audience question: So the tag could be your PIN number, for example?
Yes, in a way it could be, sure, but it's kind
of... Well, it's a PIN number generated by
this exact message. So it pertains only to
that message. If I were to change the message,
the tag changes. I can't just keep using the
tag. The PIN number is a key, essentially.
We also have an experiment, this unforgeability
experiment, the MAC-Forge.
It runs slightly like the encryption-decryption. It succeeds only if it is able to procure a message and
a tag such that the verification algorithm
is correct, with a message that it hasn't
already asked before, because here is the
thing. A has oracle access to the MAC.
So before, we just had that the adversary inputs
these two messages, gets some ciphertext back
and then does some work. But here we add an
oracle, where he doesn't know how it works
but he knows that he's allowed to send messages
m and get tags t back. We therefore assume
that he hasn't already tested m, that he hasn't
already sent m to the oracle because obviously
then he has gotten a tag back which satisfies
the verification, so he hasn't really broken
it. So we guard against that by saying that
m is not something he's already asked before.
Working with oracles is a huge part of cryptography,
especially in these proofs.
We have, again, some kind of "security" definition. Here, it's just negligible, that he basically shouldn't
be able to act like you. I don't find this
super important or impressive (for this talk),
so I am just gonna go to the next thing, which
is our last thing here: Notes on Private-key
cryptography. You can combine encryption and
authentication and get authenticated encryption.
There's also something called hash functions,
where we don't need as large keys, and block
ciphers. And then there's something that I'd
love to talk about, but there's no time. And
this is the stuff that I work with: Pseudorandom
functions. Now we're on to Public-key cryptography,
and this is also called asymmetric-key cryptography
because there are actually two keys. It's
sort of like private-key, except here we have
two keys, a secret key and a public key, there's
focus on this key exchange thing and we still
use "hard" problems, but here it's like number
theoretic problems that are very good to use, like
factoring in RSA. We have dual notions, for
pretty much everything. Secrecy in private-key
is private-key encryption, we have public-key
encryption. Integrity (or this verification/authentication
thing), we have Message Authentication Codes
(MACs) and in public-key, it's Digital Signature
Schemes. So whenever you hear about "Digital
Signatur", in the public debate, then you
know what they're talking about. We have,
again, kind of the same definition of everything,
but then we here have two keys: the public
key and the private key, or secret key. Encryption
algorithm follows the same way, but here I
am going to make sure that you notice that
there is a "random" because it's actually
been proven that if it's not randomized, if
it's not probabilistic, if it's deterministic,
you can easily break it. Always. And that's
a problem because for many years, no one actually
knew that, although I kind of thought it was
pretty obvious. When you see some of the encryption
schemes you will be like, "why did they ever
do that?". There's a lot of stuff on the internet
which is not secure at all against your usual
computer. In any case, here we also have correctness,
and so on and so forth. Here is something
called Diffie-Hellman Key-Exchange. Some of
you have probably seen this in Elementary
Number Theory. This is not encryption, this
is simply a way to get a key across to Bob,
over an authenticated channel, so that I don't
have to give Bob my secret key. This could
be a problem if he's in Canada and I am here
in Denmark, so we only have the internet to
work over, which is authenticated but this
procedure gives us a key that we can share.
I'm gonna maybe just skip this. Basically
it says that we can do some fancy stuff to
get a key across so that no one knows the
secret key, other than ourselves, and Bob
also has his own, but we have a common one
we can use together. Again, we have the indistinguishability experiment.
Again, it's the exact same, which is nice.
We constantly have the same things
that we need to check, the same way to prove things.
But here again, there's a difference,
and that is that the adversary is given the
public key. So eavesdropping indistinguishability
actually gives the adversary an encryption oracle!
He can encrypt messages because all
you have to do is use the public key. This
is the entire brilliance behind the system, it
is that I can give my public key, out on the
internet, I can just put it anywhere. And
then someone can just take their message,
encrypt it using this public key, and send
it to me and then I am the only one who can
read it. But the adversary also has access
to this public key, so he can obviously encrypt
anything he wants. The whole point that we
get to in the secrecy, is that he can't decrypt
it, necessarily easily because of the "hard"
problems. Again, indistinguishable encryption
in the presence of an eavesdropper (Pub-EAV)
and we have the exact same thing: again PPT
adversaries and some negligible function that
exists such that the success probability is
still very close to only 1/2. So yes, this
definition actually gives us CPA security
like I said, you get this Chosen Plaintext
Attack security because he has an oracle where
he can choose his plaintext, encrypt it, and
do whatever he wants to it. This is an example
of an encryption scheme, called El Gamal.
Here, El Gamal uses this randomness in order
to make it so that it's not super easy to
decrypt it. You need this randomness. And
if you look at the proof of security for it,
you'll see why. Other kinds of public key
cryptography that exists is something called
"Learning With Errors", it's very linear algebra
based encryption. It's sort of like using
vectors, shooting them off, and you get to
a point, where you really want to be, but
then you add an error. And now you know what
the error is but no one else does, so whenever
they try to do any calculations with it, in
trying to break it, the error just increases
so they get further and further away from
the true message. Fully homomorphic encryption,
is actually pretty cool, because it's what
Google uses. You can encrypt something, send
it through Google, they can do whatever you
want with it, all the information, without
having any idea what the message is, and then
send it back to you and they've done stuff
to your message that you wanted them to do.
It's kind of weird but it basically allows
you to send secret things and Google doesn't
know anything about it, but they still work
for you. Elliptic Curve cryptography, if you're
into number theory, that would definitely
be the way to go. And then there is Quantum
Cryptography. Now, I am going to differentiate
between two types of Quantum Cryptography:
There's the one where you're actually on Quantum
computers and using Quantum mechanics in order
to encrypt and show that things can't be broken
by other Quantum computers. But there is also
using Classical Cryptography and then proving
that no matter what kind of computer you are,
like Quantum computer or classical, you can't
break it. And that's what I am doing in my
Thesis, so that's fun. Yeah, so Private-key
vs. Public-key. Public-key is very good because
it allows key distribution over public but
authenticated channels. It also reduces the
amount of stored keys because if it were symmetric
or private-key ... I am going to draw a picture.
If this were private-key, then these two would
need to share, these two would need to share,
and they all need to share keys with each other.
Right, so we're summoning the devil when we try to do that *Laughter*
The brilliance
with the public-key is that we can get rid
of everything, and just have this. Which is
nice, just meet in the hub. And everyone stores
a secret key as well. We get quite less key
material, and that's a very good thing. But
it's not as good as using private-key, because
it's a lot slower, because you have to make
sure no one can break this stuff and you have
these two keys. There are more operations
involved so if you can, use private-key.
Yes,
that's pretty much it. If you have any questions?
Audience question: In the beginning, you stated
perfect correctness, which is sort of that
encryption/decryption, given k, are bijections,
with each other as an inverse. Then you defined
correctness where they cancel from the right
but not necessarily from the left because
encryption might not be defined on the. No
encryption is defined on all messages, but
decryption... Audience: ... on all C. But
isn't the second form of correctness always
better than perfect correctness, because you
have some, so to speak, red herrings?
Yes, exactly. You have "noise" or some such. Yes,
but in perfect correctness, you need it otherwise
you don't have this 50-50 chance.
Audience question: So you stated that almost all of the problems, that quantum computers could easily solve them, but isn't...
I didn't quite say that. Some, like RSA; can be broken but
there are still quite a few that we don't know.
Audience: So what is it, quantum computers
can exceed polynomial time, and how do you
sort of guard against something which can utilize
exponential time?
You limit the amount of oracles queries that it can have. This is again the quantum vs classical. So if I'm in a classical
setting and want to guard against quantum
computers, I make sure that their oracle access
is only in a classical sense. They have to
send bits, or bitstrings, or group elements,
or whatever, to the oracle, who then does
all the work and then sends it back. In the
quantum case, it can have a quantum oracle,
which means that it can query things in superposition
and then magic happens and it can actually
query a lot, instead of only polynomially
many things. For example, in my Thesis, I
take the classical case, then I say, you're
only allowed to talk the oracle in the purely
classical sense, and you're only allowed to
ask q things. Audience: And when you say q
things? Polynomially many. Audience question:
You said something like, public-key can only
be secret if you had a probabilistic algorithm.
But isn't RSA secret in the sense that factoring
numbers is a "hard" problem? Yes, but in the
actual encryption algorithm, you use some
randomness. Audience: In RSA? Yes, you should...
I can't be sure right now, but it's an actual
theorem that says it has to be probabilistic,
the encryption scheme. I'll have a look at
RSA and try to point something out.
Audience question: This oracle thing, is still very
mysterious. Can you maybe elaborate, some
sort of, I know mathematicians hate stuff like that, but maybe some real life analogue or something?
Yeah sure... Here it is. The NSA, really
loves to mess around with our computer. What
they do is, they get a ciphertext that Alice
has, and they have access to her computer,
because they put in an actual device, which
allowed them access to it. They can just go
straight through her firewalls and security,
windows logon. But she, came from an outside
source and put in her key, random key, so
they don't know her random key. She put it
into a program which is on her computer, and
then locked it, in some way. Now, the NSA,
they can't see what the key is, that's secure
in this program, but they can use this program.
They can logon to her computer and write some
message and ask it to encrypt it. Now they
have an oracle. Let's also say that the program
is completely locked, they can't access the
program because the people were very clever
and kinda put it in titanium box somehow.
So they use the program, but they don't know
anything about the program. Other than what
it needs as inputs, and outputs. Audience:
So sort of like an end user, who doesn't know
anything about the program, just how to use it? Yeah, exactly. We like to call it Black Box scenario as well.
Audience question: Could you maybe say a few words about this elliptic curve cryptography?
No. *Laughter* I don't
know anything about it, but there will be
a course here in the next block called Elliptic
Curves, with Fabien Pazuki. He has promised
that there will be a part of it, at the end,
in the last week maybe, where they also talk
about elliptic curve cryptography. But I think
it is also in the ElmTal book. Just a little
bit about it. Anything else? Then I would
like to say thank you very much. *Applause*
