https://www.youtube.com/watch?v=PDjAuSAcbY4 The impact of quantum computers in cybersecurity

[Transcribed by Pekka P]

(KYBS2004 course assignment at JYU.FI)

♪ (37C3 intro music) ♪

And with that, I would love it for you to welcome Alessandro and his great talk.

Can everybody hear me okay?

Yes.

Okay.

Okay.

So, quantum computers.

Dear community, dear hackers, it was December of 14 years ago that I attended my first CCC

in Berlin.

And it's also because of that experience and that community that I made a series of

choice that led me here as a researcher studying quantum algorithms and quantum computation.

And there are certain similarities that we can draw between hacking and writing quantum

algorithms.

The idea is that writing quantum algorithms is like hacking nature.

Why?

Well, because we can think of nature as a quantum mechanical system and programming it is like

a way to make nature behave in a way that is not meant to be used.

So, writing quantum algorithms is a lot of fun.

It is a lot of fun in games, but how do I feel today?

Well, today I feel a little bit meh.

Why?

Well, because the impact of quantum computers is not communicated very well in the press today.

There is a lot of hype.

So, we are here today to understand better what's the impact of quantum computers, especially

in cyber security.

So how do we measure impact?

Well, we can say that a new paradigm for doing computation has impact if it's faster than

the classical computers that we have or if it can give us better results, right?

Like imagine we are approximating some solution of a problem like the price of a derivative,

for example, and our quantum computers can give us a better estimate of a price in the

same amount of time of a classical computer.

Or maybe it's just cheaper to compute the same result in the same amount of time.

Another way that we can expect quantum computers to impact our society is if they can

allow us to do something that before we couldn't do, right?

And an example is exponential speedups or big polynomial speedups.

And I know you have in mind Shor's algorithm for factoring.

But it's not that easy, right?

Because we know from high school that asymptotically an exponential function will dominate a polynomial

or linear function.

Imagine that this is the cost of your computation and you can imagine to measure the cost in

hours, okay?

So asymptotically if we have a quantum algorithm that is exponentially or polynomially faster

than a classical algorithm, then we know that it will be faster.

But maybe we have to look at regimes that are relevant for us.

And as you can see from this picture, there are cases where, you know, a linear time algorithm

is slower than an exponential time algorithm, okay?

So how do we measure the cost of quantum computation?

Well, in theoretical computer science, what we do, even for classical computation, we measure

the size of a circuit, right?

And the size of a circuit is basically the number of logical gates that we execute.

Or maybe we can measure the depth of a circuit, that is also known as parallel time.

Or we can measure the space, right?

The number of bits, the size of a memory that we use in our computation.

Or we measure the number of queries that we perform to an oracle.

But we also care about more practical things.

And these practical things are maybe the money that it costs to run some computation, the energy

that I use to run this computation.

And more specifically in quantum circuits, we care about the number of Toffoli gates, which

are a particular kind of three qubit gates.

And we also care, obviously, about the work clock time of our computation and the number

of physical qubit.

So there is a difference between physical and logical qubit.

I won't get into the details of this because it's related to error correction, a very difficult

topic.

But you just have to know that in order to obtain something that we call physical qubit,

we need to, something that we call a logical qubit, we need to use a certain amount of physical

qubit.

And now the ratio is 1 to 1000.

So how do we estimate these more practical and interesting measures?

We do what's called the resource estimation.

And the resource estimation is basically a procedure where we take the theoretical complexity

of an algorithm, we look at the real problem that we have to solve, perhaps we use some

tricks to optimize the circuit, and then we can count the number of resources that we

really need to solve the problem that we care about.

Okay, so what are we going to see today is three topics.

The first, the impact of quantum computing in the cryptography that we use today.

So RSA and LiptevCurveCrypto.

And there the too-long-didn't-read is that there is a long way to go, but we will eventually

get there.

We will see if there is any impact in post-quantum cryptography.

So we will show some research estimation of post-quantum attack on post-quantum cryptography.

And there the result is that lattice-based crypto is safe even when considering practical

implementations of the attacks.

And then we will see the impact of quantum machine learning.

Why?

Because machine learning is used in cybersecurity and we will just try to explore a little bit

this area with methodology.

And the conclusion there, and this is not just in cybersecurity, but is that we will see a

speed-up only for massive datasets.

But we have a lot of good ideas and a lot of hopes.

So in this part, I'm going to present some results of the internship that Adi did in Invariant

with me and Varun and also Antonio joined later this project.

So factoring, right.

The state-of-the-art on factoring is this paper by Craig Gidney.

And basically in this work, he is showing how to break RSA 2048 using 20 million physical

qubits and approximately eight hours of quantum computation.

So he is assuming to work with a particular kind of hardware made of superconducting qubits, with

a gate error of 10 to the minus three.

And he is using concatenated surface code to achieve these estimates, right?

So in order to perform a resource estimation, you have to do some assumption on the hardware

that you expect to have in the future.

What he is using in his circuit is this idea of windowed arithmetic.

So in his circuit, he needs to perform, let me be very technical for five seconds, phase

estimation on an oracle that is performing modular exponentiation.

So basically he needs to perform arithmetic in his circuit.

To perform arithmetic, he is using this idea called windowed arithmetic.

And windowed arithmetic is basically a way to have space-time trade-offs.

So instead of running a circuit that is computing the function that you want to compute, you

pre-compute this function classically and you store some results in memory and you just

query the memory when you run the quantum computation.

And in order to look up the memory at some point, since the computation is quantum and it needs

to be reversible, at some point you need to uncompute some garbage.

And for that, he is also using a trick that allows him to save some gates in these settings.

So our contribution is that we can do some improvements in the way this unlookup is done, especially when

we have nested loops in the circuit.

And in modular exponentiation, you do windowed arithmetic using nested loops.

And therefore, you can have a little bit of saving in the number of gates.

So the performance improvements that we were able to get is around 1% for cryptographic relevant

numbers.

So RSA keys of 2048, basically, 0.7%, is a modest improvement, but it's still non-negligible,

and we hope to do more in the near future.

And it's basically saving 15 minutes over 8 hours.

There is another problem that you face when you're trying to do Shor's algorithm, which

is implementing Boolean functions in general.

So imagine you have a Boolean function.

You can write your classical circuit for implementing this Boolean function.

Using some tricks from classical computer science, you can make this circuit reversible, and then

you can obtain a quantum circuit for this Boolean function.

But again, you will see that you have a problem of performing a computation.

But in literature, we have this thing called measurement based on computation, which allows

you to have savings in expectation when you run the on-computation of the circuit.

And applying this trick to something that we thought was very well analyzed and optimized,

that we realized that you can have savings in the circuit that is performing modular addition.

And where is the circuit for modular addition used?

Well, it's used also in the circuits that are used for breaking elliptic core cryptography.

And here, the state-of-the-art for resource estimation of ACC is this paper by Littinsky.

It's again another corollary of the Shor algorithms.

It's using some particular kind of architecture called active volume, which is assuming basically

to work with photonic qubits with a similar gate error.

And the number of logical qubits that is using is 6,000 logical qubits.

So after our trick, we were able to save, again, a little bit less than 1%, but we have

other tricks under our sleeves to improve this result further.

And the message here is that there is a lot, really, really a lot to do in the whole stack

of quantum computing to improve these attacks and algorithms.

So in the second part, I'm going to present briefly some results of our team at CQTeam, where

me and Joao are super lucky to have Georgios and Aditya helping us studying the resource

estimation of post-quantum cryptography.

So we are focusing on lattice attack, and this is the only math part of this talk, I promise.

So a lattice is basically the set of all integral linear combination of a set of n linearly independent

vectors.

And the problem that you have to solve here is I give you the basis, and you have to find

the shortest vector of this basis.

Shortest vector in, let's say, Euclidean norms.

Why this is important?

Because if you know how to find the shortest vector, then you are able to break post-quantum

cryptography.

Fortunately, we don't have polynomial time algorithms.

We don't have polynomial time quantum algorithms and classical algorithms for solving this problem.

So theoretically, we know that at some point for big lattice dimension, we are safe.

But the question is, are we safe even when we look at the constant factor of the attack

when we implement it?

And there are already works in this direction.

Namely, the first one is studying some version of an algorithm called gauss-siv.

And the second one is implementing and studying enumeration attacks.

So what we did, well, we implemented the gauss-siv.

And here you can find the code online of the attack.

That's great.

But let's look at the results.

So what's the real complexity of the circuit?

Well, from this plot, you see the following thing.

Well, the dotted green line is the cost of the classical algorithm.

And the dotted red line is the cost, the asymptotic cost, the theoretical cost of the quantum algorithm.

The two non-dotted lines are the number of Toffoli gates, a particular kind of gates

in the circuit, and the blue line is the duration in hours.

So you can see that the slope of the two non-dotted lines is compatible with the red dotted lines.

And yes, so it means that we are safe from quantum attacks.

Unless someone finds a new quantum algorithm that is more efficient asymptotically.

And then we have to repeat this study again.

Okay.

In the last part, we study quantum machine learning and applications in cybersecurity.

As I said before, why are we doing this?

Well, because machine learning is ubiquitous in cybersecurity.

And we want to see if quantum has something to say.

So the idea of quantum machine learning is that you want to use a quantum machine for training

a model, so the training part, and or the predict phase of a machine learning algorithm.

Let me say that there are two ways of doing quantum machine learning.

One stems from the theoretical computer science community.

And there you have a theorem stating, I can do this computation with certain probability

and certain approximation error.

And the other community is saying, okay, we have very small devices.

Let's see what we can build on top of those.

And this is very similar to what people are doing in deep learning and with neural networks.

I belong to the first community.

So what I do is I take a classical machine learning algorithm and I try to come up with

a quantum version for it.

And in our work, what we do is we study the query complexity of an algorithm.

Why?

Well, because if we know the number of queries that we do to the input, then we just need

to understand what's the cost of performing a query.

And we know the final cost of performing the whole algorithm.

So this problem is basically reducing to understanding when the left-hand side of this equation is smaller

than the right-hand side.

Let's not delve into the details of the meaning of all these symbols.

But the only important thing here is that on the left-hand side, we don't have n.

And n is the number of samples in our data set.

So there is hope that a quantum algorithm should scale much better than a classical algorithm

in terms of number of samples, right?

But what about the other parameters?

So in order to understand that, we developed this methodology to try to see for data sets

that we care about, what are the parameters in the runtime of a quantum algorithm so we

can compare the runtime with a classical runtime.

So we tested this on a few data sets that are standard in cybersecurity, and the result is that we need 10 to the 7 elements in our data set in order to start to feel a little bit of quantum advantage in terms of query complexity.

So without taking into account the cost of query to the Q-RAM.

Okay.

So maybe there are other data sets and problem that we can look at to get advantage.

And so, well, the answer is there is some hope.

And there is this particular problem that I found many years ago.

And the problem is related to malware detection.

So DGA, domain generation algorithm, is an algorithm that malware is using in order to contact the command and control server.

They are basically generating random domains.

And they are trying to connect to a web server that is answering behind one of these randomly generated domains.

And the randomly generated domains are very different from the domain that we humans generate.

Take, for example, google.com versus randomletters.com.

So I took as a training set the top one million domains.

And I did some pre-computation.

And I obtained an n-gram matrix where the number of rows is one million.

And in the columns you have the n-grams that you built out of the training set.

And in any row you have one if the n-gram in the column you are considering is appearing in the domain in that row.

Okay.

So what's interesting here is that this matrix is very sparse.

And I tell you later why it's interesting.

But then when you build this n-gram matrix with a classical computer, you can only afford to pay linear time to process it.

So you cannot do linear algebra on this matrix on a classical computer.

And my idea was, hey, let's use a quantum algorithm to extract something out of this matrix.

Great.

So I wrote, my first paper was a quantum algorithm for something called slow feature analysis,

which is exactly equivalent to something called fissure linear discriminant.

You might know this.

And so I wrote a classical simulation of a quantum algorithm to extract this feature out of this

very big and very sparse matrix.

And then I used this feature in a classification step.

So the game is the following.

You give me a domain.

I have a classifier, a machine learning classifier.

I use the feature I just extracted from the matrix to add a new input to this classifier.

And I looked at the results.

And I compared the classical results with the quantum results.

And you can see that this feature is improving a little bit the results of a classification.

So the moral of the story is that if you think hard enough, maybe there is some hope to get

quantum advantage in the future.

So conclusions.

Well, the results and the paper that we see nowadays are kind of the following script.

We know how to perform linear algebra.

We find a problem where linear algebra is needed or is a bottleneck.

And we write a quantum algorithm for it.

It's interesting, but maybe we want to understand and we want to get a new algorithmic paradigm

for writing new quantum algorithms.

Different kind of speedups.

A common trend that is limiting the quantum advantage in practice is something called QRAM.

So the quantum version of random access memory.

And there is a lot of research to do there.

And if you're asking me when this will happen, I really do not have the answer.

You have to ask a physicist.

There are many other topics in quantum computing that might impact cybersecurity, namely the delegation

of quantum computation.

So the idea that not only you can do encrypted computation over the cloud, but you can also

delegate and encrypt the computation that you are delegating.

Quantum key distribution.

There were other talks at CCC previous years about QKD.

Something called position-based cryptography.

And if you want to learn more about the computational aspects, so the algorithmic aspect of what we

do is quantum computing.

You can find an open source project set of lecture notes on quantumalgorithms.org.

And the last thing, I'm hiring at CQT, postdoc internship for PhDs and research assistant positions.

So thank you so much.

So we actually have a lot of time for questions.

Please, people who are leaving, leave very, very quietly.

And please take your trash.

But questions.

Do we have any questions?

We have four microphones on the floor.

And we have the signal angels on the internet.

You have to go to the microphone, sorry.

So if you have a question, step up to the microphones.

All right.

Microphone one.

Hi.

You mentioned that you were speeding up the Tifoli gates with some enhancements.

Were these enhancements for lattice general, or was it specific to learning with errors,

or short integer solutions, or was it...?

Can you repeat the beginning of the question?

Yeah.

The enhancements on the Tifoli gates that you showed earlier, was it on all lattice algorithms,

or was it specific to learning with errors or short integer solutions?

It was for general lattices.

All of them.

Yeah, but the algorithm is not done by us.

We just implemented it.

Thank you.

So, microphone number three.

Hi.

Hi, Alessandro.

Thank you for your time.

I have somewhat of a more different question.

So, you've shown a lot of resource estimation where we look into how much does it cost to compute

this.

Do you also have work where you look into the adversarial cost, as in how much does it cost

to do this in an attack, as in compared to a classical attack path, where you do, for

example, in the short algorithm, you usually decrypt things.

So, you look into an attack on crypto, and usually it's, you know, at the end of the

attack chain, after exfiltration, to decrypt certain things.

Can you more elaborate, maybe, how the attack path looks like in comparison, the adversary

cost to use a quantum computer versus a classical thing, and what the timeline would be?

That's a great question, and I'm afraid I don't have an answer for that.

There's probably more research to do to understand that.

Yeah.

So, we have a question from the internet.

Yes.

Thank you.

The internet is wondering if you could go into more details about the differences and

the synergies between a classical neural network and a quantum neural network.

To answer properly this question, it takes more than one PhD, for sure.

What can I say?

Well, I mean, the similarities is that you have a quantum circuit, and a quantum circuit

is composed of gates, and the quantum gates are somehow more general than classical gates,

so you have angle of rotations.

And the idea is that you can do gradient descent or other optimization algorithms on these parameters,

and this is similar to the weights of a neural network.

So, that's a similarity.

And the difference, well, the difference is that one is quantum, the other is classical.

So, we still don't know if one is more powerful than the other, if one is trainable,

if it's trainable, maybe it's classically simulable.

So, it's a very open area of research.

Microphone number three.

Sorry, one.

Hi.

Thank you for the talk.

I was wondering if you could quickly explain the similarities and differences between time

complexity classes for classical versus quantum algorithms.

Exactly.

Another great question.

It requires more than a PhD.

But, I mean, complexity theorists try to take complexity classes and add quantum somehow.

And then they try to compare these classes between quantum and classical.

So, there are a lot of open questions.

If you have any more precise thing, maybe we can discuss it later.

But, yeah, it's a big, big topic of research.

Thank you.

Thank you.

Thank you.

Microphone number three.

Hi.

Thanks for the great talk.

First of all, I wonder if you heard about the first theoretical, practical approach, research

of Harvard University, and logic-based coprocessor they found with natural atoms, where they found a methodology to build up a processor for quantum computers with less physical qubits than it's foreseen.

Because it's helpful for the next threat, let's say.

So, I wonder if you know about it.

And I wonder if you could use this approach for this open research themes as a thing of the memory-based problems and challenges.

Thanks.

Thank you.

Great question.

Are you referring to this recent result of a few weeks ago?

Yeah.

I think, I mean, it seems to be solid research.

So, I'm very happy.

But, again, I'm not a physicist.

So, like, between me and them, there's a whole stack of people that needs to connect our results, basically.

But, yeah, I'm hopeful.

That's great.

That's great.

So, we have a question from the internet.

Thank you.

The internet is wondering if what you showed is also applicable to special quantum computers, especially quantum annealers.

And they're referring to an announcement made by Lockheed Martin a couple of years back here that they were able to do something like Shaw's algorithm here.

Great question.

I usually do gate-based quantum computing.

So, the thing is that you can put whatever you want in an annealer because the thing that the annealer is solving is very general.

It's very simple to see that you can reduce factoring to an optimization problem.

Right?

You have N, the number you want to factor, equal P times Q. And you do N minus P times Q. And you are trying to minimize the difference between these two things.

So, the difference is zero for the right P and Q. But if you try to do this on an annealer, you don't have a proof that the runtime is polynomial.

For the annealing thing, it's like quadratic or cubic in something called spectral gap.

And for factoring on annealer, we don't have any bound on this thing.

So, microphone two.

Right.

Joran?

Thanks for your talk.

What I want to know is what the...

Well, I know quantum computers are still experimental.

And how well do your algorithms break or scale or break up to the currently available systems, physical systems, or...?

Well, it's a great question.

And unfortunately, the answer is they don't run very well because they really require a lot of qubits, a lot of gates.

So, I need error correction to run anything meaningful.

Question from microphone three.

Yeah, hello.

My question also relates to this.

And I want to be a bit more specific.

So, it's really hard, as you mentioned, to judge how well things are going and how well are things progressing, apart from all the hype that's been going on.

So, one thing that I was asking myself, so how far are we actually with factoring numbers?

And despite the progress that we've been seeing in quantum processes in the past years, I believe that except for certain publications that maybe happen once or twice a year where they factored a really long number, but like they've pre-chosen that number to optimize for it.

Exactly.

Yeah.

And I believe the current record still is more or less factoring 15, and that has been since 2012.

Why hasn't anything happened since then?

I think they may have gotten up to 21 by now.

Great question.

I don't know.

I don't know.

I don't know.

Well, maybe because also the attention shifted to other topics.

Maybe.

Yeah.

Thank you.

I think we have another question from the internet.

Yes, thank you.

And the question is if you have ever had the chance to look into the cybersecurity application for quantum certified deletion.

So quite special, maybe, but maybe you have some experience.

Quantum certified deletion.

Yes.

Never heard of that.

Yeah, I just Googled it.

It's a paper may.

Okay, cool.

Microphone three.

Hey, so when you talked about quantum machine learning, you made a distinction between predictive model and variational model.

I was wondering how do they differ in terms of what happens when you need to measure in intermediate steps or the wave function collapse in general?

What is the difference between those?

And if there is more than that?

Because you named two, but maybe there is more.

Yeah, good question.

So, as far as I know, you don't measure much during the computation in variational algorithms, but you can measure intermediate things in provable algorithms.

There are other models.

For example, annealing is one of those.

Also, there are two, three papers where they try to do something in between variational and provable.

It works by Kerenidis and Prakash, some recent results from them.

But no, this is what I know.

So, just these two, three things.

So, we still have a little bit of time and we have a question yet again from the internet.

Yes, internet is on fire today.

Okay.

So, the question is, is there an equivalent for, in quotes, gigahertz or speed measure for quantum computers?

Absolutely.

Yeah, yeah, yeah.

Absolutely.

I think, depending on the hardware, you have different clock speeds.

I didn't mention that, but it's really platform dependent.

Some architecture are faster than others, but in general, for superconducting, I think the clock speed is in megahertz.

So, this is also why we are very slow to get practical quantum advantage, because the clock for quantum computers is much slower than the clock of classical computers.

Question from microphone three.

I come from a math background, so maybe the question is stupid, but the matrices where you said you need linear time with classical algorithms to process it.

How do you get the matrix in sub-linear time into your quantum computer to process it?

No, no.

So, imagine you...

No, no.

It's a very good question.

You give the matrix classically.

And then, in linear time, you can build quantum access to this matrix.

And then, the quantum algorithm is polytime or whatever time it is.

Okay.

Yeah.

So, one...

I get maybe final question from microphone one.

So, this is more of a general question.

You said that there's a lot of hype.

I mean, there is a lot of hype around quantum computing in general.

And I'm curious, what are your opinions on...

Not the hype, but what is the most promising application that quantum computing can bring?

And if any, or are there some things currently being overhyped?

Or what do you think?

What's your general opinion?

Great question.

Okay.

So, I mean, for the crypto that we're using nowadays, I'm sure it will eventually work.

Maybe quantum finance is slightly overhyped.

So, quantum algorithm for pricing derivatives and these kinds of things.

Estimating the risks of something.

But maybe quantum chemistry is something where we can have advantage in the next years.

So, new molecules, new material, estimating ground state of things.

Yeah.

Maybe that.

Okay.

Thanks.

Thank you.

I don't see any further questions, so let us thank Alessandro for this fantastic quantum talk.

Thank you.

[Transcribed by Pekka P]

(KYBS2004 course assignment at JYU.FI)