Homomorphic Encryption by Rob Slade

a hundred thousand greetings from uh the wet coast of north america uh vancouver british columbia canada and the vancouver uh b-sides is is going to be held in about a month and a half um the uh i am delighted to be back in back in dublin because i i taught a cissp review seminar there um well about 17 years ago interesting experience and uh all of you can take a picture of my screen and and uh get all my details from that qr code in complete safety bearing in mind that i did get my start in security as a malware researcher and so i know every way there is to trick people into installing malware on their computers

however we'll not mention that and yes we're going to be talking about homomorphic encryption here uh as soon as we get this thing to work yes uh this also is uh details which you can clearly read if you understand brought 13 since we're talking about encryption homomorphic encryption though homomorphic encryption the basic idea is you can encrypt the data and while it is still encrypted without decrypting it still be able to use it for something um you can do something with it you do not have to uh uh decrypt it in in order to uh perform some kind of function to to be able to uh get any information um oh wait oh yes canada somebody mentioned

canada on the on the chat i i should say that this is the beginning of uh canadian content time seeing us out immediately after me there's chat and then dave is going to be finishing up with a keynote so you're stuck with us for a while uh just uh give me a second though and i'll fire you guys um some details of of uh links and stuff on the talk anyway um so on with homomorphic encryption while i was setting up the slides uh for this this presentation uh i saw this this interesting news item uh that uh canada's uh cse that um which is uh our version of the you know the spies and and uh

communications uh and people who spy on us and everybody else around the world and so on and so forth um they said that they were working on the whole what they call the holy grail of encryption and this is of course homomorphic encryption so you can encrypt something it's you can maintain the the encryption you don't have to decrypt it you can still perform functions on it which is a bit of an overstatement as we will get to uh as we uh proceed through this the first thing is that homomorphic encryption isn't new this is um you know it's it's a lovely uh idea um but of course uh you can use it we have been using we've been

using it for decades and of course all of you will be uh completely familiar with the fact that i am of course talking about password hashing when we uh store passwords we don't store the password itself we store a hash and we store a one-way hash this is intended that it's you're you're not able to use the hash uh to recover the password you you can't decrypt the password uh on password hashing and and you can even uh logically mathematically prove that because of course we hash to a fixed size when we store the passwords and hashes can compress any uh any size of message into a fixed size hash digest so therefore you you cannot know that you

are in fact recovering the password even if you go through the dictionary attacks and that sort of thing you may be able to find a password that that works but you can't find the original password um so we've we have been using that um we so you know this is something we we keep the encrypted data and we still get to use it uh so that's that's what now another example uh this is kind of a bad example of of homomorphic encryption but electronic code book for those of you who have studied encryption you know that electronic code book mode of a block cipher is the weakest form of any cipher because if you encrypt

the same data you get the same ciphertext so the same plain text uh encrypted and electronic home code book is going to produce the same ciphertext now of course this leads to um situations where for example in in the graphics if it's a fairly simple graphic um and it's encrypted in electronic code book mode you can actually see what the original graphic was or at least you know puzzle it out pretty pretty accurately as as to what the original image was uh again if it's a simple image um so we can use electronic book in a block cipher if we want to do an exact search and if we are uh searching for something where the the

block size is is the same size as as the the data we're looking for so uh we can do a search we can do a comparison we can do an exact match um if we're using that now that's not something we normally do but it is the functional we can perform um we can do sorting uh to a certain extent for example a good old caesar cipher you can use the sievered cipher or rot13 and do a sort and you will basically get at least roughly a a rough approximation of the sort that you would get otherwise um and that i mean the caesar cipher is a mod function a very simple mod function but

it is a mod function so any ciphers that use mod functions we should have the ability to do a limited amount of of sorting on that as i said these these are fairly bad examples um another one uh of course covet 19. you know happy uh covet uh pandemic anniversary by the way which was a couple of weeks ago but um uh if we are doing contact tracing with the uh fairly widely used dp3t protocol uh most of the uh contact tracing apps that actually have come into implementation and i know that there's a lot of question as to how useful these things are but they use pure random data as a beacon um and

that does not contain any personally identifiable information now uh as soon as you get into implementation of that you start to see problems because even if we record the beacon along with the date and time or the location we start to give away personally identifiable information or at least potentially um but uh the if the app the contact app is just collecting the the beacon itself then no we're not giving away uh any personally identifiable information we're not uh invading privacy and that sort of thing the uh and that's just using random data so i mean we can't decrypt that for any purpose uh so but again you know these aren't particularly good examples they are examples of the idea of

homomorphic encryption but what we want is something a bit more useful and so let's get into voting now of course voting um uh lots of stuff i i worked as a poll clerk and even deputy returning officer and and some of the federal elections here in canada uh i i know that once you have the ballot when you're when you're counting the votes basically all we have is confidentiality and uh the the process of the election uh is where we get into identification authentication authorization uh non-repudiation and you know and all those verifications that we have to that's part of the process but once we have the actual ballot and we're actually counting the votes we

only have the confidentiality and the ability to to count the votes so uh if if you want to look this up i mean you know people have have looked at this for years and we have voting machines we have proposals for online voting most of which are almost universally terrible ideas and if you go to the risks forum digest and search on voting you will find literally hundreds of articles pointing out the the weaknesses and flaws and vulnerabilities in so many proposed voting systems but revised and yes that is the reverse that's the rnr rsa uh came up with three ballot voting and uh this is a very very interesting system it does give you the confidentiality and

anonymity it gives you also non-repudiation of voting it allows the voter to verify that their vote has been counted the ballots are counted without ever being decrypted so this is an example of homomorphic encryption it's a really interesting one because when you go into the details you can implement this on paper or digitally and so finally in terms of voting machines in terms of online voting we do finally have a system that uh probably gives us uh at least the beginnings of a good possibility of of using it and it's really really interesting example um so this is is a much better example of homomorphic encryption uh by the way microsoft recently uh announced uh this uh system

product whatever called election guard and uh from the information that they have given out on it it does seem to be based on reverse three ballot voting system so uh um something to to watch out for there now uh that's that's one function but there are other functions we want to do and so um when you look at homomorphic encryption and and what you want to do with the data without uh decrypting it you have to build a function and and algorithm based on what it is that you want to do for example addition and multiplication fairly simple uh arithmetic functions and of course you know writ addition at least is is going to be

uh fairly similar to the ballot counting and that sort of thing we uh addition and multiplication are uh associative and commutative that's uh what the the functions here uh indicate so if we can find any function that is both associative and commutative it might be the basis for a solution for an algorithm that will give us the ability to do addition and multiplication with undecrypted data we can we can work on the encrypted data and get proper results uh using this kind of a function and this is how you find an algorithm for any particular function for it for anything that you want to do with encrypted data you find an algorithm that supports the the basic underlying

principles of the function you want to perform uh there are a number of examples um here and and you can go to these sites and and play around with it uh ibm has been working on this uh in terms of addition and multiplication microsoft um in addition to their election guard is probably a separate project but they are working on addition and multiplication and the seal algorithm is there google is looking at uh some stuff that's slightly different they are looking at comparison again we looked at search and exact match and limited edition uh under the name of private join and computer interesting uh project there if you want to look at other examples homomorphicencryption.org the the

introduction uh section of that site lists a number of projects that are going on and and so you can go there um you can find the the write-ups you can find the the actual code um and and play around with it yourself to see uh how this works and how well and is everybody still awake uh so this is uh just a little bit of a break any any questions so far [Music] don't seem to have had any on that the chat and hopefully see aaron will let me know if anybody uh no no none so far yeah rob i think most people are waiting for the end okay i'll keep it in the end

good ask it now um so one of the things i was going to ask was do you see a time when um say things like reverse 3 will be used for digital voting systems like and that will become the standard in the future a lot of places are still on paper they kind of stick to what they know so yeah as i say the the three voting system can be used on on paper there there is an implementation that you can use it uh for a paper ballot so it would be a more secure uh paper ballot than is the existing case when you use the the three ballot voting system if if you're doing it with a

paper implementation you get literally three ballots um and you you vote um but you only drop one of the three ballots into the ballot box you get to keep two and uh the fact that you are keeping these two ballots allows you to verify at a later date if you want uh whether or not your vote actually has been counted so like i say you know the current system uh you drop your your vote in the ballot box you trust in the system the the process is there to ensure that your ballot does get counted but you don't know that you can't verify that with the paper implementation of the three ballot voting system you at a later date can prove that your

your vote was or was not counted so even even with a paper-based system yes i can see the the three ballot voting system being used as as the basis of improvements to our existing uh voting systems and certainly as uh the only thing that i've been able to see in in terms of a relatively safe uh online or or digital voting system so um oh when somebody's asked about uh quantum homomorphic i'll come back to that because if i get into that now i'm going to waste an awful lot of time but yes i i will talk about quantum encryption later on anyways the the thing is that homomorphic encryption um while it's it you know it's a lovely

idea um it's it's not perfect it isn't the holy grail that was mentioned in the the media headline first of all it's not a thing um there's all kinds of functions and implementation just like blockchain you know i i want to get myself a t-shirt that says blockchain is not the answer i don't care what the question is blockchain is not the answer because blockchain is not a thing it's a bunch of different functions uh collection of functions and implementations that are all over everywhere um uh yes daniel i will answer that question um anyways uh it's not universal homomorphic encryption when you do it you have to choose your function in advance the function that you want to

perform determines how you encrypt the data and and so it isn't just a thing where you you know perform you know encrypted with homomorphic encryption and then you can do anything you want with it at a later date you have to choose what you want to do with it first now uh yes we're we're going to talk a little bit about cryptography here do not fret uh the mathematics i i'm not going to get into the mathematics here but we all know about symmetric versus asymmetric encryption symmetric encryption you use the same key you use a single key you have to share the key and that's the problem the uh the symmetric encryption i mean

symmetric encryption is strong we know how strong it is we know how long it's going to take how how long we can ensure that the uh data is protected with symmetric encryption but we've we've got to manage the key and if you uh you know can't manage the key um we have a real problem and uh there's all kinds of systems including yes daniel quantum encryption uh which is not quite encryption actually it is key exchange quantum key exchange and that's all to support symmetric encryption now asymmetric encryption uh we we don't have any problem with the key because one key is private and you never share that key you never tell anybody what your private key is whereas the

other key is public and it you can put it in phone books you can put it on bulletin boards billboards you can do anything you want with it it's public anybody can know your public key uh and so the key management part of that is is done away with it and you know no no problem with key management um but asymmetric encryption is a lot weaker than symmetric encryption and it takes a lot longer you need a lot more computer power so um we've got this you know uh dichotomy between symmetric and asymmetric encryption between the strength and the key management and so what we do with that is we have a hybrid system we use the asymmetric part

of encryption for key management only we encrypt the key because it's very small and we can securely pass the key we don't have to worry about the key management and having passed that session key we can then use symmetric encryption to do all our bulk data encryption and and that's the way we do pretty much everything with cryptography these days you cannot do that with homomorphic encryption you have to work directly with the encrypted data and and so we can't have a hybrid system we we have no way of uh you know saying that we can use you know symmetric encryption for this you know bulk uh encryption and decryption of the data and the homomorphic encryption is only

for key management or something like that it doesn't work that way so this is going to require lots and lots of compute cycles it is going to take an awful lot to encrypt the data um and to d well we're not decrypting but to process the encrypted data and and get a result it's it's going to take more work so uh that having been the case we then go on to look at the fact that we have limited algorithms not everything we may want to do with homomorphic encryption with the encrypted data uh do we have an algorithm for at the moment as i say there's a number of uh projects looking into different types of

functions and and certainly there is going to be ongoing work in this field but we don't have all the functions that we may want if you want to combine functions the algorithms are going to be even more limited you're going to have to find an algorithm that suits all the functions that you want to combine and that's going to be more difficult to build the algorithm and definitely more difficult in terms of the processing that you want to do so that's going to be a weakness we can't do everything we want with it um and remember the bad examples that i gave you earlier the sievers caesar cipher that's a that's a very weak uh encryption system because it's got a

very limited address space you know you can you know break a caesar cipher with brute force anytime you want and again the block mode the electronic code book mode of block ciphers is the weakest mode for uh block ciphers so that is is going to limit what we can do and as we use different homomorphic encryption systems you have to pay attention to these things and realize that there is uh going to be inbuilt weaknesses to this in the same way that asymmetric systems and algorithms are weaker that than symmetric algorithms homomorphic algorithms are going to be similarly weak because they limit the ways you can encrypt the data that you're you're dealing with so uh as i said i i

taught a uh cissp review seminar over there uh some years back so this is a sample question which of the following is not an effective deterrent against a database inference attack partitioning small query sets noise and perturbation and cell suppression and this is one that always throws people because the actual correct answer and there is noise and perturbation and p you say that people and they say you know what uh are you talking about you know nobody wants to put noise and perturbation into their results but you do sometimes if you want to uh keep data private and i'd talk about that in a different presentation on differential uh privacy but the the thing is that we may want to do

different things with our data and homomorphic encryption is going to definitely limit us in terms of what we can and cannot do in in these systems now uh the the accuracy of the data and the accuracy of the results is another limitation here another weakness um the people who have worked on homomorphic encryption and and again you can go out and look at the research there uh but uh a writer named gentry has uh proposed something that he refers to as fully homomorphic encryption because he is looking at what you can do in terms of homomorphic encryption and still get completely accurate results from the functions that you perform on it so that's an you know an an interesting uh

examination and again a limitation of what you can do with homomorphic encryption uh microsoft is going to be using uh is promising us that they are going to be doing uh homomorphic encryption guarding your passwords the passwords that you have in microsoft edge well first of all everybody has been storing passwords uh in in hashed form and as i said before you know that's basically a form of homomorphic encryption so you know this is not something new and um besides what what microsoft is promising to do in edge microsoft chrome has been doing that for years in any case so um you know this is uh this is something that you were going to see

um with with a lot of these new technologies with uh homomorphic encryption with differential privacy with quantum uh cryptography and that sort of thing you have to figure out what the people are actually doing with it um vendors are going to be promising you things uh taught you using the latest buzzwords uh but you you do have to know what it is that they're talking about um to determine whether what they're promising you is actually uh you know homomorphic encryption or quantum cryptography or whatever it is and whether or not it actually is an improvement for you a a benefit for you so uh you know that's basically that the whole point of uh what i've

you know this this presentation now uh before i ask sharon for uh some more questions um quantum homomorphic ed um you have 15 minutes here rob uh if that's the only question so you can you can use the time as much as you like okay well we'll see we'll see if anybody comes up with any other questions but um yes quantum cryptography i love this because i have i have yet another presentation on uh security implications for quantum computing and there is in fact a difference between quantum computing and quantum cryptography and there is in fact a difference between quantum cryptography and cryptography quantum cryptography is not cryptography quantum cryptography is simply another way of key exchange

it's a very expensive way of key exchange originally you had to have dedicated single mode fiber optic cable to do key exchange with quantum cryptography and if you've got dedicated single mode fiber optic cable why do you need cryptography i mean you've got you know not completely untappable i've had this argument with guys from the nsa but um you have uh the most untappable system that there is and and so you know that's that's one part of it but as i say quantum cryptography is just key exchange it's not a new means of cryptography now where cryptography comes in is uh the shore and and some of the other algorithms that are proposed for uh quantum computers

and quantum computers the theory is that quantum computers will be able to break encryption but you have to have an algorithm to break the encryption and the the short algorithm for example to use one is proposed as an attack on rsa but it's only an attack on rsa it can be used on on other uh crypto algorithms that use mod functions in in particular but it's uh you know it's uh not exactly theoretical it does work but only if we have a quantum computer and at the moment uh the real quantum computers are limited to you know uh qubits in the double digits in order to break an rsa key of 4000 bits which is not unreasonable you are going to

have to have a quantum computer full quantum computer with at least 8 000 cubits so you know we've got double digits right now we've got to go to you know at least 8 000 qubits um you know there's a few orders of magnitude in there before we have to worry about people breaking rsa keys now there is a quantum computing system uh that's a little bit larger that is the d wave system and i know about that because that's over in burnaby it's you know not 20 miles from where i'm sitting here but uh that is not that that is best described as probably a quantum co-processor uh that's not a fully uh functioning quantum computer so

uh that is you know there's there's limitations there now uh i assume that when you say quantum homomorphic your talking there uh okay you've given me a url uh i'll go and have a look at that and maybe we can talk about that if you fire me your uh email address uh anyways you can you can contact me by email um okay a few more uh questions have come in here uh yeah quite a few is this something that could replace the current pki basically no i mean it's a different system um if you don't need to decrypt the uh the function of course you don't need pki because you don't need asymmetric encryption you don't need the key

exchange and that sort of thing but it's only going to be useful in fairly limited situations is there any solid homomorphic encryption solution available that is reliable and can be deployed on an industrial scale such as in public cloud um yes again the uh the ones that i uh sent you and and i fired all the links from the presentation here into the chat so if you go into the chat and pick that up um you'll be able to see those uh things um those systems are available i mean you can even get the source code they are reliable they can be deployed on a an industrial scale but only for those specific functions again you're limited to those uh the

functions that those projects uh have looked at and uh you mentioned that homomorphic encryption requires lots more cpus cycles what rough order of magnitude would you mean that i i have not done the math in in terms of how much more uh i'm just going to say you know number one it's going to be you know as compute intensive as asymmetric encryption or more and we know that the processing of uh in in asymmetric rather than symmetric encryption is uh a hundred to a thousand times uh more intense and the um we we cannot as i say um use the same type of of hybrid uh uh combinations um that we could with asymmetric and

symmetric encryption as as i mentioned there um what's the most feasible likely use case for homomorphic encryption based on the current research well it's not the current research i'd say the voting system um we uh you know there are the um uh the comparisons matching um uh as i say you know we've been using that for for password protection for years so you know we are using it there there are a bunch of of things that we can use it for uh but there are also a number of things that we we would like to do uh while still protecting and and keeping data encrypted um and we simply haven't got the algorithms yet to do that

so that seems to cover what's come in so far any any further discussions nothing yet on on the uh on the chat um rob you've made my job very easy as mc you you've done done all the questioning for me which was uh which is fantastic i could just sit back and have a coffee um well very very interesting talk rob um thank you very much um we might just give folks another minute or two just to see if they um have any additional questions and uh then we can then you and it um do duke it out on a separate channel to quantum encryption yeah so nothing nothing else has come in rob um

so once again thanks for your time today um very interesting talk you're quite welcome and and i guess people have uh four minutes to to run to the bathroom before uh chat comes on deck and you'll want to listen to chat yeah absolutely thanks again rob i hope you see you're welcome dublin sometime again

you