Quantum supremacy is this very basic
scientific question people researching quantum computers have had over the past
few decades. Is basically can a quantum computer actually do something that a
classical computer cannot? Welcome to Hedera Hashgraph's Gossip About Gossip.
If you are a developer, an entrepreneur, crypto enthusiast or just trying to
learn more about how distributed ledger technology and Hedera Hashgraph will
impact your industry, then you'll love the episodes that we have coming up.
Bookmark us. Add us to your podcast app and stay tuned! Hey there and welcome to
Hedera Hashgraph, Gossip About Gossip. I'm Paul Madsen. So it's it's likely you
heard the recent announcement from Google last week about what they had
achieved namely something called quantum supremacy.
A term, I had never heard
before. Bitcoin immediately crashed and then you
know, just as illogically surged on another announcement from China. I'm
happy to welcome my colleague to help make sense of quantum supremacy and and
its potential impact on Hedera. Atul Luykx, welcome Atul, how
are you? Alright, thanks Paul I'm fine thank you.
So you're head of cryptography at Swirlds Hedera? Yes, that's correct.
Awesome, so you're perfectly positioned to help us understand
supremacy and I guess the broader possibilities risks and opportunities of quantum computing to both Hedera and DLTs in general. So before we dig into
that, what's your background? How did you come to Hedera? Yeah, I've been doing
research in cryptography for the past eight years or so. I did a PhD at the
University of live under supervision of pardon.
For those who aren't familiar
with the University of Leuven in Belgium. That's where the AES, advanced encryption
standard algorithm was developed. While I was there, I focused on the
design and analysis of cryptographic algorithms. Trying to prove that
they're secure and I've designed of a handful of my own cryptographic
algorithms. After completing my PhD, I did a post-doc at UC Davis with another
cryptographer named Phil Rogaway. Where I then focused more on protocols
aiming for anonymity. Then continued at Visa Research where I then
looked at cryptography as relevant to the conventional payments infrastructure.
Then I kind of stumbled upon Hedera, you know where basically you get
a much more exciting application of cryptography to a blockchain where cryptography becomes evermore relevant. And over here I've been
continuing my research into cryptography and also kind of working on a consulting
basis with various people throughout the company. Awesome great to hear so how does
one become a cryptographer? Were you a math kid? Yeah, I was basically as I've
always loved math. I've been programming since I was five years old.
I studied math at my undergrad and then cryptography it's a very
interesting intersection of math and computer science where you can actually
you know be busy with slightly more theoretical math but then stuff that has
a direct impact on the world actually. Which is definitely true of the
possibilities of quantum computing on on encryption in general or security in
general and and DLTs in particular so let's dig into that. Google announced
that they had achieved quantum supremacy. What does that mean?
What is the supremacy? So quantum supremacy is this very basic scientific
question people researching quantum computers have had over the past few
decades. It's basically can a quantum computer actually do something that a
classical computer cannot? So that that seems a very pretentious way of saying
that a quantum computer can do something presumably faster or better than
a conventional supercomputer perhaps? Exactly and so what the Google experiment set
out to do or what they claimed was that here we've designed a quantum computer.
Okay, which can run an algorithm which will only take our computer about you
know three minutes to complete.
Whereas if you were to run it on a classical
computer on a regular computer then it would take 10,000 years.
So this clearly demonstrates that quantum computers can definitely do
stuff that classical computers cannot. That's what the Google paper claimed.
Okay, so I understand IBM disagrees and contended that, that wasn't supremacy? Yes, exactly IBM's response was basically so they
went into this analysis that Google made. Google made a few assumptions about
classical computers in determining how long it would take a classical computer
to solve the problem. Right so this is how Google arrived at their number
They obviously didn't run a computer for 10,000 years to figure that
out. So IBM then questioned their assumptions and actually pointed out, "hey
if you use these classical computers in this different way then you could
actually solve this problem in two and a half days instead of 10,000 years." Okay,
so it then doesn't become as clear that Google has Illustrated quantum supremacy. Right, where's with Google's estimate is okay blatantly clear ten thousand years
versus three minutes. With IBM you know two and a half days then it doesn't
become, it's not as clear-cut as an answer to the quantum supremacy problem.
Sure, it sounds like a bit of a nit from IBM though right? Because you're still acknowledging that Google did something cool but not that cool. Absolutely, yeah I
mean IBM might be a bit jealous right because they have their own 51 qubit
computer and they didn't come out with this first.
So yeah let's come back to qubits and the significance of 51, I think Google
had 53 so maybe there's competitiveness there? So whether or not it was two and a
half days or 10,000 years, Google's quantum computer was still
able to do something fast or some calculation faster than a traditional
How? What is the magic in quantum computing that allows it to be
that much faster? When analogy I've heard that, seems intuitive Atul, is
that you know classical computing is like heads or tails right. A given coin
can be heads or tails. But if you flip it while it's in the air it's impossible to
determine whether it's heads or tails. So in a sense, it's both. And quantum computing is acknowledging that superposition of heads and tails together at any one time and leveraging
that that blurriness of the state of that coin.
Yes exactly. Without going into too much detail so what quantum computers are
able to do is they're able to take their state and then go into what's called
quantum superposition. Okay, of that state.
This then allows quantum computers to do
many many different computations in parallel ok while they're in quantum
superposition. Okay so that they can explore many different possibilities of
how the computation would result. So the trick with quantum computers then is
that if you actually want a final result? You're gonna have to collapse
the superposition down to one. Okay and somehow reduce that uncertainty into
certainty and it's basically through this power of being able to do many
different computations at once that you can actually achieve a lot more with
quantum computers. Okay, so I saw an analogy if you think about Google Maps or any of
the map algorithms the mechanism by which they determine the best route from
A to B is effectively try them all and one after another see is this better
than the next one? And a quantum map algorithm would in a sense try them all
at the same time and then filter out the answers that weren't good.
Is that fair?
Roughly yeah yeah. Roughly that's that's awesome. Okay so we achieved roughly. So that's in general why quantum computers can be fast, they
parallel processing to a certain extent with some cleaning up at the end. And
they were able to apply this or Google was able to apply this sort of generic
functionality to solve presumably some obscure math problem that isn't
immediately relevant. But quantum computers are also being perceived as
presenting a real risk to internet authentication, HTTPS, SSL, etc and crypto
like crypto in the 'cool' sense. Cryptocurrencies like hbar and others.
Why? What problem will quantum computers be able to address that isn't feasible
with a traditional computer? So in this respect there's actually two types of
attacks that quantum computers will be able to do once they're around. One of
them which is you know relegated to the far-future let's say. It's where maybe
people are using quantum computers on a daily basis and they're actually running
cryptography on those quantum computers.
If you have a situation like that and
someone wants to attack you? Then they actually have a new avenue they can try
and entangle their computer with your computer and actually recover your keys
much faster. Actually attack your cryptography much faster. But that's
like a really futuristic type of attack where you know we're running desktop
computers which are quantum or something like that okay. But just to give you an
idea, people are even doing research into these types of attacks okay.
Now then there's
the second more serious problem where in the current world we're running
classical computers and we're running cryptography on the classical computers.
Then all of a sudden maybe some large nation-states or who knows some
criminal organization they're able to build a quantum computer and what they
do is they then you know maybe they'll collect our Internet traffic or maybe
they'll have a look at the Bitcoin or Hedera ledgers and take that
information, feed it into their quantum computer and they'll actually be able to
recover the keys in the cryptography using all that communication okay. So
this is a much more serious problem though, one that people are much more
concerned about. There's two very well-known attacks in that situation
that people are most concerned about. One is called Shor's attack and the other is
called Grover's. So what Shor's attack allows you to do is you've got your
quantum computer, you've collected all this internet communication you know for
example TLS communication bring in a new computer you perform Shor's algorithm
that allows you to factor the RSA public keys to be able to
determine the secret keys okay so that you could actually then recover all the
keys using it in a communication.
Then there is Grover's algorithm which allows
you to perform a key search much faster. There's all kinds of cryptographic
algorithms out there. There's already mentioned one which is based on
factorization there are ones which aren't based on those like the advanced
encryption standard what Grover's algorithm allows you to do is to brute
force search keys much faster you know it allows basically a quadratic speed-up
in how fast you can search for keys on quantum computers. Basically it's good to
say long story short if you have a big quantum computer out there yeah you're
gonna be able to factor numbers and a lot of the deployed crypto out there is
broken okay. Thanks basically due to Shor's
algorithm. There's Grover's algorithm which also
severely impacts a lot of different cryptography out there as well but the
effect of that to avoid that one you can just make your keys larger okay because
all that Grover's does is just does a big brute-force search. If you make it
keys larger then it's gonna take a lot longer for them to search for the keys.
Okay so so both those attacks if I understood correctly are because of
quantum computing speed or in a sense just optimization of solving the
difficult problems on which modern crypto non quantum modern crypto relies
right just whether it's factoring a prime or you know brute forcing as you
described and a quantum computer can just go through that search space
Is that fair? Yeah exactly. Okay so and
then the the first scenario you described is when it's not modern crypto
RSA elliptic curve or otherwise but some future quantum cryptography
and then then entanglement and that gets that gets even weirder I would think. That gets much weirder yeah the only reason I bring it up is because I've
been starting to see much more research happening about that.
You get much
more devastating attacks okay but again your attacker would somehow to
entangle their computer with yours and who knows it's a kind of a wait
situation. Right so even with respect to the you know the feasibility
of the second attack using quantum against modern crypto. Vitalik Buterin drew the analogy you know we've had fusion we have at nuclear fusion for
years physicists say it's possible but we're still burning coal. How far away is
that scenario that you described? Yeah so let's talk about Shor's algorithm. That's
the factorization algorithm so right now the best computers best quantum
computers that we have are somewhere between 50 and 100 qubits.
estimates to be able to feasibly run Shor's Algorithm is you'd need several
thousand qubits ok and this is assuming those several thousand qubits assuming
that they work perfectly ok. There's this problem with a lot of quantum computers
nowadays is that they there's a lot of error in the computation. We're all used
to classical computers where if you compute a function ok you if you do 1+1
and you do it a million times you always get two.
It's not the case with quanmtum
computers you actually could get errors in your results so you need to rerun
your computations many times. They have all this process called error correction
basically. If your qubits work perfectly you'd need several thousand cubits to
run Shor's algorithm. If you need to use error correction then you'd need a few
million qubits to be able to run Shor's algorithm. So just to put that in
perspective our best estimates is you need a few million qubits to run Shor's
algorithm. We are currently at 50 to 100 qubits. Unless we find a way to
significantly it's very quickly scale the size of our quantum computers it for
the foreseeable future isn't we shouldn't really be concerned about
Shor's algorithm. Is it just engineering? Like that the physics is known and now
it's just a matter of resolving the technical challenges? So that's yeah
so that's what these papers now from Google and IBM so they're
kind of solving these scientific problems the initial problems showing
that hey look this is all feasible and we're able
to scale somewhat.
Now getting to really wide scale quantum computers
there gonna be some significant engineering challenges. Okay well that's
good to hear right! Yeah no absolutely we've got we've got a ways
away. We've got time right. Yeah so Hedera
specifically if the opportunity for a hacker with quantum computing even
acknowledging it's not immediate it's in the future. If the opportunity is to hack
private keys so Hedera uses private keys both for no signing of events, for
clients submitting transactions. Which parts of Hedera's algorithm or
infrastructure cryptographic infrastructure are safe or quantum safe?
So if we very narrowly look at it okay so there's the there's the hashgraph
itself okay there's the history of events that have happened and then the
hashes being built on top of hashes okay and so I say the history is
protected it'll be very difficult for people to go back in time and change
events. But if the hashing function is is a one-way function is that not vulnerable to optimization? You're you're right it's vulnerable to Grover's attack okay
yeah that's why I brought up Grover's attack as well it wouldn't be more
vulnerable but we're using sha 384 okay which is a rather large
hash function so even if you have a huge quantum computer and you want to invert
this hash function it's still going to take a significant amount of time.
because Grover's algorithm doesn't provide as you know such a significant speed
up. Leeman often makes the point that not specifically the hashing function that
we're using 384 but in some sense we're using overkill, throughout the
cryptographic choices that he's made and that gives us a certain future
proof. Yeah that is the case although our signature algorithms are vulnerable
meaning that's the signing functionality for transactions for nodes.
That would all be vulnerable. Like everybody else.
Yeah and that's the point. Right is that we're not the only ones
out there right so there's all of internet banking becomes vulnerable like
you know all apps all enterprise security okay so it's basically it's a
much much larger problem than just for Hedera.
That's why there's also the
significant amount of interest across the industry. So we talked about the
risks that that quantum computing present to DLTs in general or crypto in
general DLT specifically. I've also seen arguments that quantum computing could
provide an opportunity for crypto in generating I think what they called
certified randomness. Randomness is great in DLTs particularly if you're trying
to elect a leader any thoughts there? mm-hmm
Yeah you could potentially use it to as a very good source of randomness okay
and the fact that it's verifiable this is this is very new research right
things Scott Aaronson is also looking into this. I mean the question is would
you be able to practice make use of it in a practical way that's it's hard to
say right now but it definitely looks like, I mean a promising research area
let's put it that way.
Okay fair enough and of course hashgraph we
argue that you don't want a leader in the first place where do you pick them
verifiably randomly or otherwise. So I understand there are quantum resistant
alternative cryptographic algorithms. Is it the case that they're less
efficient particularly in the early days perhaps? Yes yes there's been over the
past two decades a lot of research into designing either either called
Quantum resistance or post quantum cryptographic algorithms and what tends
to happen is is it's one of two things either if we take something like
signature algorithms right and algorithms which sign one thing that
happens is the size of the signature becomes huge okay which then will
significantly increase your communication costs. Even if the
computation is not so much. On the flip side there are signature post quantum
signature algorithms where the signatures aren't so big but then all of
a sudden you need to do a lot of computation to be able to
verify or sign.
Still you know I think factor 10 a hundred times slower
than existing signature algorithms and this is very much still a research area.
But on the flip side if all of a sudden someone were to say oh we've developed a
quantum computer you could in the worst case switch to these slower algorithms
for your most sensitive operations. That's interesting, fascinating. Atul
thank you very much for this I think beforehand my my state was maybe
fifty-fifty on understanding and knowledge and you've moved me to the
right I'd say a superposition of 30 and 70 perhaps. But we'll only find out
once we measure your knowledge. That's true I'll have to quiz you'll have to quiz me and collapse
the the wavefunction. Yes awesome! Atul thanks again. Thank you, Paul.
Thank you for listening to Hedera Hashgraph's Gossip About Gossip. If you liked
the episode please subscribe rate and review and also share and tell your
friends. Or connect with us on social media like Twitter Instagram etc at Hashgraph.
Particularly if you want to leave us feedback on the podcast. We look
forward to hearing from you.