>>Hi, everyone. My name is Dan Bonnie and I want to thank the organizers for inviting me to speak. Since I only have 15 >>minutes, I decided to talk about something relatively simple that will hopefully be useful to entity. This is joint work with my students Sabah Eskandarian and Sam Kim. And with Morrissey, this work will appear it, uh, the upcoming Asia crypt and is available on E print if anyone wants this to learn more about what I'm going to talk about, So >>I want to tell you the story >>of storing encrypted data in the cloud. >>So all of us have lots of data, and typically we'd rather not >>store the data on our local machines. But rather we'd like to move the data to the cloud so that the cloud can handle back up in the cloud, can handle access control on this data and allow us to share it with others. However, for some types of data, we'd rather not have the data available in the cloud in the clear. And so what we dio is we encrypt the data before we send it to the cloud, and the customer is the one that's holding the key. So the cloud has cipher text, and the customer is the only one that has the key that could decrypt that data. >>Now, whenever dealing with encrypted data, there is a very common requirements called key rotation. So key rotation refers to the act of taking a cipher text and basically re encrypting it under a different key without changing the underlying data. Okay. And the reason we do that is so that an old key basically >>stops working, right? So we re encrypt the data under a new key, and as a result, the old red key can no longer decrypt the data. So it's a way for us to expire keys so that Onley the new key can decrypt the current data stored in the cloud. Of >>course, when we do this, we have to assume that the cloud actually doesn't store the old cipher text. So we're just going to assume that the cloud deletes the old cipher text, and the only thing the cloud has is on Lee, >>the latest version of the cipher text which can only be decrypted using the latest version of the key. >>So why do we do key rotations. Well, it turns out it's actually quite a good idea for one reason. Like we said, it limits the lifetime of a key. If I give you a key today, you can decrypt the data today. But after I do key rotation on my data, the key that I gave you no longer works. Okay, so it's a way to limit the lifetime of a key. And it's a good idea, for example, in an organization that might have temporary employees. Basically, you might give those temporary employees a key. But once they leave effectively, >>the keys will stop working after the key rotation has been done. >>Not only is it a good idea, it's actually >>a requirement in many standards. So, for example, this requires key rotation, the payment industry and requires periodic he rotation. So it's a fairly common requirement out there. The >>problem is, how do we do key >>rotation when the data is stored in the cloud? Yeah, so there are >>two options that immediately come to mind, but both are problematic. The first option is we can download the entire data >>set onto our client machines. Things could be terabytes or petabytes of data so it's a huge amount of data that we might need to download on to the client >>machine, decrypt it under the old Ke re encrypted under the new key and then upload all >>that data back to the cloud. So that works and it's fine. The only problem is it's very expensive. You have to move the data back and forth in and out of the cloud. The >>other option, of course, is to send the actual old key in the new key to the cloud and then have the cloud re encrypt using the old key and re encrypt, then using the new key. And of course, that also works. >>But it's insecure because now the cloud will get to see your data in the clear. So >>the question is what to do. And it turns out there is a better option, which is called up datable encryption, so obtainable encryption works as follows. What we do is we take our old key and our new key, and we combine them together using some sort of ah kee Reekie generation algorithm. What this algorithm will do is it will generate a short key. That's a combination of the old and new key. We can then send the re encryption key over to the cloud. The cloud can then use this key to encrypt re encrypt the entire data in the cloud. So in doing so, basically, the cloud is able to do the rotation for us. But the hope is that the cloud learns >>nothing about the data in doing that. Okay, so the re encryption key that we send to the cloud should reveal nothing to the cloud about the actual data that's being held in the cloud. So obtainable encryption is relatively old concept. I guess it was first studied in one of our papers back from 2013. There were stronger definitions given in the work of Everest power it all in 2017. And there's been a number of papers studying this this concept since. So >>before we talk about the constructions for available encryption, let me just quickly make >>sure the syntax is clear. Just so we see how this works. So basically there's a key generation algorithm that generates a key from a security parameter. Then, when we encrypt a message using a particular key, we're gonna break the cipher text into a short header and the actual cipher text the hitter and the cipher text gets into the >>cloud. And like I said, this header is going to be short and independent of the message length. Then when we want to do rotation, what we'll do is basically will use the old key in the new key along with the cipher text header to produce what we call >>a re encryption key will denote that by Delta. Okay, so the way this works is we will download the header from the >>Cloud Short header Computer Encryption key, send their encryption key to the cloud, and then the cloud will use the re encrypt algorithm that uses the re encryption key and the old cipher >>text to produce the new cipher text. And then this new cipher text will be stored in the cloud. And again, I repeat, the assumption is that the cloud is gonna erase the old cipher text. It is going to erase the re encryption key that we send to it. >>And finally, at the end of the day, when we want to decrypt the actual cipher text in the cloud, we download >>the cipher text on the cloud we decrypted using the key K and recover the actual message in. >>Okay, So in this new work with my students, we set out to look Atmore efficient constructions for available encryption. So the first thing we did is we realize there's some issues >>with the current security definitions and so we strengthen the security definitions in particular, we strengthen them in a couple of ways, but in particular, we'd like to make sure that the actual cipher text has stored in the cloud doesn't actually revealed a number of key rotations. Yeah, so a rotated cipher text should look indistinguishable from a fresh cipher text. >>But not only that, That actually should also guarantee >>that the number of key rotations is not leaked by from just looking at the cipher text. So generally, we'd like to hide the number of key rotations so that it doesn't reveal private information about what's what's encrypted inside the cipher text. >>But our main goal was to look at more efficient construction. So we looked at two constructions, one based >>on a lattice based key home or fake. Prof. So actually, the main point of this work was actually to study the performance of a lattice based key home or fake prof relative to the existing of datable encryption systems >>and then the other. The other construction we give is what's called a nested. Construction would just uses plain old symmetric encryption. And interestingly, what we show is that in fact, the nested construction is actually the best construction we have as long as the number of key rotations is not too high. Yes, so if we do under 50 re encryptions, just go ahead and use the nested construction basically from symmetric encryption. However, if we do more than 50 key rotations, all of a sudden the lattice >>based construction becomes the best one that we have. >>I want to emphasize here that are our goal for using lattices. That was not to get quantum resistance. We wanted to use lattices just because >>lettuces are fast. Yeah, and so we wanted to gain from the performance of lattice is not from the security that they provide >>eso I guess before I talk about the constructions, I have to quickly just remind you of how >>what what the security model is, what it is we're trying to achieve and I have to say the security model for available encryption is not that easy to explain here, You know, the adversary gets to see lots of keys. He gets to see lots of re encryption keys. He gets to see lots of >>cipher text. So instead of giving you the full definition, I'm just gonna give you kind >>of the intuition for what this definition is trying to achieve. And I'm going to point you to the paper for the details. So >>really, what the definition is trying to say >>is the following settings. Right. So imagine we have a cipher text that's encrypted under a certain key K. At >>some point later on in the future, the cipher text gets re encrypted using a re encryption key Delta. Okay, so now the new cipher text is encrypted under the key K prime. And what we're basically trying to achieve in the definition is to say that well, if the adversary gets to see the old cipher text >>the new cipher text and they re encryption key, then they learn nothing about the message. And they can't harm the integrity of the cipher text. >>Similarly, if they just see the old key and the new >>cipher text. They learn nothing about the message, and they can't harm the integrity of the cipher text. And similarly, if you see an old cipher text in a new key, same thing. Yeah, this is again overly simplified because in reality, the adversary gets to see lots of cipher, text and lots of keys and lots of encryption keys. And there are all these correctness conditions for when he's supposed Thio learn something and whatnot. And so I'm going to defer this to the paper. But this gives you at least the intuition for what the definition is trying to >>achieve. So now let's turn to constructions, so the first construction we'll look >>at it is kind of the classic way to construct available encryption using what's called the key home or fake. Prof. Sochi Home or for Pierre Efs were used by the or Pincus and Rain go back in 99 there were defined in our paper. BLM are back in 2013 the point of the BLM. Our paper was mainly to construct key home or fake pl refs without random oracles. So first, let me explain what Akiyama Murphy pf >>is. So it's basically a Pierre F where we have home amorphous, um, >>relative to the key. So you can see here if I give you the prof under two different keys at the point X, I can add those values and get the PF under the some of the keys at the same point x. Okay, so that's what the key home or fake property lets >>us dio. And so keyhole Norfolk PRS were used to construct a datable encryption schemes. The first thing we show is that, in fact, using keyhole graphic PRS, weaken build an update Abel encryption scheme that satisfies are stronger security definitions. So again, I'm not going to go through this construction. But just to give you intuition for why key Horrific Pff's are useful for update Abel encryption. Let me just say that the re encryption key is gonna be the some of the old key and the new key. And to see why that's useful. Let's imagine we're encrypting >>a message using counter mode so you can see here a message is being encrypted using a P r f applied to a counter, I >>Well, if I give the cloud K one plus K to the cloud >>can evaluate F F K one plus K two at the point I and if we subtract that from the >>cipher text, then by the key home or FIC properties, you'll see that F K one cancels out. And basically we're left with an encryption of them under the ki minus K two. So we were able to transform the cipher text for an encryption under K one to an encryption under minus K two. Yeah, and that's kind of the reason why they're useful. But of course, in reality, the construction >>has many, many more bells and whistles to it to satisfy the security definition. Okay, so >>what do we know about Qihoo? Norfolk? Pff's? Well, the first key home or fake prof is based on the d. D H assumption. And that's just the standards PF from D d H. It's not difficult to see that this >>construction actually is key human Norfolk. >>In this work, we're particularly interested in the keyhole morphing prof that comes from lattices. So our question was, can we optimize the ski home amorphous prof to get a very fast update Abel encryption scheme? And so the answer is yes, we can. And to do that we use the ring learning with error problems. So our goal was really to kind of evaluate obtainable encryption as it applies to lattices. So that's the first construction. The second construction, like I said, is purely based on symmetric encryption, and it's kind of an enhancement of what we call the Trivial Update Abel encryption scheme. So what's the Trivial Update? Abel encryption scheme? Well, basically, we would look at >>a standard encryption where we encrypt the message using some message key. And then we encrypt the message key using the actual client key. These are all symmetric encryptions. The client basically clinic. He would be >>K, and the header would be the message encryption key. Now, when we want to rotate the keys, all we will do is basically we would generate a new message. >>Encryption key will call a K body prime. We'll send that over to the cloud that the >>cloud will encrypt the entire old cipher text under the new key and then encrypt a new key along with the old key under a new clients key, which we call Cape Prime. So what gets sent to the cloud is this K body prime and header prime and the cloud is able to do its operation and re encrypt the old cipher text. The new client key becomes K prime. And of course, we can continue this over and over in kind of an onion like encryption where we keep encrypting the old cipher text under a new message. He The benefit of the scheme, of course, is that it only uses >>symmetric encryption, so it's actually quite fast, so that's pretty good. >>Unfortunately, this is not quite secure. And the reason this is not secure is because the cipher >>text effectively grows with a number of key rotations. So the cipher text actually leaks the number of key rotations, and so it doesn't actually satisfy our definitions. Nevertheless, we're able to give a nest of construction that does satisfy our definitions. So it does hide the number of key rotations. And again, there are lots of details in this constructions. I'm going to point you to the paper for how the nested encryption works. So >>now we get to the main point that I wanted to make, which is >>comparing the different constructions. So let's compare the lattice based construction with a D. D H but its construction and the symmetric nested construction for the DTH based construction. We're going to use the GPRS system just for a comparison point, >>so you can see that for four kilobyte message >>blocks, the lattice based system is about 300 times faster than the D. D H P A system. And the reason we're able to get such a high throughput is, of course, lattices air more efficient but also were able to use the A V X instructions for speed up. And we've also optimized the ring that we're using quite a bit specifically for this purpose. Nevertheless, when we compared to the symmetric system, we see that the symmetric system is still in order of magnitude faster than even a lot of system. And so for encryption and re encryption purposes that the symmetric based system is the fastest that we have. When we go to a larger message blocks 32 kilobyte message blocks, you see that the benefit of the latter system is even greater over the D d H system. But the symmetric system performs even better Now if you think back to how the symmetric system works. It creates many layers of encryption and >>as a result, during decryption, we have to decrypt all these >>layers. So decryption in the symmetric system takes linear time in the number of re encryptions. So you can see this in this graph where the time to decrypt increases linearly with the number of re encryptions, whereas the key home or FIC methods take constant amount of time to decrypt, no matter how many re encryptions there are, the crossover point is about 50 re encryptions, Which is why we said that if in the lifetime of the cipher text we expect fewer than 50 re encryptions, you might as well use the symmetric nested system. But if you're doing frequently encryptions, let's say weekly re encryptions, you might end up with many more than 50 re encryptions, in which case the lattice based key home or fix scheme is the best up datable system we have today. >>So I'm going to stop here. But let me leave you with one open problem if you're interested in questions in this area. So let me say that in our latest based construction, because of the noise that's involved in latest constructions. It turns out we had toe slightly weaken >>our definitions of security to get the security proof to go through. I think it's an interesting problem to see if we can build a lattice based system that's as efficient as the one that we have, but one that satisfies our full security definition. Okay, so I'll stop here, and I'm happy to take any questions. Thank you very much.