[Music]
all right thank you
uh-oh are we on yeah thanks for the
introduction
cryptography is about people
communicating
we have names for these people imagine
one person
named alice sending a message to
another person named bob so here's
pictures of
alice and bob and they're communicating
through
the internet or through some network
they're very long distance away from
each other
and that makes a problem the problem is
that somebody's listening to the network
that's an eavesdropper and we have a
name for the eavesdropper the
eavesdropper there's alice and bob
communicating
the eavesdropper is someone named eve
here's a picture of eve
it's a great picture everybody one hand
on the laptop
one hand on the mouse
look at the camera look at the at the at
the screen and then everybody
okay so eve is listening to the
connection
and eve is maybe changing the data
changing the messages on the connection
so cryptography tries to protect against
this
and the way cryptography does this is
it writes messages in a secret language
cryptography means secret writing so
cryptography
changes the messages that we send in
some secret way
and then sends the modified messages
and then it's supposed to protect us
against the eavesdropper there are a few
different goals
for example confidentiality secrecy this
is saying
that eve cannot understand the messages
integrity and authenticity these say
that
if eve tries to change messages
or tries to pretend to be alice
then bob will figure that out
and we try in cryptography to make all
of these properties
confidentiality integrity authenticity
now you have encountered cryptography in
your daily life when you're visiting a
web page
assuming you're looking at the schedule
of vidcon you're going to an https page
and you can look
at what cryptography is secure in your
connection but it's not very friendly to
the user
because all you see there is three or
four or five letter abbreviations
and well here i've at least sorted those
into two different types so in
cryptography we have two types of
communication we have
cryptography with what we call symmetric
keys
if alice and bob have met each other
they know each other and they have a
shared secret
they can use some from this upper
category
and if they haven't met yet like you
visiting your web page you don't have
any secret information you share with
this webpage
so then you're using what is called
public key cryptography
and here are the names of the public key
crypto systems
these cryptographic systems are designed
so that
even if somebody tries to figure out the
secrets with a huge
computer this is a super computer in
china
publicly announced supercomputer in
china
the sunway taihoo light i guess if you
read the characters it says something
about divine power
and this is a very powerful computer but
even this computer cannot break
the cryptography that we're using today
well that is good for today there's one
problem
namely that in 1994 peter shaw found an
algorithm and this algorithm has one
requirement
it requires a sufficiently large quantum
computer this is a very very large
quantum computer
but given this quantum computer his
algorithm is able to break discrete
compute discrete logarithms and compute
factorizations
so factorizations is just the normal you
have a product of two integers
and it can break this into its two parts
or multiple parts
unfortunately these two problems are the
core
of what we see on the internet in this
category of public key crypto systems
so his 1994 algorithm is a real threat
to the cryptography on the internet to
the security
but this is only a threat if somebody
has
a quantum computer so do we have quantum
computers well
last year google proudly presented to
the world
a baby quantum computer okay they didn't
say it was a baby quantum computer
they said this is a powerful quantum
computer
this quantum computer has achieved
quantum supremacy this means
it does a calculation one special
calculation
faster than taihu
does the calculation this is
powerful for one calculation and this is
called
quantum supremacy
well but even though he looks very
friendly in this computer is like
nice colorful google colors i mean this
can't do anything evil right i mean it's
it's pretty red and blue
and the guy looks friendly however he's
pretty clear
about the impact on security the impact
on cryptography that this
research has maybe he is breaking a
little bit too much but he's saying
in a five to ten year time frame quantum
computing will break encryption
as we know it today
so that is a strong statement about
what these quantum computers will do in
a rather short time frame just five to
ten years
now what about other countries google is
building their computer in the u.s
so i looked around for trusted news from
other countries and i found a very
reputable news site from china called
globaltimes.cn
maybe you've seen it yourself and they
say that
chinese researchers are going to jump
ahead of google
of course this is what the chinese
government wants
everybody to know who knows what they're
doing secretly
but this is their public announcement
that china this was an announcement in
august
china is building a computer
that publicly is as good as google's
quantum computer what are they doing
secretly
who knows well so since we don't have
any pictures of that
uh let's put just the quantum symbol on
it it's like when you're pushing
purchasing something on the internet and
they tell you product details may differ
well this is our symbol image of a big
powerful quantum computer
that nobody is believed to have right
now but let's go back to the slide that
we had here
where i listed the different crypto
systems
so if eve changes and changes into eve
with a quantum computer
then everything in the bottom part
everything
under public key cryptography turns red
that means
it gets broken by shaw's attack
with a big powerful quantum computer
and what about these black things that
weren't broken well this is
symmetric key cryptography this was
again where the alice and bob
have met already and alice and bob are
sharing a secret key
and now cryptography can build
very easy solutions very easy ways to
securely encrypt your data if you have
a very long shared secret and long means
as long as the messages that you're
sending so if you've met somebody alice
and bob meet
privately and then they flip some coins
make some random numbers and they
exchange many many
random numbers and then they can use
what's called the one
time pad and that will encrypt
all of their data in a way that the
attacker
cannot figure out what the message means
they can also protect integrity and
authenticity they can stop
forgeries it's a little more complicated
but it's called a wegman carter mac
and this is a mathematical computation
which protects the
integrity of your message nobody can
fool
bob into taking another message it's
only from alice
now what happens if you don't have a
long secret key
alice and bob meet for just a few
minutes
and then they don't have time to flip a
million
coins what they can do is use aes
aes is a standard way to take a
short secret key for example as256
takes 256 coin flips 256 bits
and as256 makes a big
long random string which is like it can
flip
a million coins for you a billion and
alice and bob
if they know the same 256 bits
they use aes and they get the same long
shared secret anybody else who doesn't
know the 256 bits
they have no idea what the aas output is
they could try guessing but it takes a
very long time to guess
256 bits now
the security of aes is something that
people have studied for 20 years
and it's fine aes 256
will never be broken even with a quantum
computer
if somebody has a quantum computer they
can use
grover's algorithm which will
make guessing faster but it still won't
break
aes 256. if you're really optimistic
about quantum computers as an attacker
maybe eve thinks that
grover's algorithm will break aes 256
in only 2 to the 128
operations but that's a very large
number of operations
if you're using aes 128
then grover's algorithm takes 2 to the
64
operations and maybe that's a problem
but if you use aes 256 you're fine
as-256 will never be broken
okay so how about this other part how
about the part
in public key cryptography where
the quantum computer will break
everything so there is an area of
research and that's what the topic of
this talk is
and that's called post quantum
cryptography so post quantum
cryptography is cryptography
under the assumption that the attacker
has a quantum computer
so just as in our picture where we have
alice
and bob communicating and in the middle
eve has now turned into quantum eve so
quantum eve
is the same if that would before still
has the same interest as the same
eavesdropping desires
but also has a quantum computer it
typically doesn't mean that alice and
bob have a quantum computer
for instance alice and bot are
communicating today eve is recording
messages for later to break then with a
quantum computer
that's one of the scenarios we're
looking into with postpartum
cryptography
so eve has a quantum computer alice and
bob do not
and so this research i already showed
you the 1994 paper from shore
then had mentioned a paper by love
grover
from 1996 so these are the
two most visible algorithms but there's
a whole area of research called
quantum algorithms or quantum computing
where they have developed many more
algorithms
and several of those have relevance to
cryptography so if you want to learn
more about quantum algorithms
there's a link called the quantum
algorithms
zoo so you can go there and click on
them and you'll find out that some of
the algorithms
are good for finding fertilizer or
medication or weather forecasts
but then there also are some definitely
go over and show but also cooper berg
and several variations of those quantum
walks and so on
which have effect on quantum sorry on
cryptography
now it's not all lost
i showed you what is currently used on
the internet and that all turned red
but there were some systems even before
these other ones came into into use they
just were not as popular
but shaw's paper kicked off interest in
figuring out
what systems could remain secure against
quantum computers
and so after like a few years
people were pointing out hey look um
here is something which we believe
is even hard for a quantum computer so
even if eve has a squad computer
and it's a big quan compute and so on
then eve can't do anything against these
particular systems
and so this this area needed a name and
dan here in 2003 wrote on a mailing list
how about we call this
post-quantum cryptography so it's
cryptography
foreign area past the advent of quantum
computers
but it just means that the attacker is a
quantum computer does not mean that the
user
has a quantum computer and while this
was catching up so within three years we
had the first
academic workshop 2006 was the first
international workshop on post quantum
cryptography and that kicked off a
longer series
of conferences called pikachu so if you
google on the internet you'll find
pikachu
2006 2008 they were going basically
every year and a half and you see on the
slides that the frequency has sped up a
little bit
and if this talk interest makes you
interested in this area
you're just in time to catch the 2020
edition in two weeks from now which will
be held
online because no other country other
than taiwan can actually have physical
workshops right now
and in taiwan you can still participate
in these workshops when they're online
also several standardization bodies have
caught up so nist is the national
institutes
for standards and technology that is a
body in the u.s
but it has turned whether by historical
accident or by pushing of certain
nations
it has turned into the de facto
standardization body
for cryptography so nist defines what
cryptography gets used
broadly and so in 2015 they hosted a
workshop to kind of figure out is there
enough interest
and okay the room wasn't nearly as big
as this room but if
it was like 120 people which was more
than their room could handle so they had
to close registration
and they had to stream some stuff so yep
they decided it's interesting
and uh announced the next year that
there would be a competition
and this competition has been running
for the last few years and has kept
many of us busy and den is going to show
a little bit of the details of that
all right so let's take a look at here's
the names
of the well it's gonna take a little bit
of time okay okay so
big quake this is a code-based crypto
system
and the authors were okay uh
i won't go through all of these but just
to give you the big idea
these are from 260 people
actually even more people submitted
when nist announced they're running a
competition
there were 82 submissions these are only
the 69
public submissions nist said these were
complete
proper submissions maybe the other 13
didn't include software or they made
some mistake they didn't follow the
rules
but these 69 submissions from 260 people
all of these followed the rules and they
posted all of these
and this was the 21st of december 2017.
now by the end of 2017
10 days later there were eight
submissions that had been
attacked oops oops yeah
there are some of these that are in red
and those are broken broken means
it's completely unsafe don't use it you
cannot use for example
hk17 and the ones that are
underlined in red which is all of these
red ones
those had python scripts which
showed here's how to break these
proposals
some of these were posted the same day
or within a few days
but all of this was within 10 days of
the
submissions being public the brown ones
those were not so serious attacks
it was maybe less security than they
said they should have but maybe still
okay
and then well by the end of 2018
one year later you see a lot more red
a lot more underlines okay rank sign
this was a serious attack but nobody
wrote a python script so no
underline more brown ones with
some loss of security and then
nist said okay okay we're going to focus
we're going to have a second round of
the competition
with the most interesting submissions
and so they crossed out many submissions
and they selected
26 candidates now some of these are
in blue and the blue ones are ones that
merged
for example n true hrss and n true
encrypt
those merged those turned into one
submission
they're very similar and they said we'll
just
join the teams and work together and
there were a few different
merges and then well more attacks
happened
there were eight more attacks well some
of these were agila
5 and lita these were if i go back these
were already in
in brown before but then there were
eight more
attacks some of them serious attacks and
then nist said in 2020
just in july they said okay we're going
to focus on
15 the the ones that we think are the
most
interesting and these are the 15
including some some merges so you see 17
names
listed and out of these some of them are
called finalists and nist is thinking
about standardizing those in
while starting in a year or two they'll
select something
and some of them are alternates where
they're saying
they'll select some of those maybe in
three or four years
okay and this is the current status of
the nist
competition
so you might not think that everything
is kind of okay this is doing something
and also when you look in other reports
so the national academy of sciences of
the united states
published a big report so they got
people together
several researchers invited i mean they
had several researchers on the board to
write this report
they invited some more for special
sessions so we ended up going there for
a session on
on post quantum cryptography on and on
the effects of
quantum computers on cryptography and
then
end of 2018 they published their report
including 10 key findings now the first
key finding
you might translate is don't panic
the first key finding was well maybe a
little bit contradicted by google and
maybe the chinese
but they were saying we do not expect
that anything will happen in the next 10
years
that seriously threatens rsa 2048 so rsa
2048 is one of those
three-letter abbreviations that you saw
on the previous slides and it's a very
common system that you will find
when you click on the details in your
browser so if you're wondering what is
securing your connection to the internet
this is one of the typical ones
and this report with the basis of a lot
of researchers is saying
yeah probably nothing for the next 10
years
but that's just the first key finding
it goes up to key finding 10.
which i would say is more like panic
it ends with a nice words uh of saying
that deployment of postgrad cryptography
is critical
for minimizing the chance of of a
potential security and privacy
disaster these are academics writing
about
disaster so this is serious news this
really means
very do something and the main point
they highlight in this
key finding 10 is that it takes a long
time
to roll out and to deploy post quantum
cryptography
and so even though it's still 10 years
till quant computer that big that
threatening would be
existent it is high time to do something
here is another aspect that they don't
put into a key finding but they
highlight in section 4.4
namely the effects on long-term security
so
anything that you're sending today yes
we said even the most powerful computer
i mean the chinese one is only number
four
there are three more computers which are
more powerful but even those computers
cannot break our current cryptography
that we're using today
they might find other weaknesses
cryptography is often not the the
weakest part so i'm not saying that
everything on the internet is secure
but the cryptography is probably secure
against today's computers
however if an attacker is listening in
today
if they're recording the messages today
and
well your messages are going over the
internet so of course
they are public they get routed around
and we have seen for instance in the
snow and revelations
that the united states is very active in
recording the internet
i would be surprised if other
governments are not recording the
internet so you should assume that
everything you're sending today
is stored somewhere and even if it is
encrypted
well they can't read it today but they
might
store it and encrypt a decrypt later so
for future use that means once they have
a quantum computer they can go back
to today's messages anything that you
send today
which is still interesting in 10 years
when the attacker has a quantum computer
that is going to be lost and that's a
kind of strange time machine
because today you're feeling very sure
you're feeling secure when you're using
the internet
and we tell you yeah don't worry it's
secure the crypto is fine
but today's messages will become public
in 10 years and so it depends on what
the world is like
whether what you're sending today is
incriminating or not
let's look a little more at the other
issue the
timeline for deploying cryptography
there are many many steps that this
takes you might think it's very simple
like
we have some crypto system and we've
written down the crypto system and we
put it in the web browser and we're done
but
there are many many stages that we have
to do to make this work
let me start at the top at the top we
have to say
what are we trying to do for example
confidentiality we're trying to encrypt
data
and then you have to figure out some
mathematical transformation
some some crypto system which
achieves that goal which is able to
encrypt data
and then well maybe it's not secure so
you have to study algorithms
that the attackers might use you have to
think can
somebody break this using a big computer
maybe using a quantum computer in 10
years
and this you saw in the nist competition
there were attacks against proposals
from 2017
and there are attacks in 2018 and
attacks in 2019 and actually
there are even some new attacks now so
right now we're
at stage three we're studying algorithms
that the attackers can use
and we have to do this because we have
to throw away the broken systems
and only choose secure cryptosystems
that's stage four where maybe we're
getting to stage four but
we're not really there yet and even at
stage four
even if we have secure crypto systems
that's not the end
because we have to make these crypto
systems usable
people have to be able to use the secure
cryptosystems in
applications which first means we need
to have
algorithms which compute these
operations
the encryption or signatures whatever
operations we need to
have algorithms and software and maybe
hardware that's the next line here
we have to make that happen in a way
that people can use
and make it as fast as possible so that
nobody complains about the performance
and then you think okay now we can put
it in the browser but it's not that easy
because
the software is something that can be
broken
by timing attacks for example there are
always new announcements about
ooh the timing of some operation leaked
some secret data
and now the attacker knows your secret
key so
just the raccoon attack a few days ago
was a timing attack yeah
lots of these timing attacks breaking
everything
and so you need software and hardware
which does not leak information
through timing and through
electromagnetic radiation
and acoustic signals there's lots of
side channel attacks
it's not so easy to just implement an
algorithm securely
once you know what all the attacks are
then you can choose the
safe implementations the secure
implementations that
correctly compute the function that you
want to compute
and then maybe they're all too slow so
you have to
throw away algorithms again
and if it's fast enough and it's secure
software or hardware
for a secure crypto system then you can
put it into the
user application which maybe the user
says oh actually it doesn't fit
it's even though it was fast enough and
it's it looks good
they realize no no that's not what i
actually wanted it doesn't work in my
application
and so then you have to go back to the
beginning and start over
this type of picture of having stages
feeding into
subsequent stages this is called a
waterfall
and waterfalls are never good because
when you have a waterfall
if you have a problem at the bottom you
have to go back to the top
and start over and well maybe you can
fix it
a few stages before but it's much more
efficient to
think about the whole stack to
understand
everything that's happening and design
at the top
thinking about the rest of the picture
and
every stage looks ahead to what's
happening and people talk to each other
at the beginning but that's a big
project it takes a lot of time it takes
many years to
do all of this and to do it correctly
all right so that's what i mean by key
finding 10
and the high time now we don't have time
to go into
all the details of how these crypto
systems work we'll have one which we're
going to show you some basis
but at least to leave you with some
summaries
of what these systems are so that you
know like if somebody is trying to sell
you post quantum cryptography
then they should tell you what is the
assumption behind these what is the
thing that the attacker
is assumed not to be able to break and
so there are five big families
of the public key systems that we study
in post-quantum cartography
and i've been narrowing them down to
sometimes saying only encryption
sometimes saying only signatures so
encryption is the path that does
confidentiality signatures is the part
that does integrity and authenticity
and some of these schemes could actually
be used for both
but they're only really good for one of
them so for instance codebase
cryptography is an area i really like
but all the signature schemes that we
have seen from there
are not what you want to use so
i'm only saying code based encryption
and so the highlight of this is that has
been around for a very very long time
it is one year younger than rsa rsa was
the first
public key system that is described as a
public key encryption system from 1997
that is older than most people in the
audience here and then just one year
younger
is class is mcaleese who described a
system that is based on what we call
error correcting codes so that's not
codes as an implementation
or codes as in secret language this is
codes as in adding redundancy
so that when you're looking at a file
and it has been
well compromised but just by errors that
you can recover
the file so that is what we call error
correcting codes and he noticed
that you can turn the problem of
decoding
such codes into a cryptosystem
hash based signatures is what we're
actually going to spend a few minutes on
to explain so that is the another thing
which has a very solid theory
also goes back to the 70s and
the benefits there are that the
public keys are relatively small and it
has very few properties i should also
say for the
for the mclean system one advantage is
that the messages are very very short
public keys are large then isagenie
based crypto is a little bit
the new kit on the blog so we're not so
sure about that security
it has some very desirable features when
you care about
the sizes so dan was mentioning in this
waterfall that at some point you might
hit a block
because it's too large it doesn't fit
into things and codebase crypto
sorry i certainly based crypto the
advertisement is
that what you're dealing with is
relatively small
overall the smallest codebase crypto has
shorter ciphertext but gigantic
public keys code-based crypto both the
ciphertext
and the public keys are relatively small
i kept doing the same thank you so i
certainly have
small cipher text and small public keys
and the security now that's where you
need a ton of mathematics
to even understand what i'm saying so
there are mathematical objects called
elliptic curves and those you might
encounter in a course of cryptography
now isogen based cryptography is doing
some maps between
different curves and then the hardness
assumption is
that if you started on some curve and
somebody just tells you
the end of this computation some other
elliptic curve where you ended up
that it is hard to trace back how you
could possibly get there
and from all we know this is a problem
which even a quantum computer can't
solve
efficiently but it is a relatively new
problem so it is
less well studied it's a problem from
the 2000s lettuce-based cryptography
is well kind of an overall pretty okay
system so you have small public keys
small cipher text and you can also use
it for signature schemes
similarly small public smallish public
keys
smaller signatures it's kind of
versatile it's kind of
everywhere it is newer so we're less
sure about the security
and the hardness is finding something
which is called a short vector
in a lattice and then multivariate
quadratics
if you want to learn more about this you
are actually in the right country
because buying yang who was kind enough
to announce us
is a world leading expert in this area
and so there the advertisement
is that it is a scheme where it has very
short signatures
somewhat biggest public keys so that's
one of the downsides
and then the hardness relies on solving
systems of equations
now you probably have seen systems that
are linear and you're getting like
5 x plus 7 y is this
and you get another equation x and y and
you learned that this is easy to solve
what changes here is that they are not
linear not just
x but you also have x times y or you
have an x squared or y squared
and a few more variables a few more x
and y's
and a lot more equations and that is
another hard problem
in this case where signature scheme can
be based on
all right let's look at one of these in
a little more detail
inside signatures first of all what is
the data flow in a signature
well alice on the left side has a
message a picture or a document to send
to bob
and alice also makes a secret key that's
the
secret key all the way on the left and
then alice also
publishes something that everybody sees
bob knows this
public key and also the attacker sees
the public key
alice and bob do not share a secret and
now
alice uses the secret key and the
message to
somehow create a modified message a
signed message
to send through the network and then
that's received by bob and bob uses the
public key
to extract the original message
now if eve tries changing the message
corrupts the integrity of the message
changes the message to something else
then bob using the public key
will say wait a minute something went
wrong
what's the right message i don't know
what the right message is somebody
changed the message
so a signature system stops eve from
changing messages or making new messages
for hash-based signatures the only thing
you need
is a good hash function every signature
system that people use
has a hash function this is a function a
mathematical function that takes a
message of
any length and hashes it well does some
computation
which produces for example 256 bits
or 512 bits some short constant length
string every signature scheme that we
use
has a hash function hash based
signatures
all you need is a hash function the once
you have a hash function you can sign
messages and we'll actually show you a
little bit of how that works
quantum computers well grover's
algorithm can be used to
reduce the security of hash functions so
use at least 256 bits
or more but then you're safe against
quantum computers
and this is something which goes back
also to the 1970s
all right so if you want to use
something today and you don't want to
just
take things from the internet or the
nist competition where you see things
disappear and disappear and disappearing
here are some systems which are
basically on the fast track
these have already been standardized
this time not by nist but by the
crypto farm research group so that is a
part of the ietf which is well the
engineering task force um all right
these are the people
who specify what your browser has to
support in order to be allowed to go
online
and what the servers have to be
supporting in order to serve your
browser the right cryptography
now i said before that nist is typically
setting the standards for internet
in this case we had that the cfrg went
ahead and said
here are some systems which are
sufficiently well specified
that we can standardize them however
watch out
the caption doesn't say signature scheme
it has some extra words there
and those words are important so it says
that it's a stateful
signature scheme now stateful
means that you must be able to count
that you have to remember
basically what you have done and it's
not the normal data flow not what was
then was shown like there is
e secret key and a public key
stateful means you actually have a whole
sequence or an
array of secret keys and you have to
tick them off one by one you have to
remember
i have done three signatures i've used
the first three keys
in my one secret key and you have to
remember this pointer
if you ever go back and reuse
say the second key for a second
signature
then the attacker can break it the
attacker gets too much information from
that
so if you're in a situation where you
can count yeah i know you all learned
accounting
even before you went to primary school
but your computer
might not actually be as able to count
as you think it would be
for instance if you're using virtual
machines you might be
storing your virtual machine you're
recovering your virtual machine from an
image
well at that point you're going back to
the point where it was at that point
maybe you have done a few more
signatures since but
since restored from image your pointer
is back up here so if you're in that
scenario
you cannot use this but other scenarios
are for instance if you're a debian
developer and you're signing the code
release
well you better be able to count you
better know exactly where this
key was used for signature so debian was
actually saying yeah we are interested
in using the system
please give us a full specification we
would like to use this
and also if you're on a smart card like
if you if you're working on hardware
and you have some chip card those also
have memory
which is able to well keep state to
count
so if you're in that situation here are
two links and the slides will be online
you can just
click on those which specify hash based
signature schemes with all the benefits
that then was just saying that they
don't need anything other than a good
signature
a good hash function now that get a
signature and a post quantum
now nist is doing in parallel to the
competition
a fast track version of standardizing
these schemes as well
so in this case the cfid went ahead
standardized them and now nist is saying
hey okay we're taking the same they
asked for a few comments
but we're expecting this standard to
come out soon again this is for stateful
hash based signatures
they're not full-fledged signatures
however
they are ready to use and also iso which
is
international standards organization um
has now a track on standardizing
these hash functions or these hash based
signatures
let's look at just one example of how
hash based signatures work and then
we'll finish up
this is going to be complete
signature code in python for signing
using hash based signatures with one
restriction
the restriction is we can only sign one
message
the empty message that might sound
a little silly do that sounds useful
except if you think about it actually
that's very useful
maybe you have an alert message
for example you have one message which
says
typhoon warning on this date
and then you don't want somebody to
forge that message
you want to be able to check is this the
real message from the right person from
alice with the
the right public key and then you can
have another public key for tomorrow and
another public key for the next
day and so an alert message is something
that should be signed
for security and also once you
understand how empty messages are signed
then
it's actually not too hard to do longer
messages but just we'll just do
empty messages so here's the
key generation alice is taking some
random data the os.u random
from the operating system 32 bytes
256 bits of random data and
hashing those with sha 3 256 which is
in hash lib and well okay you have to
have sufficiently recent version of
python to have
shot 3 256 in hash lib and maybe say
hash lib.sha 3256 but this is all built
into
python python has the hash functions for
you
and then the important point is the
public key
alice's public key is the hash of
the random secret and then
alice well remembers the secret and
publishes the public key
as an example here's well making
one key pair from this sign empty and
it's just some random data
is the public key and some random data
is the secret key and the public key is
a hash
of the secret key and this public key
alice
announces everybody knows this public
key is from alice
and now let's sign a message
the signature of the empty message
is simply the secret
if alice wants to say okay alert
alice simply publishes the secret
and then if you want to check has this
message has the empty message been
signed you simply take this
signed message the secret from alice and
you hash it
and if it matches the public key then
okay you've got the empty message if it
doesn't match then you say
bad signature the only person who can
sign a message is alice because
alice is the only person who knows that
random secret
with the right hash everybody can check
and alice is the only person who can
make a signature
and then well this is just using these
functions and if you sign the empty
message
anybody can check and they get the empty
message back
if you try forging a message you have to
figure out the secret or figure out some
string which hashes to the public key
and
until alice reveals that secret that's
hard to do
you can only use this once because then
alice has revealed the secret and then
it gets more complicated so you should
look at
tonya's lectures on hash based
signatures and then you'll see how you
can do more
sign more bits of messages and sign
arbitrary length messages
and this was actually from a mini school
that was here in
july and uh okay you'll finish it up
so um just to give you some
recommendations
um these are absolutely unbiased
objective recommendations these are the
best post quantum systems that nist test
in its round three
which by definitions visual which by
definition
are exactly the systems that we and our
collaborators here in
academia seneca submitted so here are
the links
um these are one code based system so
that is the
encryption system going back to 1978.
rainbow is a multivariate signature
system
there's n2 prime which is a
lattice-based encryption system
and swings plus which is a hash based
signatures so four of the five
areas and exactly the four which i said
have been relatively well studied
we have submissions in the last round of
nist and we
do think that these are the future so
if you want to settle on something
before this finishes
this is our recommendation but of course
you should take a look at more things so
we have a whole bunch of more
information online
so please go there please look and well
try to break try to use and see whether
it fits
thank you for your attention
foreign
we have some bonus slides if you don't
want to ask questions we can keep you
busy for
several hours we have slides for how to
sign one bit message
we have slides for signing two bit
messages three bit messages
four bit okay somebody has a question
okay you have mentioned that
we have to panic because our message
will be revealed
in 10 years
as far as we know the uh our pro of
government is provide
in eid which use
isa 22048
as a core to suggest
the government to switch
the system such that we can avoid the
attack from the computers
so i think for everything which is
public key cryptography
for encryption where you need to ensure
secrecy so confidentiality for more than
10 years
i would recommend all the you in well
trying to deploy
postpartum encryption systems for
signature schemes
it's a different story signature schemes
matter at the moment when you check when
you verify whether the signature is
valid
at that point you must trust that nobody
has a quantum computer
so at the moment if you verify a
signature we don't believe that anybody
has a quantum computer
so we do believe that right now if you
verify an rsa signature
it is actually a valid signature so in
that sense you could say
signatures are less urgent we normally
encourage
people to already do use public key
the supposed quantum signatures now
because
typically you use signatures when you're
working on operating system updates and
so if the signature system is your way
to
change the cryptography behind it so if
you want to use it in order to
well update the system then you must be
sure that the
attacker doesn't have a quantum computer
yet when using it and so you're getting
into this
well what comes first problem so for
that
it helps to actually have postponed
signatures deployed
however it depends on how long the
lifetime of the product is if it's a
product
like a passport is only good for 10
years
so if in those 10 years we don't believe
a quantum computer
will have the power to break a signature
system then the first
batch of signatures sorry first batch of
passports will still be fine
but at some point you run into issues
where you have to make predictions about
the future
say passwords in five years you're
making a prediction about the future in
15 years
that the attacker doesn't have a quantum
computer and then
it gets unclear test test
okay we would like well there is there
are a few algorithms in the fourth or
third round of the nist competition and
one of them is from seneca and
it's it's really the pro of taiwan i
but i'm a crypto i'm student currently
studying in cryograph
cryptography but i must admit i
understand almost nothing
nothing and nothing like those things on
the side but
we would still like to contribute but
we have no idea what kind of way can we
contribute to the
whole to the whole thing or to the
algorithms that
cynical build like can we is there any
specs for us to follow or maybe we can
view
how how can we help help help writing
writing some codes on github to do some
maybe go
python or rust implementations or even
we can
just just a guess we can contact like
mtk or nd to build some
special specifically crafted
instructions inside the cpu to make the
cost of the of our scenic algorithm
more in the sense in a sense more cheap
is there any other ways that you
recommend us to
contribute to the the whole thing
so sorry sure of course you can
contribute by breaking some crypto
systems but you you sounded interested
in writing
software break the others
um yeah so there's a long answer for how
to get uh
how to get more information is well
there's lots of links to follow but the
short answer what you really should do
is talk to young boyin here because he
is
the master of making everything run fast
and he's been making multivariate
quadratic systems
and lattice systems and so on run really
fast
and he has lots of projects which are
projects that you can start on some of
them are
projects that you you i mean you need
programming experience but
no particular cryptographic experience
and then there's more advanced projects
if you're if you're through the initial
project
but it is very useful to have software
that is implementing these
cryptographic systems and then there's
more advanced challenges for example
testing the software it's not so good if
the software doesn't work
and then there's actually verification
systems you can try to have the computer
checking automatically that the
software works and there's more advanced
things but anyway
so talk to bayon yang and he will tell
you what the
top priority projects are
let me let me add a little bit of
advertisement if you want to learn more
about these systems
the last slide includes a bunch of links
and i'm still waiting for
the same person to come up with another
url
because the summer school he ran here in
july also has recordings
and then of course we have a lot more
time if you're only talking about hash
based signatures
for full hour so we can go into much
more detail than we could
covering the whole field of post quantum
cryptography and then trying to
highlight one little piece
so i mean we do have some of the slides
copied here but is a lot more
information
in the full slide set and his summer
school covered all the areas
and of course we are also happy to take
contributions for our systems not just
for bullions
and how
foreign
you