What would Quantum Computing and Machine Learning do to crypto?

so hello everyone my name is i'm the chief researcher of the cryptography research center at the technology innovation institute in abu dhabi the united arab emirates i'm also heading on an acting basis the autonomous robotics center at research center at the institute i would like to thank greg and the organizing committee for having me here today my talk would be on the impact of quantum computers and machine learning on cryptography and cryptographic systems maybe this topic is not mainstream for b-sides so i do hope that um that you enjoy the presentation so as i said the talk today is about what would quantum computers and machine learning do to cryptography and cryptographic systems i guess all of you are familiar with

the concept of cryptography which you know to put it simply it's a set of mathematical algorithms or operations that are conducted on plain text between two parties in order to ensure confidentiality integrity and authentication of data and providing other properties like non-repudiation for example there are two types of cryptographic systems we have the symmetric cryptography systems where the sender and the recipient are basically the two involved parties they share a secret key either through pre-sharing it or establishing it through an algorithms like diffie-hellman for example then the data is encrypted and decrypted using this shared secret key and we also have the asymmetric crypto or what we know today as the public key cryptography where each of the and the parties

what we call here alice and bob each one of them has a pair of a public key and a private key so whenever i want to send an encrypted information to the recipient i use the public key of that recipient to encrypt the data and that recipient obviously after authenticating him or her and that recipient being the only holder of the private key would be able to decrypt the information you're familiar with the the the components of what what we call today the ensemble of algorithms that we call the symmetric crypto so we have block ciphers all of you know about aes we have macs we have hash functions so the random number generators key derivation functions or kdf stream

ciphers authenticated encryption and memory heart functions um you're all familiar with rsa and ecc which are classified under the asymmetric cryptography cryptographic systems and the concepts of key exchange which we do using diffie-hellman or isidifi helman and also with the concept of digital signatures dsa or ecdsa and the same way we have cryptography the design and the implementation and the security analysis of cryptographic systems we also have what we call the cryptanalysis we have the theoretical cryptanalysis and the algorithmic attacks like the chosen plaintext attack where basically the attacker sends his own plaintext to the oracle and then receives the cipher text back and then we also have the chosen ciphertext attacks we have a cryptanalytic attacks against

implementations of cryptographic systems and the most common ones are side channel analysis so either timing attacks cache attacks memory attacks we also have power attacks both simple and differential power attacks em attacks also both simple and differential iem attacks and others and also we have fault injection attacks so these are the attacks or the cryptanalytic attacks that we know today in the classical sense or the or the conventional sense and today we have another threat to cryptography which is basically the quantum computers so focusing on asymmetric cryptography both rsa and scc they are based on mathematically hard problems where even the most powerful computers and supercomputers that we have today would take years and centuries in order to be able

to break those mathematical problems so rsa relies on integer factorization or prime factorization and the heart problem on which ecc or elliptic curve cryptography realize today is discrete logarithms so as i said today the most powerful supercomputers cannot unravel the puzzle around these two heart problems however with the advent of quantum computers and quantum computers as a reality we hear you know about breakthroughs every day regardless of the technology whether it is a superconducting technology whether it is an ion trapping technology etc they're becoming a reality and i guess most of you would have heard especially as of late 2019 about quantum supremacy and the potential ability of quantum computers to solve problems that classical and conventional

computers practically cannot solve and from a crypto sense i know two quantum algorithms we have the shores polynomial time quantum algorithm which factors into with can factor integers and compute discrete logarithms efficiently so what this means based on what i said before because we have this polynomial time quantum algorithms the security of public key cryptographic algorithms basically is gone to zero so it's is broken and we have grover algorithm or what we call grover search which can be used today um which basically reduces the security level of symmetric algorithms by half recent studies said that uh basically for for for encountering the threat the key size of symmetric crypto algorithms would go by 70 900 not 100 percent but in any case

what i'm trying to say here is that the symmetric algorithms are impacted because of global search it's not as much of a priority as as it is for public key crypto but still there is an impact through this quantum algorithm so given this there are differing point of views on how to prevent the threat of quantum computers um against public key cryptosystems so as you can imagine the physicists would say use quantum technologies to fight quantum technologies in other sense use what we call today the quantum key distribution systems in order to fight the threat of quantum computers to cryptographic systems and this is what we call today the quantum cryptography field and cryptography cryptographers say base your crypto on

math or mathematical problems hard problems that quantum computers cannot break and this is the whole concept behind quantum resistant or quantum post-quantum cryptography so post-quantum cryptography basically it consists of algorithms that run efficiently on classical computers but are hard to break even with quantum computers so in other sense these are different they use different mathematical problems than integer factorization or discrete logarithms so there is obviously a need to revamp or revise the standard for public key cryptography in other words we need new post quantum algorithms um and in early 2016 nest announced a plan to select and standardize post quantum algorithms for public key encryption for key establishment or what we call in the post quantum world key encapsulation

mechanisms and for digital signatures the deadline of submissions was in november 2017 and the competition is still ongoing is that it's round three finalists have been announced and most likely and actually i think it's a fact that the there is a fourth round and a call especially that's happening most likely towards the end of this year for candidates especially for digital signatures so basically these are the updates as of as of last year 22nd of july uh you can see that there are multiple candidates for post quantum cryptography both on the public key encryption key encapsulation and signatures there are multiple hard problems based on which post quantum algorithms are based without going into too much

detail we have what we call today the lattice-based cryptography usually there are strong candidates for encryption signatures and key encapsulation or key exchange they are based on what we call the sis and the lwe problems these are the hard problems based on which they are based so basically they are the shortest integer solution and the learning with other learning with errors problems we also have a code based cryptography which is based on coding theory still secure parameters um for uh there are still secure parameters for macales crypto system and this is quite an old crypto system that was uh suggested in the 1970s 1978 they have the key size is large so they have bigger keys and they are attractive

mainly for encryption we also have a post quantum cryptographic schemes that are these are the multivariate polynomial cryptographic schemes and they are based on solving systems of multivariate polynomials i guess multiple schemes that have been proposed have been broken but signatures based on multivariate polynomials still have some potential we have also post quantum schemes that are based on symmetric primitives and in particular hash functions so you know because they are based on hash functions their post quantum security is quite well understood and this is where i quote basically i mentioned the hash based signatures and also we have cryptographic schemes i think here i bundled it under others which is the isogeny it uses isogenes or it uses basically

based on isogeny problem of super singular curves basically there were few proposals for key exchange it's an isogenic diffie-hellman 4k exchange it was proposed there's the key sizes are smaller but we still have performance issues for those cryptosystems and maybe this is why you see them selected as alternative here so to sum it up we have there are finalists across all these um all the schemes lattices codes multivariates hash based signatures there are few that were that were selected across all of them as finalists and the post quantum competition and there are also few that were selected either as finalists or alternates candidates for key encapsulation mechanisms and mechanism and public key encryption so you see that we might be heading already

towards new standards for post quantum crypto but as i said before the competition is my most likely uh going to continue with the fourth round especially for the submission calling for submission of new digital signature schemes now the standardization efforts are great but you know as as researchers in general or security researchers or security practitioners the i'm sure the first question that comes to mind is that how are we going to transition from current cryptographic systems which you know in most cases they are either even non-existing which actually it might make it a bit easier to do that or there are legacy systems that rely on very old implementations and very and old schemes with

um reduced key sizes and bits bit level uh security security and obviously we will face we will face lots of challenges and complexities in this roadmap to transition from whatever we have deployed today in terms of um data address script security cryptographic systems and secure communication solutions so how are we going to move from whatever exists today in the classical sense to post quantum alternatives and here you see lots of efforts that are happening to introduce what we call a hybrid approach or or basically hybrid schemes and it is very crucial for um for organizations to recommend to to deploy and researchers to or practitioners to recommend agile cryptosystems so in the hybrid sense basically the evolution towers

post quantum crypto will be using a hybrid approach between classical standardized algorithms combined with new post quantum algorithms so for example for key exchange or for key establishment we would use a an extension between the key exchange algorithms as we know them today and key encapsulation and and also there should be a hybrid approach because today we still don't have standardized primitives a hybrid approach between post quantum and uh postponed so i guess this is uh this is it for the post quantum talk and i see myself that i already by past 16 minutes and i have instructions to only stick to 20 minutes so i will go very quickly through the second part of

this talk and it is basically the application of or basically the the intersection of machine learning and cryptography so cryptography based on what i've been saying and what you guys know it seems like a complex problem mathematics um constructions etc so the question comes how can machine learning contribute to any crypto field so if if i if we take a step back and put it quite simply machine learning learns from training data it makes predictions on your data through a model built through through the machine learning model that we built does this help tackle all crypto problems well not quite we have the np hard or the intractable problems that are not a candidate because

implied operations and complex in complexity classes are not probabilistically and approximately learnable as i said it takes a quantum computer capable of running shore algorithm in order to achieve that but what this means is that what we can do is define problems or models probabilistically and approximately so for each plain text x with a distribution of v and a mapping function c we can learn a model which maps x to a value and it it maps actually x to a value and that value would agree with the cipher text with a very high probability so basically i managed to approximate a cryptographic problem with a machine learning model and the output of this machine learning

model agrees with the output of the cryptosystem or the ciphertext with a very high probability so what i'm trying to say here i i think i i went to too complex here but what this means to cryptography and this is today actually this is one of the main research problem that we are working on cii and this is fairly leading edge is that how can machine learning how can i use this what i just mentioned for machine learning to help with cryptanalysis um and and you know as i mentioned before cryptanalysis is the opposite of cryptography so it is concerned with recovering a plain text from the cipher text either by recovering a key or by finding

a relationship between the cipher text and the plain text um you know cryptanalysis is just not one text okay not one test that the researcher does and that's it it's a set of tests between linear algebraic meet in the middle attacks etc and the question is how can machine learning help speed up and automate cryptanalysis obviously this can only be beneficial if we find algorithms with a space complexity that grows logarithmically to the size to the size of the feeding data and one cryptanalysis way which we are exploring today is to help find differential characteristics and estimate states inside the cipher between plain text and ciphertext and the better the quality of this non-linear relationship

the harder it is to find this model and the stronger the cipher text will be the cipher text will look closer to a random question now if this relationship between the the clear text what you see here as p1 and the cipher text is not as good a machine learning model can can be found so how does this help basically the the model helps analyze crypto algorithms in a faster and a more automated automated way it helps basically do more automa or basically faster unautomated analysis for differential attacks over crypto cryptographics uh cryptographic implementation so both from design security and the implementation this model help decipher or break cryptographic algorithms and then by doing so it helps you

because it highlights to you the security properties it can help increase the security bounds in cypher designs i have many more slides but i guess i'm running out of time the second area where machine learning can help in the cryptographic field is also it's a cryptanalytic area um but it can help with implementation based uh crypt analysis so and this is actually machine learning can be quite uh quite powerful here so to explain a bit better one of the most common ways to recover keys and subsequently clear text today is side channel analysis and this is you know typically it requires physical access and it requires getting signals or traces from a specific crypto algorithm obviously you

have this signal processing part in order to pinpoint exactly where the crypto algorithm is running um but machine learning is one actually of it's it's quite powerful to be a help or to be of assistance in side channel analysis so today basically i'm not going to to go into the detail of side channel analysis but supervised learning especially mlp and cnns can help quite a bit for profiling and stochastic and template attacks when it comes to side channel attacks we can use machine learning in in side channel attacks for classification clustering feature engineering and pre-processing in particular are quite uh basically convolutional neural networks they are in particular quite useful for this because they learn abstract abstract

representation with at each level or at each layer of of the network so they work best um this is you know this this area of using machine learning inside channel analysis is still fairly new however it is it is quite promising and it is to be thoroughly tested even in the presence of masking thresholding and other countermeasures machine learning can help with deploying security on energy constrained devices and this is one of the main areas that i'm personally quite active in the research of and here the idea without going into the detail of that here the the the idea is that i use quantized neural networks or prune neural networks um on embedded embedded devices

um because you know to today a ns have found really good success in big data applications there is a quite significant interest of using artificial neural networks for medium and small data applications that can be run on embedded systems sensors iot devices energy constraint devices in general however lots of efforts that have been done to migrate those a ns to such devices has has entered a a big loss a big loss function or a big a significant loss to the classification accuracy so here what what this this uh you know the the research here is about pruning neural networks and to be able to run efficiently with an acceptable accuracy on embedded devices and basically what this does is that by

having those pure the the pro neural networks and that are fairly energy efficient and then that can run on the energy on on the end device or the edge device you can have lots of computational power and that is saved by having on device on device intelligence and basically not using this uh and then saving power and not using this power for constant communication between an edge device and the cloud so you save on the communication energy and you would be able to run further you would be able to do inference on device not needing an external communication for doing the intelligence uh on on a cloud or an external server and then by saving this energy you would

be able to run further cryptographic functions or cryptographic protocols or other security mechanisms on the edge device itself and then finally machine learning can be quite useful in the context of confidential computing privacy preserving schemes in general fully homomorphic encryption etc unfortunately i don't have time to go through it by but basically the idea here is that by using machine learning so i execute a machine learning algorithm to a computing service while retaining confidentiality of the data so basically using homomorphic encryption schemes i keep my data encrypted and then i do operations on my encrypted data so i can manipulate the data i can do any complex operation of the data without decrypting it so for example

a cloud service can perform several tasks without exposing this private information however today this is still fhe or full homomorphic encryption is still considered as the holy grail of cryptography it's still quite slow so as you can imagine for real-time operations that's quite a problem however you know there's lots of a lot of research efforts that are going into fhe and to heart and also you know doing software optimization and developing hardware accelerators um as well um you know there is a very clear um very clear use case for federated learning and i guess i will i will stop here i would be very happy to take uh questions online and hopefully on the day i will be able to be online as well

to take your questions thank you very much once again and i do hope that you enjoy the talk when you listen to it bye