The year in postquantum crypto
Formal Metadata
Title 
The year in postquantum crypto

Title of Series  
Author 

License 
CC Attribution 4.0 International:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. 
Identifiers 

Publisher 

Release Date 
2018

Language 
English

Content Metadata
Subject Area  
Abstract 
The world is finally catching on to the urgency of deploying postquantum cryptography: cryptography designed to survive attacks by quantum computers. NIST's postquantum competition is in full swing,and network protocols are exploring postquantum extensions. This talk will take the audience on a journey through selected recent highlights from the postquantum world.

Keywords  Security 
Related Material
The following resource is accompanying material for the video
Video is cited by the following resource
00:00
Roundness (object)
INTEGRAL
Quantum cryptography
LipschitzStetigkeit
Musical ensemble
Quantum computer
Cryptography
01:14
Standard deviation
Projective plane
Nonstandard analysis
Cryptography
Field (computer science)
Elliptic curve
Word
Cryptography
Hacker (term)
National Institute of Standards and Technology
Statement (computer science)
Maize
Encryption
output
Quantum cryptography
Quantum computer
Quantum computer
Physical system
02:46
Rounding
Scripting language
Code
Multiplication sign
Electronic signature
Goodness of fit
Cryptography
Lattice (group)
Term (mathematics)
Different (Kate Ryan album)
Operator (mathematics)
Energy level
Ranking
Quantum cryptography
output
Quantum computer
Information security
God
Physical system
Compact space
Electronic mailing list
Nonstandard analysis
Bit
Instance (computer science)
Term (mathematics)
Cryptography
Flow separation
Sign (mathematics)
Prime ideal
Software
National Institute of Standards and Technology
Quantum cryptography
Encryption
Quicksort
Quantum computer
04:41
Scripting language
Rounding
Scripting language
Key (cryptography)
Cryptosystem
Multiplication sign
Direction (geometry)
Electronic mailing list
Parameter (computer programming)
Cartesian coordinate system
Electronic signature
Number
Sign (mathematics)
Message passing
Cryptography
Prime ideal
Different (Kate Ryan album)
Normal (geometry)
Ranking
Encryption
Information security
Physical system
Compact space
05:42
Building
Scripting language
Code
Cryptosystem
List of unsolved problems in mathematics
1 (number)
Numbering scheme
Electronic signature
Code
Mathematics
Goodness of fit
Cryptography
Lattice (group)
Encryption
Cuboid
Ranking
Nichtlineares Gleichungssystem
Category of being
Information security
Physical system
Compact space
Scripting language
Military base
Electronic mailing list
Code
Morley's categoricity theorem
Cryptography
Variable (mathematics)
Electronic signature
Sign (mathematics)
Category of being
Arithmetic mean
Prime ideal
Hash function
Lattice (group)
Quadratic equation
Order (biology)
Encryption
Multivariate Analyse
Quantum computer
Row (database)
08:00
Rounding
Web browser
Parameter (computer programming)
Cryptography
Lattice (group)
Bit rate
Different (Kate Ryan album)
Encryption
Authorization
Physical system
Exception handling
Compact space
Scripting language
Key (cryptography)
Instance (computer science)
Numbering scheme
Cryptography
Prime ideal
Error message
Lattice (group)
Pattern language
Right angle
Encryption
Figurate number
Information security
Communications protocol
Reading (process)
Quantum computer
Spacetime
10:00
Projective plane
Denialofservice attack
Line (geometry)
Cryptography
Cryptanalysis
Number
Latent heat
Word
Cryptography
Performance appraisal
Prime ideal
Selectivity (electronic)
Information security
Physical system
11:18
Service (economics)
Sound effect
Control flow
Denialofservice attack
Lattice (order)
Cryptography
Protein
Cryptanalysis
Number
Performance appraisal
Prime ideal
Cryptography
Information security
Information security
MaÃŸ <Mathematik>
Quantum computer
12:15
Combinational logic
Parameter (computer programming)
Mereology
Electronic signature
Cryptography
Roundness (object)
Lattice (group)
Bernstein polynomial
Befehlsprozessor
Encryption
Quantum computer
Information security
Vulnerability (computing)
Proof theory
Presentation of a group
NPhard
Adaptive behavior
Sound effect
Parameter (computer programming)
Numbering scheme
Term (mathematics)
Flow separation
Repeating decimal
Electronic signature
Band matrix
Proof theory
Message passing
Arithmetic mean
Befehlsprozessor
Process (computing)
System programming
National Institute of Standards and Technology
Compilation album
Encryption
Information security
Physical system
Resultant
Rounding
Dependent and independent variables
Control flow
Mathematical analysis
Plastikkarte
Shift operator
2 (number)
Computational physics
Telecommunication
Term (mathematics)
Internetworking
Band matrix
Form (programming)
RSA (algorithm)
Compact space
Vulnerability (computing)
Key (cryptography)
Mathematical analysis
Heat transfer
Code
Computer network
Denialofservice attack
Cryptography
System call
Similarity (geometry)
Estimation
Lattice (group)
Key (cryptography)
Quantum computer
Force
RSA (algorithm)
16:30
Email
Real number
Mathematical analysis
Computer network
Database
Denialofservice attack
Mathematical analysis
Term (mathematics)
Front and back ends
10 (number)
2 (number)
Cryptography
Roundness (object)
Software
Personal digital assistant
Partial derivative
Encryption
Information security
Information security
17:58
Web page
Information
Cybersex
Computer
Coma Berenices
Database
Cyclic redundancy check
Computer
Front and back ends
Chain
Cryptography
National Institute of Standards and Technology
Encryption
Information security
Block (periodic table)
Quantum computer
Summierbarkeit
Arithmetic progression
Quantum computer
19:05
Algorithm
Building
Physicalism
Mereology
Code
Data mining
Qubit
Vector space
Different (Kate Ryan album)
Quantum computer
Arithmetic progression
Traffic reporting
Quantum computer
19:58
Diskreter Logarithmus
Multiplication sign
Virtual machine
Information privacy
Vector potential
Field (computer science)
Cryptography
Hazard (2005 film)
Quantum cryptography
Communications protocol
Information security
RSA (algorithm)
Hazard (2005 film)
Cryptosystem
Virtual machine
Information privacy
Vector potential
Elliptic curve
Word
National Institute of Standards and Technology
Quantum cryptography
Encryption
Information security
RSA (algorithm)
Quantum computer
Electric current
20:57
Scripting language
Instance (computer science)
Cartesian coordinate system
Cryptography
Electronic signature
Publickey cryptography
Cartesian coordinate system
Electronic signature
Revision control
Graphical user interface
Quantum cryptography
Quantum computer
Physical system
21:50
Dot product
Graph (mathematics)
Mathematical analysis
Cryptography
Cartesian coordinate system
Electronic signature
Publickey cryptography
Cartesian coordinate system
Electronic signature
Elliptic curve
Graphical user interface
Different (Kate Ryan album)
Gravitation
Energy level
Information security
22:49
Overhead (computing)
Graph (mathematics)
Code
Ciphertext
Sampling (statistics)
SchlÃ¼sselverteilung
Cartesian coordinate system
Isogenie
Electronic signature
Cartesian coordinate system
Cryptography
Term (mathematics)
Encryption
Physical system
23:47
Inheritance (objectoriented programming)
Cryptosystem
Mathematical singularity
Mobile Web
Zoom lens
1 (number)
Median
Web browser
Number
Cryptography
Lattice (group)
Different (Kate Ryan album)
Internetworking
Energy level
Data structure
Information security
Free variables and bound variables
Overhead (computing)
Inheritance (objectoriented programming)
Ciphertext
Web page
Control flow
Cryptography
Publickey cryptography
Connected space
Category of being
Graphical user interface
Estimation
Lattice (group)
Quantum computer
25:21
Web page
Inheritance (objectoriented programming)
Divisor
Mathematical singularity
Mobile Web
Median
Computer
Local Group
Cryptography
Lattice (group)
Internetworking
Googol
Configuration space
Data structure
Information security
Physical system
Free variables and bound variables
Link (knot theory)
Web page
Control flow
Publickey cryptography
Mechanism design
Category of being
Estimation
Lattice (group)
Free variables and bound variables
Quantum computer
26:57
Multiplication sign
Student's ttest
Web browser
Electronic signature
Area
Graphical user interface
Roundness (object)
Googol
Hash function
Data structure
Quantum computer
Physical system
Standard deviation
Link (knot theory)
Boilerplate (text)
Group action
Numbering scheme
Electronic signature
Elliptic curve
Process (computing)
Internetworking
Hash function
Lattice (group)
Abelian category
Resultant
Electric current
Quantum computer
28:13
State of matter
1 (number)
Numbering scheme
Insertion loss
Numbering scheme
Cartesian coordinate system
Electronic signature
Cryptanalysis
Publickey cryptography
Variance
Electronic signature
Local Group
Revision control
Web application
Message passing
Internetworking
Lattice (group)
Lattice (group)
Operating system
Normal (geometry)
Energy level
Abelian category
Information security
Physical system
29:32
Metric system
Ciphertext
Open source
Cryptosystem
Mathematical analysis
Field programmable gate array
Encapsulation (objectoriented programming)
Cryptanalysis
Asymptote
Variance
Time domain
Revision control
Coefficient
Lattice (group)
Software
Data conversion
Encryption
Information security
Implementation
Sinc function
Pulse (signal processing)
Physical system
30:30
Goodness of fit
Encapsulation (objectoriented programming)
Time domain
Mathematics
Goodness of fit
Cryptography
Internetworking
Software
Encryption
Matrix (mathematics)
Implementation
Information security
Physical system
Identity management
Electric generator
Key (cryptography)
Ciphertext
Cryptosystem
Field programmable gate array
Encapsulation (objectoriented programming)
Asymptote
Cryptanalysis
Publickey cryptography
Message passing
Personal digital assistant
Data conversion
Encryption
Key (cryptography)
Information security
Matrix (mathematics)
Identity management
Quantum computer
31:30
Mobile Web
Key (cryptography)
Multiplication sign
Mereology
Goodness of fit
Wave packet
Band matrix
Cryptography
Band matrix
Matrix (mathematics)
Encryption
Right angle
Key (cryptography)
Encryption
Matrix (mathematics)
Identity management
Identity management
32:38
Context awareness
Server (computing)
Key (cryptography)
Server (computing)
Ciphertext
Transport Layer Security
1 (number)
Client (computing)
Denialofservice attack
Client (computing)
Particle system
Cryptography
Readonly memory
Semiconductor memory
Band matrix
Operator (mathematics)
Personal digital assistant
Key (cryptography)
Message passing
Communications protocol
33:50
Server (computing)
State of matter
Multiplication sign
Data storage device
Function (mathematics)
Client (computing)
Graph coloring
Web 2.0
Exclusive or
Mathematics
Cryptography
Readonly memory
Bernstein polynomial
Semiconductor memory
Internetworking
Encryption
Matrix (mathematics)
Integrated development environment
HTTP cookie
Position operator
Physical system
Key (cryptography)
Server (computing)
Data storage device
Client (computing)
Computer network
Bit
Limit (category theory)
Similarity (geometry)
Partition (number theory)
Category of being
Internetworking
Resource allocation
Integrated development environment
Partial derivative
Normal (geometry)
Summierbarkeit
Encryption
Key (cryptography)
HTTP cookie
Odds ratio
Matrix (mathematics)
Resultant
Quantum computer
Spacetime
36:30
State of matter
Client (computing)
Parameter (computer programming)
Cryptography
Roundness (object)
Bernstein polynomial
HTTP cookie
Sanitary sewer
Physical system
Scripting language
Compact space
Menu (computing)
Complete metric space
Flow separation
Simulated annealing
Band matrix
Partition (number theory)
Mechanism design
National Institute of Standards and Technology
Compilation album
Block (periodic table)
Resultant
Rounding
Server (computing)
Cybersex
Data recovery
Data storage device
Computer
Rule of inference
Number
Machine vision
Chain
Readonly memory
Statement (computer science)
Compact space
Key (cryptography)
Information
Server (computing)
Computer network
Client (computing)
Core dump
Cartesian coordinate system
Similarity (geometry)
Resource allocation
Statement (computer science)
Partial derivative
HTTP cookie
Matrix (mathematics)
Quantum computer
38:30
Inclusion map
Pointer (computer programming)
Execution unit
Randomization
Greatest element
Electronic data interchange
Interior (topology)
National Institute of Standards and Technology
Information
Instance (computer science)
Rule of inference
Installable File System
39:32
Random number
Cryptosystem
Mathematical analysis
Field (computer science)
RegulÃ¤rer Ausdruck <Textverarbeitung>
Thermische Zustandsgleichung
Inclusion map
Type theory
Pointer (computer programming)
Mathematics
Lattice (group)
Ring (mathematics)
Order (biology)
IRIST
Convex hull
Information
Curve fitting
40:27
Email
Slide rule
Random number
Execution unit
Multiplication sign
Physical law
MIDI
Mathematical analysis
Field (computer science)
Cartesian coordinate system
Valueadded network
Data mining
Pointer (computer programming)
Personal digital assistant
Hardwareintheloop simulation
Convex hull
Hill differential equation
Information
41:24
Rounding
Commutative property
Group action
Distribution (mathematics)
Combinational logic
Computer
Ellipse
Group action
Publickey cryptography
Mathematics
Modulo (jargon)
Chain
Cryptography
Frequency
Shared memory
Computing platform
Lorenz curve
Key (cryptography)
Block (periodic table)
Normal (geometry)
Abelsche Gruppe
Reading (process)
Quantum computer
42:49
Commutative property
Group action
Multiplication sign
Ellipse
Computer
Field (computer science)
Element (mathematics)
Mathematics
Cryptography
Different (Kate Ryan album)
Singleprecision floatingpoint format
Shared memory
Square number
Lorenz curve
Normal (geometry)
Quantum computer
Physical system
Form (programming)
Dependent and independent variables
Bit
Group action
Cryptography
Publickey cryptography
Elliptic curve
Modulo (jargon)
Mathematics
National Institute of Standards and Technology
Key (cryptography)
Abelsche Gruppe
Quantum computer
44:27
Commutative property
Ellipse
Computer
Mathematics
Cryptography
Operator (mathematics)
Shared memory
Square number
Lorenz curve
Normal (geometry)
Modulo (jargon)
Curve
Addition
Multiplication
Key (cryptography)
Planning
Division (mathematics)
Instance (computer science)
Group action
Isogenie
Publickey cryptography
Elliptic curve
Modulo (jargon)
Mathematics
Key (cryptography)
Object (grammar)
Quantum computer
45:20
Commutative property
Multiplication sign
Ellipse
Lattice (order)
Number
Prime ideal
Cryptography
Root
Shared memory
Square number
Lorenz curve
Spacetime
Normal (geometry)
Information security
Curve
Key (cryptography)
Mathematical analysis
Plastikkarte
Bit
Lattice (order)
Group action
Publickey cryptography
Elliptic curve
Modulo (jargon)
Mathematics
Quantum cryptography
Key (cryptography)
Information security
Quantum computer
46:34
Point (geometry)
Intel
Greatest element
Algorithm
Code
Control flow
Shift operator
Lattice (order)
Number
Cryptography
Population density
Readonly memory
Military operation
Software
Spacetime
Quantum computer
Information security
Physical system
Curve
Multiplication
Key (cryptography)
Kolmogorov complexity
Point (geometry)
Mathematical analysis
Core dump
Bit
Cryptography
Publickey cryptography
Similarity (geometry)
Elliptic curve
Proof theory
Order (biology)
Right angle
Key (cryptography)
Information security
Advanced Encryption Standard
Quantum computer
Laptop
Electric current
48:59
Intel
Key (cryptography)
Code
Multiplication sign
Moment (mathematics)
Core dump
Complex number
Similarity (geometry)
Data mining
Cryptography
Readonly memory
Military operation
Software
Key (cryptography)
Website
Information security
Laptop
Electric current
Quantum computer
49:55
Cybersex
Code
Cryptosystem
Multiplication sign
Cryptography
Publickey cryptography
Chain
Goodness of fit
Cryptography
Software
Time evolution
Software
National Institute of Standards and Technology
Musical ensemble
Block (periodic table)
Quantum computer
Mathematician
Bounded variation
Quantum computer
51:21
Web page
Axiom of choice
Implementation
Link (knot theory)
Code
Primitive (album)
Function (mathematics)
Latent heat
Cryptography
Roundness (object)
Different (Kate Ryan album)
Operator (mathematics)
Software
Energy level
Software framework
Information security
Computing platform
Physical system
RSA (algorithm)
Beer stein
Multiplication
Interface (computing)
Code
Instance (computer science)
Cryptography
Benchmark
Performance appraisal
Software
File archiver
National Institute of Standards and Technology
Software framework
Website
Library (computing)
54:01
Functional (mathematics)
INTEGRAL
Length
Transport Layer Security
Microcontroller
Primitive (album)
Open set
Field programmable gate array
Parameter (computer programming)
Arm
Formal language
Cryptography
Software
Quantum computer
Arm
Inheritance (objectoriented programming)
Key (cryptography)
Interface (computing)
Projective plane
Code
Field programmable gate array
Bit
Cryptography
Publickey cryptography
Electronic signature
Message passing
Loop (music)
Pointer (computer programming)
Hash function
Factory (trading post)
Software framework
Quantum computer
Library (computing)
55:32
Functional (mathematics)
Inheritance (objectoriented programming)
Length
Code
INTEGRAL
Transport Layer Security
Numbering scheme
Set (mathematics)
Function (mathematics)
Open set
Rule of inference
Usability
Cryptography
Different (Kate Ryan album)
Encryption
Software testing
Data conversion
Quantum computer
Physical system
Key (cryptography)
Projective plane
Code
Usability
Cryptography
Electronic signature
Message passing
Software framework
output
Communications protocol
Quantum computer
Library (computing)
57:16
Random number
Implementation
Scripting language
Machine code
Code
Function (mathematics)
Mereology
Formal language
Software bug
Publickey cryptography
Programmer (hardware)
Sign (mathematics)
Cryptography
Cache (computing)
Formal verification
Computer hardware
Energy level
Message passing
Information security
Address space
Exception handling
Physical system
Computer virus
Data recovery
Interface (computing)
Cartesian coordinate system
Cryptography
Publickey cryptography
Open set
Electronic signature
Sign (mathematics)
Message passing
Hash function
Software
Function (mathematics)
Interface (computing)
output
Formal verification
Software testing
Condition number
Fiber bundle
Mathematician
Exception handling
Writing
RSA (algorithm)
Library (computing)
1:00:37
Trail
Code
Confidence interval
Mereology
Number
Cryptography
Cache (computing)
Befehlsprozessor
Formal verification
Quantum computer
Beer stein
Focus (optics)
Code
Bit
Volume (thermodynamics)
Term (mathematics)
Symbol table
Compiler
Condition number
Software testing
Volume
RSA (algorithm)
Quantum computer
Reduction of order
Library (computing)
1:01:32
Classical physics
Key (cryptography)
Bernstein polynomial
Code
Electronic mailing list
Mathematical analysis
Musical ensemble
Instance (computer science)
Code
1:02:31
Overhead (computing)
Algorithm
Key (cryptography)
Computer file
Code
Optimization problem
Ciphertext
Cryptography
Code
Electronic signature
Number
Bernstein polynomial
Singleprecision floatingpoint format
Encryption
Quantum computer
Physical system
1:03:31
Point (geometry)
Algorithm
Building
Physical law
Instance (computer science)
Cryptography
TuringMaschine
Computer
Rule of inference
Usability
Hadamard matrix
Cryptography
Bernstein polynomial
Quantum mechanics
Universe (mathematics)
Matrix (mathematics)
Endliche Modelltheorie
Quicksort
Quantum computer
Logic gate
Quantum computer
Physical system
1:05:08
Algorithm
Key (cryptography)
Electronic mailing list
Bit
Computer
Elliptic curve
Medical imaging
Sign (mathematics)
Cryptography
Bernstein polynomial
Internetworking
Telecommunication
Encryption
Quantum cryptography
Quantum computer
Quantum computer
Physical system
1:06:05
Inheritance (objectoriented programming)
Multiplication sign
Mathematical singularity
Mobile Web
Execution unit
1 (number)
Median
Arm
Field (computer science)
Number
Usability
Local Group
Cryptography
Bernstein polynomial
Software
Software testing
Configuration space
Information security
Free variables and bound variables
Web page
Code
Field programmable gate array
Control flow
Band matrix
Befehlsprozessor
Estimation
Lattice (group)
Software framework
1:07:00
Axiom of choice
Link (knot theory)
Constraint (mathematics)
Observational study
Cartesian coordinate system
Cryptography
Area
Graphical user interface
Lattice (group)
Bernstein polynomial
Googol
Telecommunication
Singleprecision floatingpoint format
Lattice (group)
Information security
Electric current
Quantum computer
1:08:13
Multiplication sign
Computer
Field (computer science)
Area
Usability
Graphical user interface
Roundness (object)
Googol
Operator (mathematics)
Scalar field
Computer hardware
Information security
Physical system
Form (programming)
Multiplication
Link (knot theory)
Moment (mathematics)
Mathematical analysis
Generic programming
Bit
Isogenie
Elliptic curve
Lattice (group)
Electric current
Quantum computer
1:09:34
Sic
Cartesian closed category
Musical ensemble
Semiconductor memory
00:03
[Music] the next talk is called the yen post quantum crypto by Daniel anger please researching in Eindhoven and Daniel Bernstein researching at the University of Chicago they both have the first ever conference on post quantum cryptography in 2006 and they both contributed to the
00:42
lips old crypt robbery their talk is going to be a summary of Dean and his post Khan crypto competition and they're gonna provide an overview of problems of post corner cryptography and hopefully just how to integrate post common crypto in existing software please welcome them with a huge round of applause
01:15
all right well thank you first of all this title word post cognate ography
01:20
what it means we're talking about cryptography were we're designing the
01:25
systems under the assumption that our H
01:27
hacker not the user just the attacker has a large quantum computer also to remind you from three years ago when he showed you the attacker we talked about attackers all right so we're seeing like
01:44
over the last few years 2015 say middle August there was a big announcement by the NSA saying oh yeah actually the world should care about postconflict ography we need more research they finally wake up to it and that should I had a nice rollout of fact that pretty much every agency just highlight three of them here so UK the Netherlands and the NSA themselves made some statements about the urgency of rolling out post quantum that normal cryptography that are currently using so elliptic curves and RSA diffiehellman find fields will be broken soon as a quantum computer and the NIST which is the National Institute for Standards and Technology so it's an institute in the US which is working on standards said okay we're gonna call for it sanitization project for post choreography so yes it's us institution but it has in cryptography a mostly get in good history they have been writing competitions which gave us a s they've been running competitions which gave us a three and they also without a competition gave us dual EC so
02:47
competitions was NIST good thing everything else well judge for yourself this sounds like a great story it's also a little bit disappointing when you look at XI where it started so back in 2003 then he appoint the term post quantum cryptography and then they've been running around for 10 years ago like the end is nigh please invest in post pocket Agra we do something just
03:08
that 10 years later the NSA says oh my god we have to do something quantum computers are counting so it's a little bit yeah I told you so not a great story but alright so what happened with this competition
03:21
well after said hey everybody send us some proposals for post quantum crypto to standardize a lot of people did so they said actually more than 80 submissions
03:32
came in and some of them were incomplete like one of the requirements was include software and whatever reasons they said
03:38
some of the submissions are not complete but they posted 69 complete submissions the submission teams include 260 people from around the world all sorts of academia industry maybe even some government people there's lots and lots of names and we're not going to go through like what all these things are but we are going to say 60 minutes oh that's one okay so big quake this is a code based system no we're gonna give you some idea of like what the big picture is of how well these things have held up so these were all posted  on the 21st of December last year and some of you saw our lattice hacks talk last year remember that this list already there was some damage to it by the time of our talk on the 28th of December 2017 by the end of the year there were eight submissions that had attacks at different levels of severity I should explain the color coding here the stuff that's in brown is less security than claimed which could be for instance they claim something was it would take 2 to the 128th operations to break and somebody says no it's 2 to the
04:43
hundred or two to the 80 well does that really matter or maybe a different direction if somebody says this is a system where you can reuse the key any number of times which we expect for for normal crypto systems that you can publish your key and people can keep sending you messages or you can sign many times under some keys but sometimes people claim they had that feature and if they turned out to be wrong that those were attackable like gila 5 in this list which is not necessarily kicking them out of the competition because nist said you can have a system with onetime keys that can be useful for some applications the things in red are everything that they proposed all
05:19
the concrete parameters are broken the underlines are those where there's attack scripts Python scripts cage scripts whatever it takes to demonstrate that yeah look here's here's your secret key or decrypting something so that was the end of 2017 how about now well okay how let's extrapolate three days from now probably the situation is at least the following at least by 28th of December
05:45
2018 22 submissions have attacks so it's about a third of the 69 submissions and you can see more wealth most well 13 of those out of the 22 are read mostly with underlines I think some of this is from us a lot from other people and I think we did well early on establishing that people should put out scripts to demonstrate that yeah you really can break these things so again the underlines are demonstrated attacks some of the submitters have withdrawn the broken submissions some of them have not all right so when you look at this it's been said we're not going to go through explaining those but let me categorize these so when we look at the ones which are not completely smashed and broken we can put them into boxes we can say hey what is the underlying mathematical problem what do we hope is something the attacker has to do in order to break the crypto system and then there's one category of using Eric writing codes which is then used for either building an encryption system or signature scheme hash functions you can only build signature schemes from a certainty based crypto for the competition we're only seeing an encryption system and honestly all the signatures we have seen so far are pretty inefficient that is this VC verbose that is something we talked about last year so if you want to get a fullblown letters explanation go for last year's talk and then finally there's something using systems in many variables many equations and we get signatures and encryptions from that so that's one way of saying well these are good things for post one it does not mean that everything which is in this boxes is secure you can still design a system which somehow relates to this math problem but the attacker can do a way around some of those systems records I'll get back to later is a code base system code bases on the list first one up there so she'll be totally secure and yet it's one of the red underline systems so just being in one category categories does not mean it's secure but it's at least some hopeful helpful thing to box things there are the ways of describing why this is the situation we
07:56
have now as an example of this kind of categorization sometimes people might say Oh lattice based cryptography is the
08:03
safe thing to do all that read was people who were not using lattice based cryptography and everything lattice
08:09
based is good everything else is scary but if you look at the lattice based systems it's not all black there's some red stuff here compact lwe that one is broken where the script were quite sure it's broken there's some others with some damaged ers vo5 so it's not that the lattice based submissions have held up perfectly and also it's not just that these are isolated mistakes that people have made there's ongoing research which is making better and better lattice
08:35
attacks for instance some papers from last month and this month from the three authors listed there are talking about lattice based systems being broken by decryption failures now this phenomenon most of the latus submissions have occasional decryption failures once every two to the 64 ciphertext maybe you won't be able to decrypt which might sound like oh it's no big deal it's it's maybe occasionally you might have some user has that happened and they'll just the browser will reconnect whatever it takes it's not a significant failure rate except that those failures if the attacker is trying to decrypt a particular ciphertext or maybe even attack a figure out somebody's secret key they can usually get that information out of watching the pattern of decryption failures if decryption failures happen often enough and these papers are saying for two different reasons decryption failures are actually happening more often maybe much more often than people claim so that's kind of scary all right one explanation which I of course like very much I've been running a European protocol pick a crypto and just use everything in our portfolio it's good right actually it's looking better than the arguments saying I'll use everything letter space we have one which is slightly scratched but everything else is good right okay except well there's another explanation
10:02
than just well whoever these PQ crypto project people are obviously the right people putting together a great portfolio there's another possibility not saying this is right but you could imagine that crypt analysts who are deciding what to do out of that huge
10:17
pile of 69 submissions maybe they thought the people who were in this project doing this stuff for some number of years are maybe not the top targets maybe you should look at the other 49 submissions maybe you should look at the submissions with the specification written in Microsoft Word probably more likely to be broken maybe there's other ways that you can decide how to no worse than Microsoft people uh yeah that did work coincidentally I yeah so the thing to keep in mind is that there's a huge
10:50
pile of submissions more than a million words in these 69 submission documents and this is like a word in English is usually a kind of imprecise thing reviewing that this is I would say more effort than reviewing a million lines of cook this is a lot of stuff a lot of junk to go through there's a real flood there's too much for us to all the people who care about attacking systems to actually go through everything so people are making a selection and maybe they just haven't bothered looking at these pica crypto submissions so if you
11:19
if you want to actually have security review it's really important to keep this denial of service effect in mind that the the flood of submissions has to be small enough that it can be handled by the number of people who are looking at these submissions and evaluating the security so call for help please join
11:35
please break don't break hours now one thing which in this audience is a little funny but in a normal academic conference we talking to like a 40 or 100 people we like we actually have a lot of people now being interested in post cryptography but this was this
11:53
year's conference on this when Dell and I started this in 2006 we're looking at the audience of 40 this is 350 people well they would probably fit in here but well for academics this is big there's a
12:05
huge interest right now this was the combined conference together with a nist workshop and so people are looking so that's the good news there's more than enough service going Rocco's already as one vicious protein
12:18
but not withdrawn broken actually three different ways where our last message to them was basically abandon all hope this is not going to work but they keep on hoping if i zoom in there they have
12:29
they're on the way to publishing new parameters when he was reading it out actually at the conference he was saying the keys and signatures eyes maybe several dozens of terabytes well there is some effect that we're most like not going to break it so easily because when you try to download several terabytes of data it might not reconnect so this is certainly aware of the fact that there's just it's denial of service on security analysis and one of the ways that they tried to simplify the picture it said all right after the conference they put out this call saying all right if you have similar submissions see if you can merge them and then hopefully you get something which is you know going to be a combined submission that's that's easier for us to analyze them these two separate submissions in the first place and they said this is an interesting little guarantee they said NIST will accept emerged submission to the second round if either of the submissions being merged would have been accepted so you can imagine kind of attacking this if there's a strong submission and you have a weak submission like the strong one they and they surely have to accept that and then you merge your weak submission into the strong one if you can somehow convince the other team to do that then your weak submission is also going to get into the the second round but NIST said well alright you should only merge submissions that are similar and the merged submission should be like a combination of the the two original submissions so that sounds kind of reasonable I example while the first announcement of a merger I don't think NIST said that you have to publicly announce but he'll of five merged with round two and of course this was after the heel of five attack and part of the merger was fixing the issue in that attack and they formed round five and they said round five this result of the merge is a leading lattice based candidate in terms of security bandwidth and CPU performance so three weeks later the security turned out to be kind of a problem Mike Hamburg said that here's a very strong reason to believe that decryption failures are much much more likely than what they claimed and as a result of that and they they accepted the argument and said yet whoops as a result of that like I mentioned before decryption failures are something that attackers can use to break security and it's not that that a full attack was implemented but it's pretty clear that the attack would work and this is also interesting attack because the mergers were supposed to be just taking like take the best features of your two submissions that you're merging but this was a mistake the vulnerability that Hamburg exploited was a mistake that was not in either of the submissions that were being put together so there's some process of a break and fix and merge and making more mistakes which get broken and then fix and what was the fix they said I'll here's a proposed fix they're looking at the security proof adjustments there will be a round five real proposal their actual merge will be in the future I think now they have round five a round five B and round five C where a is broken B is questionable C is still not defined what is a security proof what is a security proof mean if you have a security proof previously that they were adjusting and the security proof is for something that is not actually secure very strange more merger announcements post quantum RSA encryption and post quantum RSA signatures merged to form post quantum RSA saying that that is a leading candidate in terms of depth of security analysis amount of network traffic and flexibility for people not familiar with post quantum RSA this means using RSA with gigabyte or terabyte keys which is leading in the amount of network traffic we want the internet to have as much cryptography as possible use more bandwidth yeah remember you
16:32
have if you're measuring the amount of encrypted data on your network this increases that imma I more mergers more mergers more mergers some of these are kind of gluing submissions together in a
16:43
way that does not simplify the the security analysis but this last one is a
16:47
good example I would say of emerge enter H or SS and enter encrypt two of the entry based submissions they actually put some thought into what they wanted to keep and what they want to throw away and so the analyzing the merge is easier than analyzing the both of the initial submissions after the November deadline for mergers Nest said they will announce the second round candidates maybe it'll be probably less than 30 some hints it will be 25 or even 20 I candidates and maybe that's starting to get down to a small enough flood that we can start seriously analyzing what's left they're going to announce that I think on exactly January 10th they're scheduled to do that and then a week after this announcement they said well the government might be shutting down and in that case we're not allowed to do any work so we're going to be completely silent in case of the shutdown it's important in the US government during shutdowns there's a definition of essential personnel like NSA and nonessential personnel like people protecting us against NSA and only the essential personnel are allowed to do work you know what else is not allowed to do work the back end database for
17:59
NIST web pages which might sound a little bit weird although maybe they're paying Oracle for the back end database and they have to turn off the payments or cool I don't know what's going on here but they if you look for the competition information you can't find it on their web pages anymore I we're not quite sure how long the
18:22
shutdown is going to last of course there are some people who say that this is not a problem because we can figure
18:31
out without this competition how to protect ourselves again
18:35
squonk encrypt all right now that we have aliens already our Quan computers actually coming big question we don't know what we can monitor is progress in quantum computing and just mid of
18:48
December there was a news item from inq which is a small startup company announcing their largest ever quantum computer based on iron traps all the other quantum computers we've seen so far which other of this size like 40 to 70 they were using superconducting
19:05
qubits so it is again a race between different technologies but both of them are advancing and there some more which are growing so it looks like it's coming whenever I seen a picture like this a reminder of a nice joke from a colleague of mine Stephen Galbraith
19:26
can you distinguish yep so with all
19:31
these news coming up the National Academy of Sciences in the US has been interviewing people for the last about yearandahalf so they got people in physics and engineering building quantum computers people doing quantum algorithms people doing quantum vector correcting codes and putting all of this together into a report which this came out where they look into well what are the progress and what the prospects so the first part I have key findings the first one is the good news saying don't panic we do not expect that
20:01
anything is going to happen in the next ten years which will threaten RSA 2048 or similar where I assume what I mean while elliptic curves discrete log and fine field so that's a good news but
20:15
they only don't have just one key finding it actually goes on two to three ten by the time they reach ten I think
20:22
this is panic so as I say as well it takes forever to roll all these things it's a hazard of such a machine is high enough and then the deployment of post quantum cryptography is critical for minimizing the chance of a potential security and privacy disaster these are
20:40
strong words from the National Academy of Sciences so okay can we deploy post
20:46
quantum cryptography is it deployable well some people would say we've already deployed it but maybe that doesn't include the NIST submission so let's look at the deploy ability of the nest
20:58
submissions the main thing that matters for deployment in most applications the main problem for post quantum cryptography is the sizes so here's a picture of the night sky over live session now this is a picture of on the
21:13
horizontal axis is the size of your public key for a bunch of signature systems not all of the signature systems for instance walnut DSA which is broken with a script in the first five versions a post quantum RSA is also emitted from this sorry enough oh yeah that would be I'm one of the designers of post quantum RSA by the way it's the future of cryptography that was good I yeah so what you can see here is for example this GUI submission this has you can get
21:51
your your vertical as the signature size down to just 32 bytes or 35 bytes or something like that but you need this is something like 400,000 bytes in your public key and then there's three different dots for GUI those are three different security levels and maybe the different
22:07
submissions here are maybe not exactly comparable in the security levels it should be a threedimensional graph if we measure everything properly by exactly how secure it is which of course we're not quite sure about until there's been enough security analysis you can see various different tradeoffs are possible none of which are down where we want to be with things like under a hundred bytes for your public key and under 100 bytes for your signature which is what we're used to right now that's what elliptic curve cryptography sizes which are both below a hundred bytes and that's something you can fit into your applications much more easily than say a hundred thousand byte public keys or ten thousand byte signatures there's various
22:49
different tradeoffs and maybe your application can handle some of that but there's nothing that's just really small which is what we're used to right now another more complicated graph this is
22:59
for encryption and showing more candidates why there are more encryption submissions this is still not all of the encryption submissions but representative sample and you can see that well there's still no really great sizes here the best in terms of sizes is psych super singular isogen e key exchange which is something like 400 little less than 400 bytes for the
23:25
public key and for the ciphertext and then it starts getting bigger from there and you get on this graph you get things up to megabyte or bigger you can get a little below 3 400 bytes you can get down to a hundred or so bytes for the ciphertext as long as you are willing to accept a public key that's much much bigger with some of these code base systems and then just to zoom in on some
23:48
of the smaller ones you can start seeing where some different candidates are this is everything which is public key and cypher text below 1280 bytes and again
23:59
you see psych down there little below 400 bytes and then some other possibilities but what are the security levels of these things could all of
24:08
these be broken there's not actually that many of them how many of these have actually been studied it's kind of scary and again much bigger sizes than were used to in cryptography so yes size does matter so googling CloudFlare this year in
24:24
April we're saying well we don't really know what the outcome of this competition is going to be but we have some categories of different crypto systems and let's just send dummy packets of data of respective sizes and see what happens when we do this on the internet now this is Google and CloudFlare so they were doing this on the Chrome browser for connections like occlude through CloudFlare so they could actually see from when I came where to ended where they came back as I dropped then mentioned psyche so this is the one category of super single I saw two nice those are just 400 bytes and that was pretty much fine so when you look at the first column you have a small agency increase you also see the inaccuracy there's a minus 0.2 so the numbers are mostly correct then there is in the lattices this was a zoom in what then was showed those are mostly something the category of structured lattices those are around the empty use so one hundred thousand two hundred something
25:22
bytes and that was mostly worked some small increases about under 20% so this is also something you may feel like yes you could actually deploy this on the Internet then a different category is still within lattices are unstructured lattices those would come with 10 kilobytes of data for the public key and there they just notice that too many pages including like top pages on the lexa 500 such as LinkedIn were just dropping they tried funny enough 9090 99 were fewer pages dropping so 10k was worse than 9,000 9.99 but he then linkedin was still dropping and so that they crease it to a third as basically a placeholder measured with these 3,300 bytes and then scaled up by a factor of three now those increases in the latency is what they said well this is not acceptable so then for the next experiments they were only looking at I saw two knees in structured lattices and such a knees are also special not just being the smallest but also being the slowest well okay not absolutely the slowest but it's the only system where the speed is much more an issue than the size and so despite Google having quite a few computers they were saying we can't actually use ISO Jenice for the speed reasons size would be awesome but speed not so sure it's also a relatively recent systems just from 2012 so maybe also it's a security question so just
26:54
now in December they were announced they actually building a new experiment they
26:58
announced which candidate they have chosen and 2hrs S which dentist mentioned was also one of the recent mergers and so this is one of the structured lattices systems designers are and has losing use  I know Feld Peter Schwab and Nancy a great score for Eindhoven team turned professor former student and then some collaborators and
27:19
so they're now building a system which is a combined elliptic curve so that's the combined team that's command elliptic curves and post qualm this is the second round running and so this
27:32
will come to some internet browser near you soon another nice result  it's not the only thing up there the ITF this year finished standardizing X MSS which is a hash based signature system um it's been in the making down there used to the Time Bandits been making for three years it's not really fast but it's also
27:49
the first of its kind this was the first time that ITF has published a post quantum are of seam requests for comments but that's basically their standards and so there's a lot of boilerplate text which was developed in this thing in the process of making the standard which is dealing with yeah post quantum quantum attacks and so on how should handle it XM SS is interesting it's not on earth earnest submissions because it
28:13
satisfy the normal thing that you learned in primary school what a signature should be doing signature you expect you have a public key you use it to sign something and then you have a signature X MSS you have a public key you have a state you get a message you sign it and you update your state and you've ever forget to update your state you will lose security so it's something which is not as cool as a normal signature scheme but there are so many applications will you actually know how many signatures you've made I mean if you're doing operating system updates you better know how often you got your key out of the drawer and used it so it is not impossible to use but it might not be exactly what you want for your web applications still if you can count them much smaller than the signature systems another size advantage size
29:08
advance is something called glowstick I should explain the name this is starting from a lattice submission called Sabre which is one of the unbroken ones and Sabre has a big version called fire Sabre high security level scaledup it also has a small version called light saber and this glow stick is the even
29:33
smaller version it's like let's scale it down as far as we can get that it's not quite broken and there's various technical details and it hasn't been
29:42
broken in the months since it's been proposed that six months or so and it is interesting I mean it's something which is a good challenge it's it's nice to have these scaleddown problems so we can try different ways of attacking these things and people who like breaking stuff it's good to have the simpler systems to to practice doing attacks and that gives you some insight into what could work against the larger systems all right so since we're coming
30:07
to funny names oh no since they come in two sizes why do we still care about big sizes I mean people are scaling things down Google says oh we don't like big sizes so why do people say post phone systems are bigger and we still care about it so one of the reasons is well highlighting mcLeese here which is our submissions to this competition these have had a lot of analysis so classic mcLeese is based on
30:32
a system from 1978 basically unchanged except for some changes where we can really prove this is the same as that it has one of the shortest cipher texts just 200 bytes so that's actually kind of tolerable on the internet but a megabyte of key key generations also put it slow but then the well it's nowadays called encapsulation decapsulation because all you want is your AS key you don't want to actually encrypt the message but basic thing of encryption and decryption of that so nice system very good history and security pretty fast pretty small except for the public keys it's like grandma why do you have so big case why are these keys so big so one thing is it's like a two dimensional key we have there's big matrix there what
31:22
you see on the left is an identity matrix this thing has about seven thousand columns this is like pretty long it's only but the height is n minus K which
31:33
is just like thousand five hundred so it's really long and stretched and so all of this part on your right hand side that part is random and you have to send that you can of course everybody remembers what the identity matrix looks like you can't forget about this one but this one you have to send because the encryption works by the sender thinking which of those around 7,000 column you want to pick and then just X oaring them up and for doing that well you need to have this big matrix and if you calculate well thousand five hundred forty seven times five thousand four hundred thirteen that's the part of the right matrix you're getting to this one megabyte size now what are the issues was having big keys its bandwidth but honestly when you download a pictures also megabytes early it might not be so bad I mean if you're on the German trains then you will hate it but
32:32
normally also in the world or honey mobile it's fine Google was saying her we actually
32:41
excluded Samson so they didn't experiment was classic McAleese largest the look that was 10,000 kilobytes and even then some dropped and they said well some are too large to be viable within TLS so they just said well we don't do this but then again you have a secure system you can just also design a secure protocol to go with it we don't need to stick with TLS but there's a real problem was having a megabyte of a megabyte of key because if your particle assumes that the client generates there's 1 megabyte and then just throws it at the server and the server has to accept 1 megabyte from every single client that is throwing a megabyte at it and then has to do something with it well this is read an invitation for denial of service attack because you allocating memory on the server for doing these operations the operations are pretty fast it's just X pouring zeros and ones but you have to allocate
33:38
one megabyte for each client and so this is a problem no matter what protocol we design we have to deal with the possibility of denial of service attacks or avoid them so can service avoid storing these big
33:51
keys you want to XOR these columns so one of the first limitation small devices was saying well I'm a very small device but I can pick those positions and then outside world please be nice to me and spoonfeed me one column at a time so the small device memorizes thousand five hundred bits I hope so bill and then gets the next column if it was selected it X ORS it in if it wasn't selected well it keeps the intermediate state so this works and at the end you output the normal ciphertext but what we have here is we operating in a friendly environment where we do not expect this outside world to do something nasty to us and also we have some memory now we put this on the real Internet and we don't want to have any so we cannot memorize these thousand if I find out because well we don't know what the next column is going to come so we output it sending this back to this client that's not gonna work when you tell the client oh this is my current
35:01
result then the client gets the next color at the server gets an X come maybe exhausted and maybe not send it back to client anybody who's watching this traffic could see whether there was a change or there was no change so this is not a way of dealing with it so whatever I've been busy with and well I put a two thousand eighty with a question why we still have like three days right so we working on a system called make tiny tiny because it's made for tiny web servers where we assume that this web server is not allocating any Pro client storage any Pro client state and so we again work with spoonfeeding things but we're making sure that everything that the server gets and sends out is encrypted is indicated there is some stuff to avoid replay attacks so that somebody can't just say oh what if I change the column here or there so all of these things are encrypted and what we do is we use properties of doing these sums and pieces by chunking up this big matrix into chewable pieces that are small enough to fit in one MTU and still have some space for some cookies so this is similar to normal users of cookies this is a cookie encrypted to the server sent to the client a client you handle the storage and then the client sends the next piece sends the old cookie now the cookie is encrypted but the way that the key is handled is the same for all clients so there is no pro client storage of any
36:32
keys it's a symmetric key it's pretty small so that's the one thing that the server remembers and then it gets a packets it from this cookie pod recovers
36:40
all the like which columns to pick what's the intermediate result and then does some computation sends it back so the result of this is that we need
36:50
several round trips but there's absolutely no client state on the server of course you could say well there was still all that bandwidth and what if you do have been with
37:02
problems but some people say that we're familiar with sending a lot of data
37:07
around so that's really not a big deal
37:10
something else that could interfere with deployment is patents now Don you mentioned before that classic mclees does not have patents but what if
37:19
somebody says I just don't want to handle the megabyte or for whatever reason people want something smaller or there's thing that your questions well we have a lot of information about some systems which are patented the 18 systems shown here because NIST had as one of the rules for the competition that you had to deliver statements to them signed by the every member of the submission team saying either we do not have patents patent applications on our submission or here's the patents patent applications here's their numbers and so okay as a result of that and NIST's after checking they had a complete pile of statements put them online so now we know that these are exactly the 18 submissions where the submission teams claimed patents on their submissions including for example compact lwe and DME and well not DSA which are rapidly broken by scripts that are online I and our LCU chem that one has half of the parameters are broken there's another half which are not broken it's not that the patented submissions are somehow better than the rest of the submissions but well for some reason people think they can make money off of patents and maybe they're not actually so wrong because you can't just throw away these 18 submissions and say that's the end of it problem is that there's some patents
38:33
which cover more submissions now this
38:38
does not require these submitters to say that here's which patents are which submissions are covered by my patent I the submitters are only required to say something about their own submissions and also NIST has no way to say anything about whatever random patent trolls that
38:57
are out there that have not submitted anything they can't impose any rules on that I mean of course you can try doing patent searches but you won't necessarily find things for instance this patent nobody noticed until it was
39:09
revealed in what by member of some submission teams this patent was issued in 2015 at the top there which might make you think oh if something was published before 2015 it would be okay and some submissions were published earlier but what's important is the date down at the bottom here which is the priority date of February 18th 2010 if you look on Google patents
39:33
one good thing is they put the priority date pretty far up where you can easily see it and what this means is that in order to be prior art for this patent well you have to check what exactly they filed in 2010 they might have made later changes but the 2010 thing assuming that
39:49
has all the same stuff as the patent which it's possible to find out I this anything that was published after 2010 is not prior art for this now what's really scary about this patent and I hope that really soon I'm gonna have analysis online of which submissions are covered by which patents of all the patents have seen this one is by far the scariest because this one covers a whole bunch of submissions this one covers
40:14
basically every submission which is using what's called the LPR cryptosystem ring lwe lattice based crypto systems this is a very popular type of lattice based crypto system which was published by LPN R Luba chef scape iCard and reg
40:30
EV in May 2010 which is after this patent application was filed now there
40:41
was a talk in April which had the same stuff from LPR and it seems like there might even have been a talk in January from LPR but they didn't put the slides online and then well it starts getting into interesting questions with patent
40:56
law this looks like a very strong patent covering a whole lot of submissions and there's more cases there's a whole company called asara that is specializing in planting landmines
41:06
patent land mines around things that other people are doing sometimes on things that other people have already published and then you get a court fight about it this is going to be a problem it's something we really have to watch out for is what is patented and again I hope to be some time soon done with some patent analysis of course some people
41:26
would that we don't have to worry about patents as long as we find something that we can deploy that somebody tries deploying it and they don't get sued not
41:35
sure that's going to be deployed anytime soon I mean 3095 out of 3,000 okay all right funny names are said so what do you see here anybody read phonetics yeah
41:52
see side okay so see side now see side is what
41:59
you really always wanted see side is an evasion post one commutative group action did you know that you wanted a commutative group action actually you did so what all people ask me is like
42:13
I'm using different harm on these days
42:15
what can you give me in the post cotton world and then it depends a lot on how you defined if a helmet some features that we've come to use from Davey Harmon are that well you publish a public key I publish a public key other people publish public keys and we can reuse them kind of nice also we don't have to talk to each other we can just look up the other public key on the phone book have a shared key and start using that one and if I send you something encrypted with our shared some public keys like combined thing of this then
42:51
you will be able to decrypt this there are some nice other features you can blind things you can like take your G to the a and then multiply computer in the exponent times are so put some blind effectors there and there is no difference whether I'm the initiator or I'm the responder in this we don't have this anywhere else in postponing cryptography all the systems that you see for NIST submissions make a difference between are you the sender or the responder so this is the first efficient post quantum well different harm on like things which well by fancy math called commutative group action so if you're a user you don't want to know all the details and I'm gonna give it an entire talk about this and that's maybe next year what you see to you is just one single find field element so there's some fixed prime that all the people in the system know and then everybody's public he is just one single field element so Alice computes her field element Bob computes his field element they pose these somewhere and then sometime later years later maybe of
43:59
quantum computers build they find each other they compute their shared public he combined the shed the public keys into their shared secret key sorry and then they have says shared secret now a little bit of the math behind this a actually appears in some form there so this is a one of the elliptic curves that we've been talking about in gosh when was this 2013 oh so no fortunately looking so they say Y square equals x
44:27
cubed and then a this public key a X square plus X and then what the
44:34
computation is to go from one key to another key is using an ISO Janee same isogen kind of thing that you heard in
44:43
psych before it's a math object which just means you move from one elliptic curve to another love the curve if somebody tells you to implement this what you need to get doing is well take this plan P compute modulo P for addition multiplications and divisions out of those you for instance build with the curve operations and then some more operations which computer sahjhan e but all of those are just combined from those things so there's nothing particularly scary behind it except for well we came up with this thing in January 2018 at this lovely beach
45:22
what's great there but please don't use
45:25
it yet experiment with it all you want but this has not had enough analysis but another reason why you might want this is security key sizes and so on so so we're we're looking at first of all how many keys are there at all so how big do you have to look at this P when you have
45:44
fixed your prime P say n bits then there are square root of P so 2 to the N over 2 may such curves so these are the numbers of public keys and then similar to how the elliptic curve discrete log kind of meet in the middle attacks work so basically smart bruteforce search you get a square root of the number of keys as a security so if you have square root of P many keys it takes you fourth root of P time to find out what else is key is so if you want 228 bit security you have to choose your prime P four times as many bits so a 512 bit prime but this is a talk on post quantum cryptography so where do we stand there elliptic curves would be totally broken nicely enough for I
46:36
solder nice we don't have any complete break there are some some exponential attacks so it doesn't have full exponential security as we maybe would like to have on the other hand with RSA and finally fueled if a harm on we have been dealing with the growth of keys with some exponent attacks so this is something they're familiar with it doesn't kill things but you look at the literature its most jasm tortex so we and also some others have been looking into details I think our analysis which we have at quantum that I sought in your talk is the most detailed one looking into like what actual secured you get against somebody was a really really big quantum computer now as elliptic curves you're hopefully have also learned that you must always validate you need get a point somebody says oh this is my public key the first thing you do is check is this thing on the curve doesn't have the right order same thing for certainty based crypto for seaside you have a very quick check you check that this curve has the number of points you know what it is you don't even need to do full point counting you just take a point do some scalar multiplications and you check it this is another thing that we've gotten totally used to doing this is another thing that is really really really hard for most post comment systems most post one systems you add another proof to it so typically when you encrypt ooh somebody's key and you're sending something which looks like a key you reveal all the secrets on there that's why you can't reuse it or you have to do a big zero knowledge proof to prove that you she generated this thing properly with seaside just there all you do is check it's a valid curve and you're done sighs it's also pretty neat so 32 bytes for the secret keys 64 bytes so just twice
48:22
as large as normal up the coast that is really like bottom left corner of dense graphics where there was nothing so seaside does fill a big gap a big gap is small there with something which pre corner has at least 128 bit security and post quantum so what miss was asking for is comparisons with aes128 and then you look at like how big are the sizes all because the quantum computers and so on and we think that seaside 512 to the best of our knowledge based on the latest analysis will be as secure as that there's some code written by Lorentz somewhere yeah logan's hey
49:05
this is on sky lake your mileage might vary this is a it's not a super quick hack but it's not deployment code so this is not yet constant time there are some others who've been working on constant time it makes it about three
49:18
times slower it is similar to psychic and that it's really nice small keys but somewhat slow on the other hand this is still very newest just from January so we're still figuring out ways to make it faster whereas well psyche has been doing a lot of work getting to the speed that they have now so there's hope that this will get faster and there's some hope it will remain a mine broke until next year but well I'm not sure if I might put my bunny at the thing at this moment I think actually C's had a better chance then psyche of surviving but who knows don't use it for anything yet speaking of broke there's a lot of
49:56
people who are investing in crypto currencies and I think I think it's Nick
50:04
matthewsons fault this whole quantum cyber blockchain idea if you know something earlier than 2016 well anyway there's variations of it since then like quantum AI blockchain apparently you can buy the tshirt we have about 10 minutes left so I'd like to finish things off
50:20
with some comments on software now this
50:22
is looking back at 40 years of public key cryptography while RSA was from 77 or so the big lease crypto system from 78 and then well here's some some schematics of what the software quality has been in cryptography on a scale of good bad terrible and horrifying 1978 I don't actually know I haven't seen software from back then by 1988 it was clear that the software quality was horrifying by 1998 it had moved up to terrible by 2008 it moved up to bed and by 2018 it has jumped back down to horrifying [Music] and of course a major contributor to this is all of these NIST submissions which have code written by mathematicians who barely can implement anything and certainly don't have good code quality there's occasional submission teams that have people who can write code but in general if you well for a good time technically yeah
51:24
that's fine yeah yeah the classic mcLeese code is fine there's other submissions where the code is is fine but if you just take a random submission and look at the code it's well interesting if you would like to find out where the software is and download
51:44
it yeah this doesn't work very well I did look archive.org has like you know search for nist round one on DuckDuckGo and the top link is to the NIST page and then you take the URL for that put it into archive.org and I tried a few of the the submissions and the zip files that NIST prepared with the specifications and the code those are available from archive.org I guess they got most or all of them you can also look for more than half the submissions there are upstream websites with newer code NIST has not updated the code but lots of submissions the submission teams have lots of the fastest code and even some faster well improved code is available in our Supercop benchmarking framework so this is the system for unified performance evaluation related to cryptographic operations and primitives bench CR ypg oh and this one has well a hundred seventy primitives from 40 of the 69 submissions might have accidentally left out all of the patented submissions well the supercoppa policy is anybody who sends us code to put in will it will benchmark it it doesn't have to be unpatented doesn't have to be secure we benchmark md5 we benchmark RSA 512 but well anyways there's 40 submissions where code is in there from other people or from me painfully going through getting code to actually work the primitives are for instance RSA 512 and RSA 1024 and RSA 2048 they're all RSA but they're different primitives or different mathematical functions with different security levels and well in these submissions there there's typically three different security levels sometimes more choices sometimes less and then a lot of the primitives have multiple implementations like reference code and optimized code for different platforms maybe so okay a lot of those are collected in this benchmarking framework all with the same API lid PQ crypto I think I might have a few minutes to say a little more about this let Picou crypto is focusing on having an API which is suitable for cryptographic deployment in the future if you imagine that the implementation quality of the underlying crypto is dramatically improved at least that interface layer is supposed to be something that we will be able to use some more examples of things out there PQ m4 is a library optimized for small
54:04
arm microcontrollers the arm cortexm for p q HW is for FPGAs and this last one open quantum safe that one they don't have as many primitives maybe as loop PQ crypto or super cop but what's cool about that project is they've got working integrations of all of these into open ssl and open SSH so if you're in say the TLS world then that's clearly the way to use these post Quantum proposals at least quite a few of them inside TLS okay let me look a little bit at lib PQ crypto and then we'll finish
54:39
this off I there's lots of cryptographic libraries which give you a nice simple API for hashing they'll have some simple function like sha256 which takes a message okay and C you have to say there's a pointer to the beginning of the message plus length of the message and then gives you back some hash of some 256 bit 32 byte hash and in a higherlevel language of course you say something like H equals sha256 of M and M knows what it's like this but in C it looks like you have H and M and the length of m as arguments why not do this for all cryptographic functions somehow it's really weird lots of cryptographic libraries just have a nice simple interface for hashing and then if you want to do something like public key signatures it's well okay first we're going to find the factory which is producing the keys while the the generator method for the key blah blah blah and well you can
55:34
just say and what lid PQ crypto does is
55:37
it simply says you sign something with whichever signature scheme you have to tell it well I'm gonna put the signed message somewhere and then the length of the message is an output the message you're signing in the length or inputs and your secret key is an input and then it just takes everything in wire format produces everything in wire format you don't have to have conversion functions and put output C realizations etc this is actually an API that goes back to we've been doing Supercop for many years and Supercop the salt library lib sodium etc are all using the same API and this is something which actually people have
56:13
measured the impact on usability of cryptographic libraries depending on the different API provided by these libraries and so we're pretty confident about benefits of having a nice simple way to use crypto this looked at this and said well okay yeah people should submit something in to the post quantum competition using this API but they didn't have test code that people could use to make sure that they were they were following the rules they didn't require that everybody pass any particular set of tests and they accepted submissions which didn't work for example in Supercop so well okay that's why I had to do a bunch of work to integrate a bunch of submissions into into Supercop but it's been sufficiently close to everybody using this that there has been a lot of code shared between these different projects open quantum safe is also starting from the same API and then providing higherlevel integrations into open SSL and open SSH all right okay there's a bunch of different signature systems and a bunch of different encryption systems in
57:17
Latika crypto here's an example of what the higherlevel API looks like in Python if you want to use lib PQ crypto and sign a message well first somebody has to generate a public key and a secret key using the PQ crypto library signature system here's one of the signature systems Sphynx is stateless hash based signature system you don't have to record anything when you sign message and then 128 is security level two to the 128 using the sha to 50 and well you just have to know this name and then you say give me a key pair sign a message using a secret key open a message using a public key now this is not you get a signature and then you do verify of a message and a signature this is another little API detail designed to protect people against screwing up there's lots of applications which verify signatures and then if the verification fails nobody's ever tested it and the verification failure is ignored what actually works to protect application programmers is have an interface where you have a signed message as one bundle it goes into the opening a signature opening a signed message and producing a message and the cryptographic library does not produce a message as output if the signature was invalid so the signed message is produced is is handled by the cryptographic library producing a message if the signature is valid also there's an exception being raised but even if you ignore the exception in python or if you're using a lower level language without exceptions then you just aren't given back a message this is lots of little thought that goes into the API all right maybe a bigger example in Python this is a whole thing of using library generating a key signing some random message and opening the message okay what's going to happen in lib peek your PQ crypto coming up is first of all one of the big problems with code quality is there's lots of exposure to timing attacks I saw a great talk earlier today about Specter and there's lots and lots of these attacks and part of fixing these attacks is fixing software along with we're gonna have to do lots of hardware fixes there's been some work on some implementations to fix this but much more is required need a lot more work on correctness lots and lots of the code doesn't even pass address sanitizer and this was I don't want to tell you how much pain to get code working and address sanitizer where I mean anybody writing code professionally is going to be using these automatic tests as they're writing the code and this is something that just doesn't happen when you ask a bunch of mathematicians to write code formal verification will do much more than staying and do much more than say address sanitizer does and much more than even an expert auditor will do that formal verification is going to guarantee that your code is doing what it's supposed to for every possible input which I used to be very skeptical
1:00:13
about because it seemed so painful to do for any realistic code but I've started getting much more enthusiastic about it because the tools are getting much much better and one example of something I did was a sorting verification where some really fast sorting code is actually completely verified to work correctly the machine code is verified so you compile it even if there's compiler bugs then the machine code is what's verified so that
1:00:38
the verification isn't going to rely on some compiler being correct this is using the anger toolkit also I don't know if there's any trail of bits people here Manticore I understand has similar
1:00:48
features I used anger but well there's really cool tools out there for doing symbolic execution and as part of that formal verification speed is important and trying to get the code volume down
1:01:01
there's lots of duplication we need more internal libraries to get post quantum krypton a smaller easier to review codebase and finally hopefully at the end of all this we'll be able to throw away as many primitives as possible and focus on a small number of things where we can say we've really seriously reviewed these we've reviewed the designs we reviewed the implementations and we're confident that these things are secure that's it thank you for your attention [Applause]
1:01:34
[Music] [Applause] [Music]
1:01:45
Daniel if you would like to leave at this point please do that very quietly will ever use smaller keys you said yeah
1:02:07
from yeah so basically a few there's two submissions classic mcLeese which are highlighted because it's ours and there's NTS chem which has these gigantic keys both of those are using copper codes which is what has received the most analysis so far but at this gigantic list of yep well then it's shown here
1:02:27
several of those are actually code based so big quake for instance down there is
1:02:34
a code based system then like that's my guess one latest one down this whole Lake would be fitting this by saying it's very small keys and signatures and ciphertext the downside is it is using
1:02:49
file as well study codes so we need to see how that develops thank you for
1:02:57
people in the room please try to limit your questions to a single sentence microphone number three your question okay how exactly do you define post quantum crypto I mean you have Shor's algorithm you have the other algorithms but do you
1:03:12
say okay it's just secure against factoring discrete logarithms or do you also take into account optimization problems and stuff like that yeah so so I mean the definition is we're trying to protect against any attacker who has a big quantum computer and we have a rough
1:03:33
understanding of what quantum computers can do because they're limited by the laws of quantum physics which tells us that okay if you can build a computer that supports what are called toughly gates and Hadamard gates then you can well it's not completely proven but it's very plausible that you can simulate the matrix at that point I want I made X which is universal model yes you have a universal computer at that point the problem is
1:03:58
how do we know even if we say well okay by believing that quantum physics is everything we can do in the universe that tells us we have a computation build out of Hadamard and TOEFL ease that doesn't tell you what kinds of algorithms you can put together and there's this big problem that's always been a problem for cryptography is trying to imagine what all possible algorithms are and sometimes people miss something and so if somebody ever tells you oh the system is provably secure there's there can't possibly be an algorithm which is faster than this to break the system no there's no guarantees and lots of people have been overconfident and burned because there is actually a faster algorithm we've had a lot of work on people trying to figure out good algorithms using quantum computers for instance for the subexponential attacks that Tonya was mentioning against seaside and that's something where that there's a long history to those attacks starting with Cooper Berg's algorithm and this is going beyond Shor's algorithm and Grover's algorithm and it's really important to look more at what sort of quantum algorithms could attack cryptographic systems there's been some some initial work but there definitely needs to be more I mean our attacker is allowed to do whatever they want that's why I'm showing this attacker the attacker is not playing by the rules the
1:05:09
only thing we know is our attacker has a
1:05:11
quantum computer okay all right I'll see
1:05:15
you enjoy your next question from the internet size doesn't matter about what about the performance of post quantum cryptography compared to classical algorithms for embedded or FPGA devices for example of fever signing or
1:05:30
communication encryption okay so on the big list and they quickly firing up so PKM four that's using an image cortex m4 so it's a rather small device they did not implement all algorithms and for some of them they said it is very cumbersome to do with a big keys so yes it's more of an issue I mean we're spoiled with elliptic curves just having 256 bits there and all the systems are larger than that these are is the closest you get but then it has a big computation but there is effort and the smaller and more fitting systems have
1:06:07
been implemented hopefully we'll get better Thanks microphone number for your question you said when Google did some
1:06:18
tests they said it's just too slow they
1:06:21
cannot really use it what the solution B acceleration units like use for a s and CPUs so Google was excluding the use of the super single ice dodging ease based on speed I assume that's what you mean rather than the the big ones with the
1:06:37
bandwidth I don't know all the details of it my assumption is it was factoring in also the security like how much time have people spend and analyzing it which made them more comfortable with the structured lettuces than the supercilious Hajin ease you can speed things up if you have a big engine which would be manufactured do you find field arithmetic but that is much much bigger
1:07:01
than say in a gas engine maybe just an extra comment I think that the the choice they made of enter a char s s is really an excellent choice of it's
1:07:11
something which is small enough to fit into most applications I mean a thousand bytes or so it's much bigger than a little curved crypto but compared to all the data we tend to send around it it usually fits unless you got like some really small communication happening then then you usually can fit a kilobyte or so which is the the nth RSS sizes and it's something which it's got some history of study I would be the last
1:07:37
person to say that lattices are definitely secure and we actually are in true prime submission is worried about ways that something like nth RSS could maybe be broken but there's no evidence of any problems and in true has held up for about 20 years of study without being broken so it's also reasonably fast so it's it's a reasonable compromise between the different constraints of trying to have something secure and not ridiculously big and well if it gets broken then we're in trouble but hopefully it's okay thanks single
1:08:13
angel the final question please the final question can see side run on a hardware accelerator made for regular
1:08:20
elliptic curves or is the handling of either Jeanne's more problematic alright so depends what your hardware accelerator has if it's like one of fairly generic elliptic curve arithmetic you can probably use it we're getting some speed from not using
1:08:36
elliptic curves inverse transform but Montgomery forms so you probably would want to modify the accelerator they're currently using to fit this better also most systems are optimized for 256 bit elliptic curve or 384 with 512 bits be a
1:08:51
little bit outside but most of the operations would be looking just the same the most time we spend on doing a big scalar multiplication and then we have some operations in these isogen ease but they are fairly similar if you have like the field or thematic buildup you can just put these together and have nice oddity computation as well so yes it can get faster as I said this is from January we still work on the security analysis so don't build any hardware at this moment quiet thank you so much please give summer youth round of applause for the talk [Applause]
1:09:41
[Music] [Music]