What Storage Access Privacy is Achievable with Small Overhead?
CC Attribution 3.0 Germany:
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.
Patel, Sarvar
Persiano, Giuseppe
Yeo, Kevin
Oblivious RAM (ORAM) and private information retrieval (PIR) are classic cryptographic primitives used to hide the access pattern to data whose storage has been outsourced to an untrusted server. Unfortunately, both primitives require considerable overhead compared to plaintext access. For large-scale storage infrastructure with highly frequent access requests, the degradation in response time and the exorbitant increase in resource costs incurred by either ORAM or PIR prevent their usage. In an ideal scenario, a privacy-preserving storage protocols with small overhead would be implemented for these heavily trafficked storage systems to avoid negatively impacting either performance and/or costs. In this work, we study the problem of the best storage access privacy that is achievable with only small overhead over plaintext access. To answer this question, we consider differential privacy access which is a generalization of the oblivious access security notion that are considered by ORAM and PIR. Quite surprisingly, we present strong evidence that constant overhead storage schemes may only be achieved with privacy budgets of epsilon = Omega(log n). We present asymptotically optimal constructions for differentially private variants of both ORAM and PIR with privacy budgets epsilon = Theta(log n) with only O(1) overhead. In addition, we consider a more complex storage primitive called key-value storage in which data is indexed by keys from a large universe (as opposed to consecutive integers in ORAM and PIR). We present a differentially private key-value storage scheme with epsilon = Theta(log n) and O(loglog n) overhead. This construction uses a new oblivious, two-choice hashing scheme that may be of independent interest.
 I'm here today to talk to you guys about what storage access privacy is achievable with small overhead. This is joint work with Sauver Patel and Pino Perceano at Google. So before I begin, I have to tell you guys what the storage access privacy even mean. So we consider a scenario where you have a client on the right and a server on the left. And essentially, the client wants to outsource a large amount of data to the server. So do this in a privacy-preserving way because the data could be sensitive. So the classic way of essentially trying to do this is essentially the client's client-side encrypting data and then storing the encrypted versions of the data on the server. So this seems to work at first in the fact that the server only sees ciphertext. But it turns out as the client is going to operate on the data, it leaks information. So for example, let's suppose the client wants to access the green document. And if you do this naively, well, the server will return the encrypted version of the green document. So while the server doesn't know, oh, is it the green document, what the contents are, stuff like that, it learns that this specific document or this encrypted record was downloaded. So at first, it doesn't seem that bad. It's just a little piece of information. But let's suppose you do this over a long period of time and the server keeps watching. It gets much more complicated statistics. So things like maybe the yellow document or this encrypted record was never downloaded or this one was the most popularly downloaded document. And it turns out that in recent times, if you have some real-world settings with a priori knowledge, this leakage can actually be used to reconstruct the data set, even though it was encrypted. So it's actually an important problem to try and hide this leakage. So this leads to these ideas of access pattern-hiding storage. So essentially, it tries to solve this problem. We have, let's consider this scenario again. The client wants to download this green document. And what will happen is these access pattern-hiding storage systems replace this naive retrieval with a sequence of more complex retrievals. But it does it in such a way such that the server is unable to see what the requested document was. So it won't know, it won't even know this was a specific encrypted record that was downloaded. And I also note that in this example, the server can actually move blocks, like the files around, stuff like that. And it'll do some more complicated things, which I'll show you now, actually. So in the past, there's been two types of these primitives that I've been studying. One's called oblivious RAM or ORAM. Another one's called a private information retrieval, also known as peer. They're slightly different in the fact that one allows the client and server to be stateful while the other one forces them to be stateless, and I'll describe it in more detail. So let's start off with ORAM, or oblivious RAM. In this scenario, we allow both the client and server to be stateful. So what can happen is the client can keep a private key, and it can encrypt the data on the server. And what I mean beyond just encrypting the records, it can actually shuffle the data around according to its private key. So you can imagine some permutations, or pseudo random permutations, where the client keeps the key. And what will happen is it'll do a sequence of requests. So let's, OK, let's suppose it wants to get the green document. And to retrieve the green document, it'll do a sequence of requests, where requests are slightly more complicated than before. Essentially when it does a request, it'll tell the server also to maybe move files around, something like this. It'll swap some locations, et cetera, stuff like that. In addition, it might get another document in return. And it does this several times. So OK. It can do this, and it's been shown that you can, by doing these sort of requests and downloading documents, you can actually achieve access pattern hiding. And now the natural question is, what's the efficiency, or what's the cost of this? And it turns out it's logarithmic. So just in the past year, we've actually had ORAM constructions that have gotten to logarithmic time, and they match lower bounds, which are also just discovered in the past year. And OK, so logarithmic overhead seems to be the cost of trying to do access pattern hiding when the client and server are stateful. And I'll also note that there's an underlying assumption to ORAM, or I believe it's RAM, which is that you're essentially querying from a dense universe, so like n items, and each of the queries exists on the server. You can have a natural generalization of this called key value storage, where your universe is much larger, and you can query for items that don't exist. So in this example, the red document doesn't exist, and the server will return null, or the client will receive null. All right, so moving to the peer example of private information retrieval, like I said, the only difference is that the client and server are stateless. So that means the client can't even keep a private key between queries. So what this means is actually the best upper bounds have running time that's linear. And it's not hard to see by a simple observation that since the client and server are both stateless, if a query does not operate on a database item, and the server sees this fact, the server can essentially rule out that document being downloaded. So in essence, a query must touch every item in the database, and inherently has linear running time. Well, okay, so now let's think about it more carefully, and you see that both of these parameters have expensive overhead. One is logarithmic, the other is linear. If you imagine a system such as a real world system that has low latency or high QPS requirements, you can't really plug these in very easily, or even at all. They're both expensive in practice, and the constants in front of them are actually quite huge as well. So this leads us to our natural question. Now we try to flip the question and essentially say, let's say we want a system, so it's some security, but it has to be high QPS and low latency. So you know, what's the best storage access privacy that's achievable when we have small overhead, when we're sticking to small overhead? All right, to do this, we have to go into a little more detail about what the definition is actually mean. So in the previous example of oblivious RAM and peer, what I was discussing is something called oblivious access. So what does it mean? It takes two sequences as here of the same length. They can differ at any location. And essentially, what will happen is oblivious data structure will compile it into a more complex sequence, but it should be such that the two sequences that are compiled are always indistinguishable. So what this essentially means is the adversary can't tell which the two original sequences had generated this compiled sequence. And what I mean the compiled sequence, I literally mean this. Remember, we take this naive download and compile it to something more complex. All right, so if you think about it carefully, the problem we're asking is what is the best storage access privacy we can achieve? Whereas oblivious access is not flexible at all. It's actually a fixed definition. So we need something flexible and composable to allow us to even try to answer our question. So to do this, we consider something called differentially private access. So what does it mean? It's the same sort of idea, but you take two sequences that differ in exactly one location. They're compiled again by something called a differentially private data structure, and they satisfy this statistical guarantee. If you've never seen this before, this is just the typical differential privacy notion, but the key point essentially is that what we want to say is the resulting sequences from the differentially private data structure don't differ too much in probability distributions. And why we use this is essentially we get this composability result. Essentially what I described for the normal definition or the previous definition was two sequences that differ in exactly one location. But if they differ in k locations, you get this composability result where the security parameters multiply by k. And I'll note if someone's into differential privacy, this is the weakest notion of composability. There are stronger ones for different parameters, but I'll just give an example of why we use this definition and why it's just mainly because for this composability. All right, so a natural question right off the bat, you might ask is, isn't this way too easy? Before this oblivious access, you must hide two sequences that differ at almost every location, but now differentially private access. You're not even saying to hide them when they differ in one location, and you don't even have to hide them. They just have to be statistically close. So this could be way too easy, and the answer is no. So we actually have a different paper where we prove that even in the case where epsilon is constant and delta is less than one third, typically delta is negligible by the way, one third is way too weak of a privacy notion, you still need runtime log n, which matches the oblivious access notion. So clearly this problem is not easy, even with this relaxation. So this leads us to our results, essentially. So in this paper, what we do is we prove lower bounds for these epsilon, delta, and differentially private versions of private information retrieval and RAM and key value storage. And if you see the first bullet, essentially the running time is actually independent of epsilon. So what it typically is, what it's essentially showing you is that you need linear running time for information retrieval because the client and server are completely stateless, regardless of this epsilon, however big your epsilon is. For the RAM and key value storage versions, because the client and server are stateful, you can do some more complicated things, and you can actually have running time n over e to the epsilon. So going back to our problem, what is this state? It states that for constant overhead, you need to have epsilon to be at least log n. All right. So now we go to upper bounds. And essentially, at first, you guys might think it seems very easy to construct these things with epsilon log n. And it turns out it's much more nuanced than you expect. In our paper, we have some strawman constructions which are totally wrong, but you have to be very careful with the construction, essentially. But going back to our results, what we show is that if you have epsilon equals log n, even with pure differential privacy with delta equals zero, we can give you epsilon, delta, or epsilon, differentially private RAMs with constant overhead, and for the key value storage variant, we just need order log log n overhead. And I know for the upper bounds that to do this, we actually have to develop a novel oblivious variant of two-choice hashing. So actually, this is what I'll start off by getting into. So what does hashing typically mean? There are many definitions of what hashing should be. I'm just going to give you one that actually suffices for us. You have a large universe, you, of which you want to only keep n items, and you're going to try to hash them into n bins. And the bins are numbered one to n, let's say, just for simplicity. And what we really consider is this oblivious variant. And what does it mean to be oblivious? It essentially means that we want to hide the number of items in each bin. So you shouldn't be able to see how many items are in each bin. And I'll discuss a little more in detail later. So two-choice hashing, it's actually quite old. It's almost a couple of decades old. It's actually a couple of decades old. And it's this very simple idea. You have n bins of items. And when you want to insert a new item, all you do is you take, let's say, two random hash functions and apply them to the items key. And now you'll get two random bins. And you look at the load of each bin and place it into the least loader of the two bins. So in this example, there are two bins that are chosen. One has load two, one has load one. So we choose to place the item into load, in the bin with load one, and just place it in. So for some probabilistic guarantees, you can essentially show that each bin grows to at most order log log n size. Essentially, yeah, what you can show is that the bins grow. The probability that bins grow decreases doubly exponentially. But if you just do the naive way of doing two-choice hashing, it's not really oblivious because the bin sizes are revealed. So the idea of how to get oblivious hashing is simply padded with dummies. It's actually the only way we know how to make hashing oblivious. So let's suppose we just go back to this example, and all of these dotted line encryptions are just encryptions of dummies, let's say. And this would give us oblivious hashing because now all of that bins are the exact same size. Well the problem is that since the bins are log log n size, you get super linear storage and log log n. So in our paper, what we do is we solve this problem. And by looking at the probabilistic analysis of two-choice hashing, you sort of get an idea of how we can actually fix this. Like I said before, the size of the probability that a bin is full or keeps going in size is actually decreasing doubly exponentially. So we know that if you fix a bin, the chances that it'll be completely filled is quite small. On the other hand, if you look at all the bins, we know one of them will be filled. So the idea essentially is what if these bins started sharing storage? We actually don't need the highest level, the most filled bin. It doesn't occur too often. So the idea essentially is we share these bins in a tree like Strushka. So you have, let's look at the format. You have n over log n trees. Each of these trees are log log n heights. And we have exactly n leaf nodes. And okay, so what we're going to do is for each of these leaf nodes from left to right, we're just going to assign the numbers one to n. And what this will actually be correlated with is actually the bin number. So bin one is correlated or associated with the leftmost leaf node and so on and so forth. So now what constitutes the memory of a bin? Let's suppose let's look at bin four. And it's essentially all the nodes starting from the leaf node associated to bin four all the way to the roots. And I note that each of these nodes can store exactly one item. So if you think about it again, each bin consists of now log log n items once again, because we know some of these bins will go to log log n size. But the total storage is only at most two n items. So now two choice hashing on this is actually identical. If you want to insert a new item, you pick two bins uniformly at random. You look at the memory associated with it and you find essentially the lowest unoccupied node in each bin. So in this case, one's the root of the tree, the other's at the second level. So you place it at the lowest of the unoccupied nodes. So in this case, it would go there. And you get the exact same guarantees. You can show that overflow happens in negligible probability. Okay, there's one little caveat I should mention that you need something called a stash. So you need like, if you essentially show that overflow will be negligible if you buy like some superplay by like essentially omega little omega log n for some function of log n. So you can prove that it's negligible probability. And now like I said, padding with dummies is at most size two n total items. And query and search still require order log log n, right? Each of the bins have still size log log n. So you know, like we said, now we just repeat the same argument. And now we can get an oblivious version of two choice hashing with linear storage. Now let me show you how to quickly, I'll just quickly show you how to use this to get a differentially private key value storage with epsilon equals log n. So and I also, I also want to tell you, I'm going to give you this construction because I want to give you an essence of what is epsilon equals log n security even mean and why it's probably not a good notion of security. So essentially what happens is the client will store will pick a one over N buy or a flip it one over N bias coin. And with this probability, so for each of these items will store it on the client side's cash with probably one over N independent independently. And now if you let's say you want to read a key cane and get the value associated with it, it's quite simple. What you do is you first check if it's in the client's cash. If it is, let's suppose you found the key, the value associated with key K, you just do, you just download two random bins. On the other hand, if let's suppose it's not found, then what you essentially do is you just download the two bins associated with that key K. Right. So if you really think about it, what is the actual security here? Essentially, you're storing each item with probability one over N on the client cash. And in that case, you're doing a dummy request, otherwise you're doing a real request. So that's an example of what epsilon log N differential privacy means. And you can prove that this specific construction does satisfy epsilon equals order log N. And I also know you can support writes by reuploading the download bins and reencrypting, but that's not a very complicated thing. There are some other details of the construction. You can look into the paper, but this is the main idea. And yeah, so I guess before I end, I just want to say that our paper essentially sort of produces a dichotomy of results. If you really want real privacy, you sort of need this expensive overhead. And if your system inherently needs small overhead, you're not going to get much privacy in terms of storage access. And that's like the main results of our paper. Thanks. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you. Thank you.
 I'm here today to talk to you guys about what storage access privacy is achievable with  small overhead.  This is joint work with Sauver Patel and Pino Perceano at Google.  So before I begin, I have to tell you guys what the storage access privacy even mean.  So we consider a scenario where you have a client on the right and a server on the left.  And essentially, the client wants to outsource a large amount of data to the server.  So do this in a privacy-preserving way because the data could be sensitive.  So the classic way of essentially trying to do this is essentially the client's client-side  encrypting data and then storing the encrypted versions of the data on the server.  So this seems to work at first in the fact that the server only sees ciphertext.  But it turns out as the client is going to operate on the data, it leaks information.  So for example, let's suppose the client wants to access the green document.  And if you do this naively, well, the server will return the encrypted version of the green  document.  So while the server doesn't know, oh, is it the green document, what the contents are,  stuff like that, it learns that this specific document or this encrypted record was downloaded.  So at first, it doesn't seem that bad.  It's just a little piece of information.  But let's suppose you do this over a long period of time and the server keeps watching.  It gets much more complicated statistics.  So things like maybe the yellow document or this encrypted record was never downloaded  or this one was the most popularly downloaded document.  And it turns out that in recent times, if you have some real-world settings with a priori  knowledge, this leakage can actually be used to reconstruct the data set, even though it  was encrypted.  So it's actually an important problem to try and hide this leakage.  So this leads to these ideas of access pattern-hiding storage.  So essentially, it tries to solve this problem.  We have, let's consider this scenario again.  The client wants to download this green document.  And what will happen is these access pattern-hiding storage systems replace this naive retrieval  with a sequence of more complex retrievals.  But it does it in such a way such that the server is unable to see what the requested  document was.  So it won't know, it won't even know this was a specific encrypted record that was  downloaded.  And I also note that in this example, the server can actually move blocks, like the  files around, stuff like that.  And it'll do some more complicated things, which I'll show you now, actually.  So in the past, there's been two types of these primitives that I've been studying.  One's called oblivious RAM or ORAM.  Another one's called a private information retrieval, also known as peer.  They're slightly different in the fact that one allows the client and server to be stateful  while the other one forces them to be stateless, and I'll describe it in more detail.  So let's start off with ORAM, or oblivious RAM.  In this scenario, we allow both the client and server to be stateful.  So what can happen is the client can keep a private key, and it can encrypt the data  on the server.  And what I mean beyond just encrypting the records, it can actually shuffle the data  around according to its private key.  So you can imagine some permutations, or pseudo random permutations, where the client  keeps the key.  And what will happen is it'll do a sequence of requests.  So let's, OK, let's suppose it wants to get the green document.  And to retrieve the green document, it'll do a sequence of requests, where requests  are slightly more complicated than before.  Essentially when it does a request, it'll tell the server also to maybe move files around,  something like this.  It'll swap some locations, et cetera, stuff like that.  In addition, it might get another document in return.  And it does this several times.  So OK.  It can do this, and it's been shown that you can, by doing these sort of requests and  downloading documents, you can actually achieve access pattern hiding.  And now the natural question is, what's the efficiency, or what's the cost of this?  And it turns out it's logarithmic.  So just in the past year, we've actually had ORAM constructions that have gotten to logarithmic  time, and they match lower bounds, which are also just discovered in the past year.  And OK, so logarithmic overhead seems to be the cost of trying to do access pattern hiding  when the client and server are stateful.  And I'll also note that there's an underlying assumption to ORAM, or I believe it's RAM,  which is that you're essentially querying from a dense universe, so like n items, and  each of the queries exists on the server.  You can have a natural generalization of this called key value storage, where your universe  is much larger, and you can query for items that don't exist.  So in this example, the red document doesn't exist, and the server will return null, or  the client will receive null.  All right, so moving to the peer example of private information retrieval, like I said,  the only difference is that the client and server are stateless.  So that means the client can't even keep a private key between queries.  So what this means is actually the best upper bounds have running time that's linear.  And it's not hard to see by a simple observation that since the client and server are both  stateless, if a query does not operate on a database item, and the server sees this fact,  the server can essentially rule out that document being downloaded.  So in essence, a query must touch every item in the database, and inherently has linear  running time.  Well, okay, so now let's think about it more carefully, and you see that both of these  parameters have expensive overhead.  One is logarithmic, the other is linear.  If you imagine a system such as a real world system that has low latency or high QPS requirements,  you can't really plug these in very easily, or even at all.  They're both expensive in practice, and the constants in front of them are actually quite  huge as well.  So this leads us to our natural question.  Now we try to flip the question and essentially say, let's say we want a system, so it's some  security, but it has to be high QPS and low latency.  So you know, what's the best storage access privacy that's achievable when we have small  overhead, when we're sticking to small overhead?  All right, to do this, we have to go into a little more detail about what the definition  is actually mean.  So in the previous example of oblivious RAM and peer, what I was discussing is something  called oblivious access.  So what does it mean?  It takes two sequences as here of the same length.  They can differ at any location.  And essentially, what will happen is oblivious data structure will compile it into a more  complex sequence, but it should be such that the two sequences that are compiled are always  indistinguishable.  So what this essentially means is the adversary can't tell which the two original sequences  had generated this compiled sequence.  And what I mean the compiled sequence, I literally mean this.  Remember, we take this naive download and compile it to something more complex.  All right, so if you think about it carefully, the problem we're asking is what is the best  storage access privacy we can achieve?  Whereas oblivious access is not flexible at all.  It's actually a fixed definition.  So we need something flexible and composable to allow us to even try to answer our question.  So to do this, we consider something called differentially private access.  So what does it mean?  It's the same sort of idea, but you take two sequences that differ in exactly one location.  They're compiled again by something called a differentially private data structure, and  they satisfy this statistical guarantee.  If you've never seen this before, this is just the typical differential privacy notion,  but the key point essentially is that what we want to say is the resulting sequences  from the differentially private data structure don't differ too much in probability distributions.  And why we use this is essentially we get this composability result.  Essentially what I described for the normal definition or the previous definition was  two sequences that differ in exactly one location.  But if they differ in k locations, you get this composability result where the security  parameters multiply by k.  And I'll note if someone's into differential privacy, this is the weakest notion of composability.  There are stronger ones for different parameters, but I'll just give an example of why we use  this definition and why it's just mainly because for this composability.  All right, so a natural question right off the bat, you might ask is, isn't this way  too easy?  Before this oblivious access, you must hide two sequences that differ at almost every location,  but now differentially private access.  You're not even saying to hide them when they differ in one location, and you don't even  have to hide them.  They just have to be statistically close.  So this could be way too easy, and the answer is no.  So we actually have a different paper where we prove that even in the case where epsilon  is constant and delta is less than one third, typically delta is negligible by the way,  one third is way too weak of a privacy notion, you still need runtime log n, which matches  the oblivious access notion.  So clearly this problem is not easy, even with this relaxation.  So this leads us to our results, essentially.  So in this paper, what we do is we prove lower bounds for these epsilon, delta, and  differentially private versions of private information retrieval and RAM and key value  storage.  And if you see the first bullet, essentially the running time is actually independent of  epsilon.  So what it typically is, what it's essentially showing you is that you need linear running  time for information retrieval because the client and server are completely stateless,  regardless of this epsilon, however big your epsilon is.  For the RAM and key value storage versions, because the client and server are stateful,  you can do some more complicated things, and you can actually have running time n over  e to the epsilon.  So going back to our problem, what is this state?  It states that for constant overhead, you need to have epsilon to be at least log n.  All right.  So now we go to upper bounds.  And essentially, at first, you guys might think it seems very easy to construct these  things with epsilon log n.  And it turns out it's much more nuanced than you expect.  In our paper, we have some strawman constructions which are totally wrong, but you have to  be very careful with the construction, essentially.  But going back to our results, what we show is that if you have epsilon equals log n,  even with pure differential privacy with delta equals zero, we can give you epsilon, delta,  or epsilon, differentially private RAMs with constant overhead, and for the key value storage  variant, we just need order log log n overhead.  And I know for the upper bounds that to do this, we actually have to develop a novel  oblivious variant of two-choice hashing.  So actually, this is what I'll start off by getting into.  So what does hashing typically mean?  There are many definitions of what hashing should be.  I'm just going to give you one that actually suffices for us.  You have a large universe, you, of which you want to only keep n items, and you're going  to try to hash them into n bins.  And the bins are numbered one to n, let's say, just for simplicity.  And what we really consider is this oblivious variant.  And what does it mean to be oblivious?  It essentially means that we want to hide the number of items in each bin.  So you shouldn't be able to see how many items are in each bin.  And I'll discuss a little more in detail later.  So two-choice hashing, it's actually quite old.  It's almost a couple of decades old.  It's actually a couple of decades old.  And it's this very simple idea.  You have n bins of items.  And when you want to insert a new item, all you do is you take, let's say, two random  hash functions and apply them to the items key.  And now you'll get two random bins.  And you look at the load of each bin and place it into the least loader of the two bins.  So in this example, there are two bins that are chosen.  One has load two, one has load one.  So we choose to place the item into load, in the bin with load one, and just place it  in.  So for some probabilistic guarantees, you can essentially show that each bin grows to  at most order log log n size.  Essentially, yeah, what you can show is that the bins grow.  The probability that bins grow decreases doubly exponentially.  But if you just do the naive way of doing two-choice hashing, it's not really oblivious  because the bin sizes are revealed.  So the idea of how to get oblivious hashing is simply padded with dummies.  It's actually the only way we know how to make hashing oblivious.  So let's suppose we just go back to this example, and all of these dotted line encryptions  are just encryptions of dummies, let's say.  And this would give us oblivious hashing because now all of that bins are the exact same size.  Well the problem is that since the bins are log log n size, you get super linear storage  and log log n.  So in our paper, what we do is we solve this problem.  And by looking at the probabilistic analysis of two-choice hashing, you sort of get an  idea of how we can actually fix this.  Like I said before, the size of the probability that a bin is full or keeps going in size  is actually decreasing doubly exponentially.  So we know that if you fix a bin, the chances that it'll be completely filled is quite small.  On the other hand, if you look at all the bins, we know one of them will be filled.  So the idea essentially is what if these bins started sharing storage?  We actually don't need the highest level, the most filled bin.  It doesn't occur too often.  So the idea essentially is we share these bins in a tree like Strushka.  So you have, let's look at the format.  You have n over log n trees.  Each of these trees are log log n heights.  And we have exactly n leaf nodes.  And okay, so what we're going to do is for each of these leaf nodes from left to right,  we're just going to assign the numbers one to n.  And what this will actually be correlated with is actually the bin number.  So bin one is correlated or associated with the leftmost leaf node and so on and so forth.  So now what constitutes the memory of a bin?  Let's suppose let's look at bin four.  And it's essentially all the nodes starting from the leaf node associated to bin four  all the way to the roots.  And I note that each of these nodes can store exactly one item.  So if you think about it again, each bin consists of now log log n items once again, because  we know some of these bins will go to log log n size.  But the total storage is only at most two n items.  So now two choice hashing on this is actually identical.  If you want to insert a new item, you pick two bins uniformly at random.  You look at the memory associated with it and you find essentially the lowest unoccupied  node in each bin.  So in this case, one's the root of the tree, the other's at the second level.  So you place it at the lowest of the unoccupied nodes.  So in this case, it would go there.  And you get the exact same guarantees.  You can show that overflow happens in negligible probability.  Okay, there's one little caveat I should mention that you need something called a stash.  So you need like, if you essentially show that overflow will be negligible if you buy  like some superplay by like essentially omega little omega log n for some function of log  n.  So you can prove that it's negligible probability.  And now like I said, padding with dummies is at most size two n total items.  And query and search still require order log log n, right?  Each of the bins have still size log log n.  So you know, like we said, now we just repeat the same argument.  And now we can get an oblivious version of two choice hashing with linear storage.  Now let me show you how to quickly, I'll just quickly show you how to use this to get a  differentially private key value storage with epsilon equals log n.  So and I also, I also want to tell you, I'm going to give you this construction because  I want to give you an essence of what is epsilon equals log n security even mean and why it's  probably not a good notion of security.  So essentially what happens is the client will store will pick a one over N buy or a  flip it one over N bias coin.  And with this probability, so for each of these items will store it on the client side's  cash with probably one over N independent independently.  And now if you let's say you want to read a key cane and get the value associated with  it, it's quite simple.  What you do is you first check if it's in the client's cash.  If it is, let's suppose you found the key, the value associated with key K, you just  do, you just download two random bins.  On the other hand, if let's suppose it's not found, then what you essentially do is you  just download the two bins associated with that key K.  Right.  So if you really think about it, what is the actual security here?  Essentially, you're storing each item with probability one over N on the client cash.  And in that case, you're doing a dummy request, otherwise you're doing a real request.  So that's an example of what epsilon log N differential privacy means.  And you can prove that this specific construction does satisfy epsilon equals order log N. And  I also know you can support writes by reuploading the download bins and reencrypting, but that's  not a very complicated thing.  There are some other details of the construction.  You can look into the paper, but this is the main idea.  And yeah, so I guess before I end, I just want to say that our paper essentially sort  of produces a dichotomy of results.  If you really want real privacy, you sort of need this expensive overhead.  And if your system inherently needs small overhead, you're not going to get much privacy  in terms of storage access.  And that's like the main results of our paper.  Thanks.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.  Thank you.
Patel_Persiano_Yeo_0_323.png Patel_Persiano_Yeo_324_4175.png Patel_Persiano_Yeo_4176_5807.png Patel_Persiano_Yeo_5808_6299.png Patel_Persiano_Yeo_6300_9623.png Patel_Persiano_Yeo_9624_9779.png Patel_Persiano_Yeo_9780_12707.png Patel_Persiano_Yeo_12708_15851.png Patel_Persiano_Yeo_15852_21011.png Patel_Persiano_Yeo_21012_21827.png Patel_Persiano_Yeo_21828_23831.png Patel_Persiano_Yeo_23832_24251.png Patel_Persiano_Yeo_24252_24383.png Patel_Persiano_Yeo_24384_24719.png Patel_Persiano_Yeo_24720_24880.png