[Music]
everyone today we'll be presenting to
you post Quantum cryptography uh the
cryptography of the future something
that will come up after quantum
computers come
in let's start with our agenda we'll go
with present day cryptography first so
you'll see RSA eptic curve all the
things which we use today right after
that we will go into the second part
which will be okay
sorry yeah uh Quantum Computing and how
do they affect present day cryptography
then we would delve into securing the
future uh which is what is the
cryptographic researchers doing about it
right what are they doing about it
finally we'll look at Crystal skyber
that is a nest finalist and an algorithm
that all of you will be using in the
future with that let me show our bios
so yeah I'm rek and that's tarun so both
of us are very enthusiastic in this
space and read a lot about postquantum
crypto apart from that I have some uh
research articles also in the
space let's start with a big imagination
imagine does not mean the John lenon
song Imagine is uh I want you all of you
to imagine so let's imagine a world
where communication is no longer
possible uh all internet communication
is hacked so what are the three uh
different very useful use cases right we
have net banking so uh in net banking uh
in net banking basically I have money
but somebody halfway across the world is
using my money to buy coffee then
there's email uh CEOs send confidential
emails but suppose there's a scenario
where competitors are able to read your
emails finally intelligence agencies
intelligence agencies have uh include
something like CIA raw and all of them
have National Secrets right what if
their data is also compromised so what
is that one common thing that ensures
security of all of these the answer is
cryptography so you have two kinds you
have symmetric and you have asymmetric
correct so in symmetric you have a
common key and the common key is used
both by the encryptor and the decryptor
to encrypt or decrypt a message while in
asymmetric cryptography uh you have
algorithms where you have a public key
and a private key where the private Keys
is with only the owner and publicly
shared across the world and you use use
the public key to encrypt data while the
private key is the way to decrypt it so
to share uh
the Kei right for symmetric encryption
as well you would need asymmetric to
bootstrap and start it right so all
primarily we have three algorithms that
use uh asymmetric crypto the ones which
we use nowadays one is RSA one is Def
Helman and there iseptic curve based
variance and all of them they rely on a
hard mathematics problem so RSA relies
on prime factorization while defy Helman
and ECC relies on the discrete logarithm
problem so what we say is RSA will
remain secure if prime factorization is
a hard problem similarly defy Helman and
ECC will remain secure as long as
discrete logarithm problem is
secure uh can somebody guess what this
is okay that's a very vague question my
bad so this is the amount of years it
would take for you to be able to crack
RSA 20 for it uh to put this number into
p uh perspective and just to tell you
this is called 19.8 quadrillion years
even I had to Google what you call so
many zeros right uh the age of the
universe is 13.7 billion years so we are
writing algorithms that uh would take
even more than the age of the universe
to
crack that is good right RSA 204 it so
this is for rsa2 for now uh
over here you would be able to see
security levels so security level is the
amount of computations would you would
need to take to be able to crack
something so say for example RSA with
2048 uh key size has 112 bits of
security that means it would take you 2
to the^ 112 computations to be able to
crack it and as you just saw that is
19.8 quadraline correct and the other
algorithms if you look at the ECC part
or the Diffy helment part you would
observe the security level is either
equivalent or even more so if it's more
that basically means it will take even
longer for you to crack it so natural
question comes uh why are we here uh why
are we having this talk the answer is on
the top right over there quantum
computers with quantum computers there's
a different way of compute they will
revolutionize the way we compute and can
solve some difficult problems in a uh
easy Manner and I'd like to stress here
not every problem but certain problems
can be solved much faster using quantum
computers that is why you're here so uh
before we go deep into this let's look
at Neil B Scot Neil bore is a uh father
of quantum mechanics one of the fathers
I would say and uh we'll look into
quantum mechanics after this and quantum
mechanics is truly profound profounding
and shocking so let's start with shinger
cat Okay uh all of you would have heard
of it sometime in a physics lesson or if
you watch Big Bang Theory you would have
seen uh Sheldon explain it to penny four
times in one episode so uh yeah what let
me try and explain it to you again for
the fifth time for those who have
watched Big Bang Theory so uh shorting
us cat basically has a cat you have a
box you put the cat inside the box and
close the box now once a box is closed
there is no way of you getting
information outside so there's no way
you would know what is happening out if
the what what is the state of the cat
right now you use poison and you put
this poison in inside that breaks at a
random time te so until the poison
breaks uh like once the poison breaks
the cat will be dead uh until it uh it
does not break it's alive correct so but
since the box is closed and there's a
like the poison will break at a random
time until the box is closed we would
say the cat is both dead and alive at
the same time right because we for us
outside there's no way to understand
what is happening and if what's the
state of the cat so the cat is in a
super position of alive and dead now the
only way you would find out what it
actually is is by opening the box if you
open it it will be alive or dead but
there's a very interesting concept over
here uh which is how Quantum bits work
so Quantum bits can also be in a zeroed
State and first state at the same time
just like the cat is both dead and alive
your Q bit or Quantum bit can be both
zero and one so that gives you a
different way of computing all
together with that uh a question comes
what are the three so there are three
primary things that help you like that
show how quantum mechanics can Quantum
Computing is different compared to
regular Computing first is dual nature
so in dual nature basically means a
Quantum entity can both be a particle
and a wave second is superp position so
uh classic computers you have a bit it's
either zero or one in quantum computer
as I just said shinger SC both de than
the AL similarly a q bit can be 0 1 0
and one at the same time so you see a
spear over there and it means your bit
can be anything over there
finally you have something called
entanglement entanglement correlates to
different cuits so suppose uh I
correlate two electrons and dist them
apart quite far away right now uh if I
measure one I know for sure the other is
this and this is primarily used in
Quantum key distribution and does have
other applications as well so after the
how let's look at some applications if
you look at the use cases you would see
applications in chemistry simulation
communication algorithms uh machine
learning a lot of different use cases
and these are just starting so we'll
have many more in the future uh primary
Quantum simulation optimization problem
so you would have understood a cubbit
can be both zero and one at the same
time right so definitely there'll be
some kind of speed up when you're doing
simulation and optimization now you
might wonder why factorization of large
numbers is present there on the list so
some of you may have guessed uh RSA
depends on this and as I mentioned in
the start if uh if Prime like RSA
security depends on factorization of
large numbers so if this is an
application of quantum Computing what
happens to our present day cryptography
let's have a look
so these are some news clippings from
the present day world you can see
different uh universities and different
countries claiming different
things yeah so I'll move next so now an
important thing comes comparison right
you have classic computers you have
quantum computers RSA 2048 has 112 bits
of security and that takes some
quadrillion years to crack which is
greater than the age of the universe so
we are safe now assume you have a
quantum computer that is capable enough
and has enough Q bits what would the
bits of security change
to uh as you can see asymmetric crypto
is no longer secure right you can see
bits of security are just 25 31 31 is
for RSA 15360 so that is comparatively
very less and it is no longer secure
even on the uh symmetric side you would
see as 128 as 256 bits of security of
halfed but over there you can double uh
the key size and you'll be safe but
asymmetric is a byy by so buyby
asymmetric
crypto now I used RSA as an example but
the other algorithms which are ECC and
defy helment depend on something called
discrete logarithm prime factorization
and discrete logarithm all are solvable
by the same algorithm called Shores
algorithm and that's a Quantum
algorithm so if these present day crypto
systems May no longer be safe in the
future what do we do so to uh all of you
would be familiar with this set right
the NP Set uh you have polinomial
problems you have NP complete problems
and etc etc so what the quantum
computing power gives you is it
envelopes the P set and gives you more
different uh problems which you can
solve easily so that's what we call the
bqp set and RSA def Helm and ECC all of
them the hard problem which they rely on
Falls inside this so it's possible for
quantum computers to crack so what did
the crypto researchers do they found new
hardmat problems and now they'll base
their security on this so yeah okay if
it's outside the bqb set even it should
be safe from quantum computers as well
right and as you can see now
cryptographers they have come up with
six different families all of them
depend on a different hard mathematics
problem that we hope is not solvable by
quantum computers we are not sure and uh
tarun will specifically speak about ltis
based cryptography ltis based
cryptography is uh one of the more
promising ones I would say because nist
has a couple of finalists from ltis
based cryptography and T will speak
about Crystal skyber as well later
[Music]
all right can everyone hear me
okay perfect so let's look at what a
lattice is what do you see on the screen
I don't know about you but the gamer in
me sees a Pac-Man going on over there
don't worry about that it's a bunch of
dots that are repeating again and
again so and we find that these have
some properties such as
they are a collection of points they are
regularly spaced from each other and
they extend to
Infinity now in general a latice can be
n dimensional one but for illustration
purposes we will look at two-
dimensional
laes let's see how we can form the
latice
mathematically we start by taking two
vectors V1 and vs2 also called as the
basis
vectors from the origin we move
alongside the direction of these two
vectors to explore new points and from
there we repeat this algorithm again for
example if our basis vectors were
represented by 5 0 and 05 and we were to
go in two times in the direction of V1
and one time in the direction of vs2 we
would reach to the point 5 comma 10 so
in essence a lce can be formed by its
basis vectors it can only contain
integer linear combinations so it can be
something like V1 + V2 V1 minus V2 but
not irrational combinations of those
vectors now let's take a step back and
try to see if the same lce can be formed
by more than one basis vectors here you
see that we have taken a different set
of basis vectors 5A 2 and 5A 6 and we
are trying to reach to the point 5a 10
your initial in might be that you know
it's not possible to reach but let me
tell you it is possible if you go two
times in the direction of the vector V1
you would reach 10A 12 and from there if
you come one step back in the direction
of vector V2 you would arrive at 5 comma
10 so what do we understand by this
experiment we understand that the same
lce can have multiple basis vectors and
a basis effect effectively determines
how efficiently we are able to navigate
through the
lce now I'm going to speak about the
hard math problem that forms the
foundation for postquantum
cryptography the problem goes something
like this we are given with two basis
vectors V1 and vs2 and we are asked to
reach to a point which is on the latice
and which is closest to a given Target
Point let's take an example to
understand this let's say our initial
basis vectors are 6 I + 3j and 14 I + 8j
and the target point is 11.6 4.2 now how
do we solve this problem as engineer
everything for us boils down to math and
so we do it we model this in terms of
linear equations and we have two linear
equations with two variables we solve
for x and y and we round them off
because we want to arrive at integer
linear combination points we plug back
the original values that we G got into
the equations and we find that the
closest point is 9 comma
-2 now let's take a retrospective at how
we did
you can see that we have our basis
vectors 6 I + 3j and 14 I + 8j and you
have our Target Point highlighted in
green and you find that the actual point
is highlighted in red now that's pretty
far off from our Target isn't it can we
do
better certainly we can do better let's
do something different this time let's
take the basis vectors to be 2J and 3 I
what do we observe here we observe that
these two vectors are perpendicular to
each other in other words the angle
between them is exactly 90° these type
of vectors are called orthogonal basis
vectors and right out of intuition if
you were to reach to the point which is
closest to 11.6 4.2 if you go four times
in the direction of the vector 3 I you
would reach 12 and if you would go two
times in the direction of the vector 2J
you would reach four so out of intuition
you can say that you will reach 12a 4
which is the closest point right now why
is this easy it's because the m in in
One Direction is not influencing the
movement in the other direction and so
we can conclude that if we have a set of
orthogonal basis vectors it is much
easier for us to navigate through the
lce let's see if we can do the same
using the same math that we used before
so again we model the system as a system
of linear equations you have 3x is 11.6
2 Y is 4.2 solve for x and y and you
round them off and you plug them in the
original equations and as you see we
have arrived at 12a 4 now let's see how
we did in terms of graphical
representation you have our basis
vectors again on the screen you have the
target Point highlighted in the green
and you have the actual point
highlighted in red you can see that's
pretty close right so at this point of
time I would like to pose a question to
you this was much easy to solve right so
what if we could use this to form the
basis of our new crypto system
and that's what exactly we
did let's say that we have a set of good
basis vectors which are orthogonal to
each other and describe a lce now we
treat these vectors as our private key
so we keep them safely with
us let's say that the same latice can be
formed by a set of vectors which are
nonorthogonal and so are bad basis
vectors and we make this vectors as our
public public key so they are available
to the public to see now if someone
wants to send data to us they can just
encode it in the lce in terms of some n
dimensional point and send it to us and
since only we have the good basis
vectors we'll be able to navigate
through the lce
easily now let's have a look at how hard
this problem becomes as the dimensions
go up you have a graph which depicts the
dimensions and the number of
possibilities and you can clearly see
that as the DI ditions go up the number
of possibilities are going up
exponentially and by this we can say
that the difficulty of this problem is
related to the dimensions in a direct
way we can also say that in practice the
algorithms that we use have more than
thousand Dimensions so this Factor makes
it extremely complex even for quantum
computers to solve this problem because
it's just that there are too many
possibilities and to give you
perspective this would give rise to the
possibilities which are more than the
number of physically observable atoms in
this entire
universe so in essence even though if
you move in some of the dimensions
correctly the chances are you will be
thrown off in the other dimensions if
you don't have a good basis
Vector now let's look at kyber which is
one of the post Quantum uh cryptography
finalist algorithms the way it works is
you start by taking a secret key of
vector and you form set of linear
equations so if you plug those values 10
8 to 5 55 in the below equations you
would get the right hand side and then
you see there's a plus minus uh error
which is intentionally introduced to
harden the problem so the system of
linear equations becomes extremely hard
to solve the difficulty of this problem
has been mathematically proven to be an
approximation of the closest Vector
problem that we just saw so think of it
like something like traveling
salesperson problem indirectly maps to
hamiltonian graph problem in terms of
its difficulty so if someone were to
solve this it means they are able to
solve the closest Vector problem which
we know till date hasn't been
possible now let's look at how data
exchange happens using this crypto
system you have your classic situation
the actors which we cryptographers
cannot live with we have our Alice on
one end and we have Bob on other end and
let's say that they want to exchange
data now Bob would take these public key
the equations from Alice and he would
encode his message in terms of these
equations either by performing additions
subtractions or some sort of linear
combinations on these equations and
forms a set of new equations he sends
these set of new equations back to Alice
as Cipher text and since Alice has the
correct solution to the these equations
only she can decrypt it using the
private
key and now let's look at how far are we
from the future on the x-axis you can
see that we have the passage of time and
years on the y axis you can see the
number of cubits that we need to crack
present day crypto you can see that the
estimated number of cubits that we need
to crack present day cryptographic
algorithms is constantly going down
while in reality the number of cubits
that we have achieved is constantly
going up and even at their current rate
of progression they are expected to meet
somewhere in the near
future now let's look at some of the
Practical Quantum advancements that have
been happening over the time in 2016
nist started with a postquantum uh
cryptographic algorithms call and
researchers from various parts of the
world submitted their research to Nest
over the years you see that many big
organizations take their baby steps or
initial steps in the world of Quantum
Computing you can see that in 2017
Microsoft went public with world's first
Quantum oriented programming language
called qar in 2019 Google invented its
first step towards achieving quantum
computers by inventing a 53 bit Cubit
computer that could perform basic
additions and
subtractions in 2021 you can see that
Azure built its first world uh world
class Quantum as a cloud stack solution
called Azure quantum
in
2022 we have a list of finalist
algorithms that have been selected as
candidates for postquantum cryptography
you can see that Crystal skyber is the
one that I just explained you but we
have three other algorithms these three
other algorithms are used for digital
signatures while crystal skyber is used
for public key
exchange going forward you see these
Tech Jes making leaps in terms of
quantum compute uh notable ones include
IBM bringing its first thousand plus
Cubit computer called Condor and Azure
launching its uh Quantum elements to
help chemist across the world solve
complex chemistry problems and you can
see that the adoption of quantum compute
is constantly growing
up and I want to tell you a funny story
here just a day before the presentation
I received a ping from one of my
colleagues stating that the ltis based
cryptography that I just shown you has
been cracked I don't about you but to me
that would be a bummer right I don't
want to present outdated content but
thanks to us the author of the paper has
done a simple bug in his code and has
retracted his findings so whatever I
presented is still safe for the
considerable
future so what do we want to conclude
here we want to conclude three things
one quantum computers are extremely
capable in terms of their computer
compute power now this is what
differentiates them from traditional
computers and enables them to push the
boundaries to break traditional
cryptographic algorithms and so
cryptographers have shifted their focus
to look for new hard math problems out
of which latis based cryptography is
just one of the families that seems
promising and last we would like to urge
you to keep an eye out on the quantum
world because this looks very promising
and even at the the current rate at
which it is progressing it seems that
these algorithms that we' have just seen
we will be using them in the very near
future thank you
[Applause]