Accessing Data Privately, from Theory to Practice with Elaine Shi | a16z crypto Research Series

Transcript

All right, welcome everyone to today's A16Z crypto research seminar. Very pleased to introduce Ela Shei, full professor at Carnegie Melon. Uh Elaine's worked extensively in almost every area relevant to blockchain technology, whether it's cryptography or consensus or mechanism design. Uh she's won lots of stuff, Sloan fellow, Packard fellow, etc. very happy she's here to talk to us today about accessing data privately. So >> yeah, thank you so much. Uh I'm very excited to uh be here today. I'll talk about how to access uh your data privately. So I'll start with some motivating examples like why real life applications really need this and and I'll start with Signals application. So Signal is running private contact discovery and what happens is like let's say Tim wants to join Signal and he

wants to discover his friends on Signal. So he's going to send his address book to signal and signal will return the entries corresponding to his friends. There's like various application domains where this happens. Um I'll start with the signal example and say like why access pattern leakage is an important problem and then I'll quickly go over the other applications. Uh so so with signal obviously you know Tim Tim thinks this address book is top secret. Uh so he doesn't want to disclose it. Uh and one solution to this problem is we can use a trusty hardware also called TE. Um and uh essentially you can imagine there's like some hardware sandbox and everything's encrypted uh either in

storage or in transit and data can only be decrypted inside this uh sandbox uh where the computation takes place. So the problem with this solution like it appears that it should be very secure because all the data contents are encrypted but the problem is that here only the data contents are encrypted but the access patterns are not encrypted and the access patterns are very leaky. In this particular example if you observe which entries are fetched it will directly leak who your friends are. So also um this should not be dismissed as a side channel leakage because this is like directly observable digital information that leaks your sensitive secrets. So that's one example and then uh a similar problem also manifests in

many blockchain applications. I'll just talk about uh one particular application uh private order flow. So today what happens is that all the transactions are submitted in clear text uh and then the block builder will assemble the next block to be included in the uh consensus protocol. Uh the problem with today's approach is that uh the block builder can uh perform front running and back running attacks. Uh so I I gave the talk earlier to a crypto audience but to to this audience you know this is called MEV uh and uh it's a big problem in the cryptocurrency community because uh this is actually causing the infrastructure to be highly centralized. So according to a recent empirical measurement by

young at all uh they show that more than 85% the blocks are produced by just the biggest two block builders. So it's kind of like a duopoly and and obviously if you are uh blockchain creator this is a big problem because the core value proposition of blockchain is the decentralization right so it is very important to retain the decentralized nature uh and when in envision the solution is called private order flow where users can submit their transactions in encrypted format and the block building takes place in a encrypted fashion. Okay. Similarly uh in this context uh the problem is as you build the block you have to

speculatively execute these transactions and you can think of each transaction as a small smart contract program and as this program executes it's going to read data that lives on the blockchain and these access patterns here are just equally leaky because they leak the the crypto assets you are interested in trading. They leak your trading partners and they also leak who you are and this is precisely the information we want to hide. uh so therefore it's also incredibly important to protect access patterns uh in this context okay and it's not possible to give a talk without mentioning AI and LLM and in large language model a commonly used technique is called retrieval augmented generation or rack and what rack does is that it

will take the user's query it will perform some transformation on the query to figure out in this very large knowledge base which parts I should read to answer the user's query and again here you can imagine the access patterns leak highly sensitive information about the query itself. So these are some of the high value applications we are looking at and they all ask more or less the same question. Uh how can we provably defeat access pattern leakage but still preserve the efficiency and I'm going to quickly formulate the problem. Imagine there's a client and there's a server and the server has a database. It has been uh possibly it has been pre-processed and we are going to assume the server is untrusted. Uh so

what do I want? I want a protocol such that when the client wants to access some address X the client and the server will interact with each other uh in this protocol and at the end the client will output uh the desired entry and the security property is that we want to make sure given any two access sequences of the same length uh let's say x0 and x1 are two access sequences I want to make sure the servers view um uh are computationally indistinguishable.

So the server basically learns nothing um from its view about your intent. Okay. So there are actually a couple solutions that can solve the problem and I'm going to compare them and tell tell you where things are today and then look forward to the future. Uh so I'll talk about two main techniques. One is called oblivious RAM or ORAM and the other is called private information retrieval or peer. You know both of these techniques can hide access patterns. So what are the main differences between the two approaches? And I think perhaps the biggest difference is that ORAM allows per client state. In other words, the server is allowed to store a separate copy of the database for each client.

Whereas for PIR, we typically assume uh all these clients want to access a globally shared database and we don't want to make a separate copy of the database for each client. like the database can be huge like the blockchain and it's like not viable to make a separate copy for each client. So for this reason actually OAM is actually a better fit if uh we are in the outsourcing scenario. Let's say the these businesses they each have their own private data set and they want to outsource the data set to the cloud whereas PI is actually better suited for accesses to some public uh it actually it doesn't have to be public it just has to be a global database okay and as you have seen right the motivity examples I talked about today

actually they're kind of more like in the PI bucket there they have a globally shared database so why is ORAM still relevant But let me tell you why ORM is still relevant. Uh so actually the practically deploy solutions today they actually use TE plus OM and in order to avoid the drawback that the state has to be replicated for each client. Uh essentially what happens is they have a TE in the cloud and the T acts as a global client on behalf of all clients. So this uh circumvents this problem. Uh and you know this is the solution that Signal is running. uh Meta actually has also implemented ORM uh with TE they have open source available and they told

me they're going to launch some service uh based of it and they I I asked them for more information and they just say okay wait for the launch okay and then we are also working with like blockchain um players like Ethereum flashbots to get this kind of solution deployed so it doesn't have to be TE right like I think at this point a lot of people will ask you know T may not be a good assumption and and uh you know especially for instance blockchain like they believe in decentralization they don't want to trust any uh single hardware vendor so in the longer term and perhaps it doesn't even even have to be the longer term like you can uh think about replacing the TE with like a

two-party computation or multi-party computation in this talk I'm only going to focus on two party but everything I say will apply to multiple parties as well uh so here essentially you are using this two PC to realize a cryptographic computer that replaces the TE and and um of course the third approach is just to use P itself. >> Okay. So I I want to do things in a reverse chronological order. Yeah. >> Just a question. So so you're you care only about reads or reads and writes?

reads we can do. Um I I guess okay maybe that that's a a good good question like I think for the P schemes we have implemented they it only supports reads but for the OM based solutions reads and rights they they just rights come for free and I think for P it may take some extra effort if you want to support rights are general basically there's also also the more general question whether you can support general purpose computition and the ORAM based approaches the first two approaches will support general purpose competition whereas for PI the practical solution today doesn't support general computition yet it's theoretically possible to support general computition but it's like way way way out there so I I will do things in reverse

chronological order I will first talk about where things are today maybe hopefully you'll get more excited and then I will tell you how we actually got here the state-of-the-art for the first approach ORM plus TE uh so things are really fast we can support a key value lookup and at 20 to 50 microscond. So notice this is like not even millisecond level. It's microscond level and everything's on a single machine and we are using like realistic data sizes like from a 100 gigabytes to one terabyte database like for all of these experiments like exactly how large it is it doesn't matter that much like because for at least for one and two like the scaling is logarithmic. For three the

scaling is square root 10. So even though the data sizes like are slightly different for these experiments, it doesn't matter that much. Okay. And we can handle 200k queries per second on a single machine. And I guess the state-of-the-art implementation uh is uh an implementation by our company. Uh it's open source at this uh URL. So what about ORAM plus 2PC? And for this the state-of-the-art is a open source implementation called Poggram. the the paper is not out yet but the implementation has been out for a long time. It's open source. Uh the paper is going to appear in crypto this year and you are looking at so if you care about optimizing the online time you are looking at about 30 to 40 millisecond

online query latency for each memory lookup. If you care about total time like let's say I care about the offline um work as well you're looking at roughly 300 to 600 millisecond per query. uh these two require these two bars are not based off the same implementation like you need to make different optimizations to optimize for different metrics and then pirate is piano and I think ling also has a paper maybe it has some slight improvement over these numbers um but I think all of this on the ballpark is like kind of the state-of-the-art so this is really um just dominated by the network latency like you are looking

total online latency about um 100 milliseconds but out of which actually in this experiment 60 millisecond is the just ping latency the the time it takes to even just send zero bytes. So basically the the compute is only like 12 millisecond per query online. >> So for the for the first setting what is the nonoram access cost? So let's say I I use a TE and I'm querying but I don't use an ORAM >> it will be a lot faster than 20 to 50 microsconds is like basically ORAM it has like you know you have to access this uh tree path right

>> right so >> so actually I had this interesting discussion with Serini Davidus from MIT whether at this performance and it's still worth implementing Orammy hardware I think the answer is inconclusive like it may still make sense. I mean this I think at some point you need to consider the cost uh whether it's cost effective to like actually implement OAM hardware or in software because software can achieve like really fast performance already. So I think the answer is inconclusive like maybe it still makes sense uh to speed it up by implementing in hardware but it requires some further investigation.

>> Yeah. >> So in the P numbers you included the network latency. Uh yeah this 100 millisecond includes 60 >> in the microcond example you did not right >> you mean pog >> the first one the t >> oh this is just happening on the server side so so it's like on a single machine but whereas yeah this doesn't in in include the time where the client sends the query to the server. Um it's just like assume the query is already on the server. uh so measuring the the lo local latency on the server where whereas this is in indeed taking into account the sending the query to to the server so

that's where things are I mean you can see actually these crypto-based approaches are catching up like they have very promising performance already like you know you can even argue they can be deployed in applications that are not so performance sensitive and of course in performance hungry applications like you know when we talk to like let's say the flashbots like they're doing it for block building and there when you talk to block builders they'll tell you they care about 1 millisecond delay. So there really you want to use the uh TE based solution. Okay I I also want to thank my students who did all this amazing work.

Uh and before I tell you how these schemes work um I I want to ask a seemingly naive question but actually maybe it's this is not a joke question. uh perhaps like when I teach 451 algorithms to undergrads like they'll be easily convinced that linear is no good and logarithmic square root 10 is good but actually when you talk to the more sophisticated audience like cryptographers or real world practitioners who are implementing the these things they'll actually ask the same question why don't we just do a linear scan so why not and I I can give you some concrete performance numbers so signal today they are running or plus te they have servers and their implementation is like I think about 20x

lower than ours. And if you use a linear scan inside the TE with no crypto, that's what signal actually tried back in 2017 and they were actually performing a highly optimized linear scan because they're doing batching and stuff and they required 500 servers back then. uh and signal also looked into performing a linear scan wrapped in crypto like using classical P schemes and they estimated the the computing bill to be 300 million USD per year. uh so so this also I think there's a also an interesting lesson to be learned from this because latency actually is not the only metric you care about like for instance like these classical P schemes

can be easily parallelized like they are trivial to parallelize so you can parallelize the latency away but you cannot parallelize the computing build away okay so for this reason you know we perhaps like these linear solutions are not too great when to have these huge data sets. So in today's talk I will tell you two extremely simple schemes an ORAM scheme and a P scheme and and I I unfortunately I won't have time to tell you how to build RAM which is like the second category. Okay so let's first start with OAM. Uh I will start with a little bit of history how we actually got here. At the very beginning uh in

around 1986 uh that there was hierarchical OAM proposed by Goldri and Ostroski uh and hierarchical OM can achieve log cubed n where n is the data size it achieves log cubed n overhead and they also prove a lower bound that any scheme must suffer from logarithmic overhead and then uh there there's a line of work that tried to optimize hierarchical OM and there's a paradigm shift around 2011 And we proposed this new paradigm called treebased OAM and they're extremely simple schemes and this is the kind of scheme I will tell you and you can get log squared n in theory but actually in practice it just behaves like a single

log n because these two logs log ns are not equal like one is a log base 2 n and the other is a log base something large n and that log n is just like two or three in practice and then you know very recently we've seen these uh large scale real world deployments >> the log squared is tight at least in the theory the theory right >> login is tight >> oh I see >> so there are works that even in theory get login >> there's there's works that we have a paper that actually gets login um but I guess like I think as of today the practical practically optimal scheme and the theoretically optimal scheme are not the same okay so I'll tell you how these

treebased OMS work and and before I do that uh let's take a look at a simple straw man scheme suppose we are just going to permute the blocks in memory like start each block at a random position and then perhaps let's say the memory uh the adversary like the server doesn't know uh this this random permutation the advantage of this is like if I want to access any block let's say I want to access logical block nine I will just end up visiting a random location and it seems like this should be safe to disclose So what's the problem with this approach? The problem is like it's okay if you just make one access and in fact it's even okay if you promise you are going to access each block at most once.

uh so this is what I call one time security but once you start accessing the same block multiple times you start to release a statistical information like you can see uh frequency and you can also see high order statistics like co-occurrence and and these are you know very leaky and you can perform statistical inference attack. So in fact the reason why this approach is not secure is very similar to why deterministic encryption is not secure and the lesson we should learn from this is that the blocks have to move around in memory and in fact every time you access some block it has to move around instantly. So this is the key insight to keep in mind as we go over the scheme.

So how does a treebased OM work? Uh you know obviously you're going to have a tree. Uh each bucket each node in the tree is called a bucket. Actually in the OM community like the biggest debate is not whether or schemes are practical for large scale real world workloads. It's actually whether the tree is upside down or not. Okay. >> I was about to say >> yeah this is a tree that you draw like as if you were a normal person as opposed to computer scientist. Yeah. So in inside each bucket there's a finite number of slots and and each slot can start either a real block or a filler block. So a real block is encryption of actual data and the filler

block is just encryption of zero. So the filler blocks are there just for security. Uh and for now you can imagine all the blocks are constant size except the root uh all the buckets are constant size except the root bucket is like logarithmic in size. Okay. So the most important invariant is that every block is going to be mapped to a path and this means the block can reside somewhere on this path. Right? So in this example uh this block at logical address X resides on the blue path and I will first cheat a little bit and assume that the CPU can start a large position map that remembers where every block is. I'll get rid of this assumption at the end.

uh and I I also want to mention that you should assume all the blocks are encrypted and every time I access a block I read or write the block I will always reenrypt it and write it back. Uh so the server cannot tell whether I've changed the block or not. Uh and the only thing the adversary can see is the access patterns because of the encryption. Okay. So now reading a block is very simple. If I want to read block X, all I have to do is, you know, visit this blue path, read and read every block on this path and once I find the block uh I want, I will hold it in my hand, meaning store it in some CPU register and then uh if it is not the block I want, I just re-encrypt this the same thing, write it back. If it is the block I want, I

reenrypt zero and write it back to the same slot. So this is how we read a block. uh and at this moment let's revisit the key intuition like after we read a block it has to be relocated immediately so how do we relocate it the most natural idea is I will pick a new path and assign the block to a new path so suppose I happen to pick the green path uh and I want to write this block in my hand to this green path and the question is where on the green path can I write it I mean obviously first I will update the position map to record the fact that the block has been relocated to the green path and now I want to actually write it and I want to decide where on the path I can write this block. Uh so

the first question is like can I write it to the leaf node? A lot of you have seen this already and you know the the answer should be no like we cannot write it directly to the leaf node. And what's the reason? The reason is because if you just directly write it to the leaf node you are declaring to the server. You're you're saying out loud oh hey you know I've read something from the blue path and now I'm writing it to the green path. So the next time if you are requesting the same block again you'll go to the green path and the server can see the linkability. Okay. Yeah. And now for the same reason you should not write it to any of the internal nodes because even though the internal nodes don't reveal the entire choice of the path they reveal partial

information about the choice of the path. So in fact the only safe place to write it is into the root bucket. So okay I'm going to take my block and write it into the root. The root is on every path so it doesn't leak the choice of the new path. I I guess I I I still need to address you know how I can keep writing things to the root but let's set that aside for the time being. If I'm doing this then security is easy to see is because every time I make a request I will go to a random path and importantly the choice of the path has not been disclosed before and this is because when I write it back I always write it to the root. So I don't disclose the choice and this is why the scheme is secure and the only thing that's left to

resolve is like I cannot keep writing things to the root because the root will become full. So how do I deal with that? There's a background maintenance process called eviction. And eviction is like trying to move things close towards the leaves to make sure no bucket will ever overflow. And a simple way to do eviction and this is the reason why the scheme is called pathogram. So in pathogramm the eviction algorithm piggybacks on the read path. So suppose I've just read something from this blue path. I will rearrange the blocks on the blue path to pack them as close to the leaf as possible. But just keep in mind I cannot write take any block on the path and write it into the leaf because that may not be the leaf the block wants

to go to. Right? So I have to do this carefully in a way that respects the the path invariant. So in some sense pathograms eviction algorithm is the most aggressive eviction algorithm possible like you're going to uh evict as aggressively as possible on the read path while subject to the path invariant. So we show that if the root bucket has size slightly more than logarithmic and let's say all other buckets are constant in size and actually four is enough and then we prove that except with negligible probability no bucket will ever overflow and this proof is non-trivial even though the scheme is looks like it's almost trivial. The proof is non-trivial and thankfully the proof is non-trivial because otherwise reviewer B would have

said your paper is trivial reject. rejects. Okay. Yeah, this proof requires some sophisticated stochcastic analysis of this randomized process. Uh, and there's only one last question left. I have cheated so far by assuming the CPU can start a position map. Yes. >> What's the probability over? >> Uh, the you mean the sample space? It's over the randomness of the in the algorithm. The algorithm is assigning make this random path assigning these to random paths. So I need to get rid of the position map and the solution is just one word it's recursion. So I will take the position map and instead of storing it in the CPU I will store it in

a smaller OAM and now I get a even smaller position map and I recurse until the position map is constant size. uh so if your block size is large enough let's say your block size is at least four login and that means every your position map is going to be a constant factor at least a constant factor smaller than the original data set so every time you can shave at least a constant factor off so after at most log log steps you'll get to constant size so this contributes another login but the thing to keep in mind is that the block size in practice like in SGX uh it's like a page it's like 4kb And in practice the the recursion depth is just two or three because the block

size is reasonably large. Okay. So the total cost is log squared and in theory but because one log has a large base in practice it's a constant. The algorithm is very simple. It's just just a simple tree data structure. There's no cryptography at all. You are essentially just seeing database performance. This is not cryptography performance. It's just database performance. Algorithm can be described in 16 lines. Even if we count lines like and end if n and4 you can print it on a t-shirt. I want to mention that when you implement these algorithms for real world enclaves, you should not just take the pathogram paper and implement as is. And the reason is because when we write these algorithms papers, we implicitly use the word word

RAM model like including your algorithms textbook like and the there are like you know all these popular algorithms textbooks and implicitly everyone uses the word RAM model and here we assume like you know you have a CPU that talks to memory and you are reading every cycle you are reading one bite reading and writing one bite and we count uh the running time of the algorithm by counting how many steps it needs. Whereas in practice we have a more sophisticated machine like for enclave architectures. Um what's important is that the page swap is a heavyweight operation like every time you perform a page swap like you read and write 4 KB of data. Um even if you just want to read one bite

like it doesn't actually make sense for the enclave to try to fetch just one bite of data from outside the enclave just because of the this high overhead of this context switch. uh in particular what happens with the page swap is that you have to make a system call you you have to perform encryption and decryption and if like the data is actually residing on disk you also have to make disk swap. Uh so this actually in the algorithms literature there's a nice there's actually a whole line of work dedicated to this kind of computing model. It's called the external memory model and in external memory model we care about not just optimizing the compute cost but also the uh they call it the IO cost and in particular in this context the IO cost is the page swap cost. So you can take these uh ideas

from external memory algorithm literature and optimize uh these OAM data structures and it actually makes a big difference in practical performance because what you'll get is an asympto improvement in this external memory computing model. And this is one of the reasons why our algorithm can our implementation can outperform the others u by a large factor. I mean of course we also have other algorithm optimizations and also actually I want to mention our our algorithm actually uses circuit OM rather than path ORM and this is because once we use these external memory algorithms to optimize away uh the page swap overhead then actually the computation overhead becomes more

important like if you don't do anything your page swap will be like 90% of the overhead and then we are kind of like we can kind of balance the page swap overhead and the compute overhead and we are at the point where we have to further optimize the compute overhead and this is why circuit ORM is better than path OM and also I want to quickly mention that not everything have to use an ORM yeah >> so when you say compute overhead we're talking about microsconds or nanoseconds at at that point because I guess at the register level you know when you're accessing L1 it's going to be much smaller right >> yeah so we actually also make our I I didn't say it explicitly we also make our implementation doubly or strongly ability oblivious meaning it's even

oblivious inside the enclave. Even if you launch cache timing attacks, you cannot observe access patterns within the enclave. So that that is the reason why we need circuit ORM because we need to like in path if you want to like make the eviction algorithm oblivious, right? you you have to do these oblivious starts on the path and I don't know we've written all these papers about that but circuit or like what's interesting like circuit OM was originally proposed for an MPC setting but it turns out it's like useful for enclave and I I think Facebook also uses circuit OAM rather than path or maybe they realize the same problem Ela are are you saying the IO is no longer the bottleneck

>> in our implementation it's it's kind of balanced because we made the IO So sufficiently small. Yeah. >> Yeah. I mean like in practice we can go into more details because in practice like there's also there's some difference between whether there's data residing on disk or everything is in RAM. Like this 20 to 15 microscond is kind of like you know it also captures when maybe even some things are sitting on disk. It can it's like maybe 15 microcond. If everything is in RAM maybe it's more like 20 20 microcond. So not all the time do you need an ORM because ORM is like a generic compiler that can take any program and make it oblivious but often times like you have these concrete data structures and algorithms that you care about and you

can do much better than generic OAM like you know there's a a long line of work on this topic like starting with oblivious data structures and we also know like algorithms that are aminable to parallelization can be made oblivious without going through the generic OM transformation like for instance Since if you are looking at map produce and spark and in the theory in the algorithms literature this is called massively parallel computation. So a different kind of MPC and you can actually transform an MPC program to oblivious MPC program with constant overhead. So that login even just goes away and and there's also like very nice work by Ling and and David Heath like this oblivious immutable memory model or

the single access machine model and they also can capture a large class of algorithms. So this is why in ongoing work we are building oblivious STL which is kind of like oblivious counterpart of standard STL library and we are going to ship these libraries with like highly per highly optimized customized oblivious algorithms and to to end this part of the talk here's another large scale application of ORAM and so they are available in Pittsburgh coffee shop. So if you come to visit me in Pittsburgh I'll take you to one of these coffee shops and buy you a Oram donut. Okay. Okay, so let me tell you how to construct private information retrieval.

Again, this is going to be an extremely simple scheme. Uh you it's almost don't need any crypto background to understand it. Okay. So how do we solve the PI problem? Uh one strong man solution and this actually is an example of classical P uh is to use fully homorphic encryption. So imagine Tim is going to encrypt his query X, send an encryption of the query to the server and the server homorphically evaluates the query over the database and sends back encryption of the answer and then Tim will use the secret key to decrypt the answer. Uh and the problem with this approach like is basically the bandwidth is uh ideal. It has constant or logarithmic bandwidth.

But the server computation is very costly because the server has to take a circuit that encodes the whole database and evaluate the cipher text using this large circuit and that takes linear cost. Uh so this whole approach we can call it classical PI. uh it was first proposed by core Adall in 1995 and since then there has been a line of work dedicated to studying classical P uh and PE people have shown you can construct uh classical P not just from FHE but also from various other public assumptions u but all of them suffer from the same drawback like the compute has to be linear and in fact this is shown to be inherent because if there's any location

in the database you don't have to look at then it reveals the information that the client is not interested in that position. I tried to find a real world application of classical P. I guess of course it has to be tiny scale. So I did find a tiny scale application. Google is using it to fetch device unique configuration and while guaranteeing privacy. So this is like if you have Chrome Chromebook or something like maybe there's like a 100 different configurations and you want to find the configuration that fits your Chromebook.

Okay. So obviously when you try to use it and you know for your large database like signal did the exercise uh and they they were disappointed because it would cost more than 300 million USD per year. So in order for PI to scale to large database we have to rethink the problem definition and beimo at all they proposed the pre-processing model in 2000 and the idea uh so so they proposed the this model called server prep-processing and in server prep-processing you are going to take the database and compute some locally decodable code over the database and which will make your query more efficient and then there also has been a

line work dedicated to serverside prep-processing. Uh and the latest is a groundbreaking result by Way Kylen uh Lin Muk and Wix. And this one the stock best paper award and they show we can do it with poly logarithmic bandwidth and compute assuming the server expands the database into n to the one plus epsilon where epsilon is arbitrary small constant and they need ring lwe. So this result is very nice because theoretically it's dream right you know we cannot hope for anything better um I mean maybe except if we can improve the server space it would be nice um but concretely it's it has astronomical constants and it's like very very far away from

practical so the question is like can we actually have a truly practical P with sublinear computation um but without these heavy constants so I I want to talk about a line of work called client side pre-processing. It was first proposed by actually in two different works like one by Patel Adall and the other by Corrian Gibbs and Kogan. Uh I think the Coran Gibs and Kogan paper is more often cited because they actually made it sublinear whereas like I think the Patel Adall paper didn't make it sublinear. Um so I I will talk about our scheme called piano and I haven't explained what climb prep-processing is but actually it'll become obvious as I explain the scheme.

It's a different kind of pre-processing. uh so what we can achieve is square root 10 cost so square root 10 bandwidth and square root 10 compute uh with like square root 10 client space and the only cryptography we use is due to random functions so that's why the scheme can be so lightweight and this is actually theoretically also interesting because we know for classical P that doesn't do any pre-processing this kind of result is not possible because any non-trivial classical P will imply public key uh cryptography and another nice thing is that in this particular model all of these trade-off like let's say the the bandwidth and the compute trade-off is optimal the bandwidth and the client space trade-off is also optimal

under these assumptions so we have like some lower bound papers and there's also like some other lower bound papers earlier like by Coran Gibs and others okay so here's how the scheme works in the pre-processing phase uh what do we do we take this data set it has n indices and we'll divide them into square root 10 chunks each of size square root 10 and then we will sample one random index from each chunk. So this allows us to write down a set. We we are going to sample a bunch of sets and each set has one random index from each chunk and this this parity is defined as the database value at those indices and then I XR all of them. So I

use parity of the set to denote uh this equation. So I will do this roughly square root n times and I will write down square root n sets and their parodies and this is the information the client is going to obtain during the pre-processing and that's why it's called client side pre-processing. So besides this information the client is also going to get some entries called replacement entries and they're very simple. This just says for every chunk I will pick polylog random indices and I will start the database value at those indices and these replacement entries will become useful later.

Okay, so this whole thing is called uh hint and the client will start the hint and it will facilitate the online queries. So if you do this in a naive manner, you can see the space is very large because to store each set requires square root 10 space and have square root 10 sets. So in this case the client has to have linear space and it might as well just store the whole data set. Fortunately, we can use PRF to compress them. Like instead of generating the set randomly, I will generate a pseudo randomly. And this allows us to compress the space to square root 10. And this is the only place where crypto will show up. And the rest of the scheme has no crypto. And basically during the prep-processing phase, the client can write down this hint by making a single streaming pass

over the database. And the client only has to have square root space. That's why it's called a streaming algorithm. So it's not hard to see this. I will not go into details but if you just think about it a little bit more you'll realize how to do this. It's a homework exercise. Okay, let's go to the online phase. The client wants to fetch index 5. What does the client do? It will find a hint that contains this index. Let's say the second hint and it will find a replacement entry that belong to the same chunk. Okay. So with this in my hand I can now compose the query. The query is basically the set but I have to be a little careful because my query is

five and I don't want to disclose that. So I will this position that corresponds to my query. I will replace it with this replacement uh entry and remember this replacement entry this index is a random index within the same chunk as as this position. Okay. So this is the set sar. The server just sends back the parity of the set. The client can compute the answer by just computing the simple XR. Uh this part comes from servers response and these two comes from the local hint and you can easily verify this gives a correct answer. The security of the scheme is easy to see because this set sar just contains a random element from each chunk and it's independent of my

query because I did this replacement. Okay. So you you might might think okay you know we've solved the problem but actually there's a catch because the scheme so far works only for one query. If you make more than one query it's not secure and do you know why? >> It's like a onetime pad thingy where if I have two things I can sort them and get it. >> Not not exactly. So the question is like once I consume the hint what do I do with it? like I I I've have this database of hints and I consume one of them, right? The like the maybe the most natural way is to delete it but the problem is like if I delete it then it skews the distribution of my hints like the remaining hints are slightly less likely going to contain five and that

make makes the new queries slightly leaky. I mean you you can also you also cannot just like uh leave it there because if so like the next time you use this hint it'll end up leaking information. Okay so that's slightly problematic and how do we fix this problem? So in order to support more queries I will introduce a simple technique called broken hint technique and the idea is really simple. Once I consume a hint I'm going to throw this hint away but replace it with a random hint subject to containing my query five. Because if you think about it, the distribution of this set is a random set subject to containing five.

So I just have to sample a new random set subject to containing five and replace the consume hint. Yes. >> Is it the same idea as uh what you have in a hierarchal or level? I think you access one and then you replace it by some the next time you kind of ensure that you're not accessing the same thing. >> Maybe there are too many hierarchical ORAMs. Maybe it's like >> I I mean the original Gold Rick Ostroski work >> I think they they have like a one time they they they require one >> one time memory >> access each location only once >> right >> uh >> so this is not using something similar okay >> maybe there's a way to view it such that it's similar but maybe we can discuss it offline there are too many different hierarchicals

okay yeah so so the only problem is like I'm replacing it with this random set but I don't know the parity so what do I do I will just mark it as broken and hope that I don't hit it the next time. If I do hit this entry the next time, I will not be able to obtain the correct answer. So I lose incorrectness. So this has allowed me to transform security error into correctness error. And to fix the correctness error, I just need two words parallel repetition. I'm going to repeat this game like roughly logarithmically many times. And they don't ampl if you repeat it like super logarithmically many times you can amplify the correctness failure to negligibly small and in practice you don't actually have to even suffer from

the parallel repetition overhead you just have to do some additional trick to get rid of the parallel repetition overhead but I I won't go into the details you can read our paper so the scheme so far just to quickly summarize uh in the pre-processing phase the client makes a streaming pass over the whole database consuming square root 10 space and it'll record a square root 10 size hint uh in roughly linear time and online query. Client sends a set to the server of square root 10 size. The server sends back a single parity. Client computes answer. So extremely simple. There's just one last thing I want to mention. The scheme so far supports only square root n queries. So let's assume the database has been randomly permuted. So every time I query a distinct index, it's going to land in

a different chunk. And I I've said you know I I prepare polylog replacement entries per chunk. So after I throw these square root n queries into square root n chunks like you know with extremely high probability I'm not going to be able to I I I will not will not run out of uh replacement entries. But if I make more queries I may eventually run out of replacement entries. So how so how do we um extend this bounded scheme to unbounded? And that's just one word we can do pipelining. Uh basically we are going to run the next phases pre-processing and in the current window of square root 10 queries and you can see that because this pre-processing cost is linear

amortized to square root 10 queries just introduces square root and overhead for each query which we already incur anyway. So if we implement the scheme and compare with classical P we are like about 900x better in compute than classical P. So so the the actual response time this number is diluted just because it's like already ping latency dominated like in this experiment the pin latency is much larger than the computer overhead. Okay. So I will try to end and talk about some open questions and but before I do that like I haven't had time to talk about this two PC OM plus 2PC I will just quickly talk about how we got here without going into any technical detail.

>> Ela the P this is honest but curious uh adversary or >> the server can if the server is malicious it will harm correctness but it doesn't learn any privacy is against malicious server. Yeah. Okay. So before I ask open questions about ORM plus 2PC, let's quickly look at how we got here. Uh so there's practical land and there's theory land. In theory land, RAM model 2PC was first proposed in 2012 uh in in a paper with many authors by Gordon Adall and then and then god RAM was proposed like around 2014ish. Uh the difference is RAM model 2PC is like doesn't care about the run complexity.

If you have a competition that runs in T rounds, the RAM model 2 PC will give you a protocol that runs in T login rounds. So it's very very interactive and this RAM requires it's only two rounds. No matter how long the original competition is, you can only have two rounds. Um so it did not take very long before we made RAM model PC practical. And this is actually when Kartik was a PhD student and we were all happily doing research in Maryland, we like worked on all of this. Um but it took much longer for people to make gabble ram practical like uh so so cartic will be happy to hear now actually there's a new state-of-the-art for ram model to PC which is our new gabo ram but I also

want to mention that we are also building on others work like the work by heat at all um so I I think this is in some sense both encouraging and a little bit disappointing it's encouraging that you know we've made a big step forward since 10 years ago but on the other hand I feel like there's very little work on RAM and that's why when I was like looking for a baseline to compare to I I was surprised that even my work own work 10 years ago is still like a baseline is like the state-of-the-art baseline okay so on the theory front there's more like um fancy algorithms 16 gabble RAM and RAM model FH I I will tell you what they do so essentially goblet RAM the

bandwidth is not succinct like if you have a computation that runs in t time you would have to consume roughly t bandwidth whereas in theory you can compress the bandwidth to almost constant like poly logarithmic but you need like some uh stronger assumptions like indistinguishability offiscation or ring lwe and I think the interesting question is like whether any of these theoretical technique can be made practical so this is also like one place where theory starts to diverge a little bit from practical because in practical we don't really care about just minimizing one metric like at the cost of let's say compute right like what we care about is just the end to end time and in some sense it's like the bottleneck cost that we care care about like really in pract when we implement these things in

practice we'll always try to balance the bandwidth cost and the compute costs um but that that's not saying like these theory things cannot be we cannot use the techniques from these theoretical works so I think the exciting open question here is can we take any of these techniques here to design a practical gabble RAM or RAM model 2PC or MPC technique and that achieves actually better concrete performance. Uh so you can break this question down into more final grain questions but I'm not going to try to do that here. So let me talk about open questions along the P side.

Uh so this actually comes back to what it was asking earlier. So PIR like even though it looks like the performance is similar to doubled RAM and there are a couple drawbacks like one is the practical implementations today only support retrieval it doesn't support general purpose computation uh if the database is updating very very fast like in blockchain scenario like the updates are much much faster than the queries and then you have to pay the every client has to pay per update which makes things more messy in practice. Um so so I I think you know whe whether we can overcome these drawbacks are interesting open problems but I I do want to mention like P does have like P

has one advantage over RAM model 2PC which is like the trust model because this P you can do it with one server whereas two PC you need two servers okay so here are some interesting open questions can we make it work for fast evolving databases and and the one reason why these client side prep-processing schemes uh are not compatible with fast evolving databases because the client has to be involved with the updates. So perhaps like we can try to make server prep-processing approaches more practical. That's interesting question. Uh and if you want to support general computation like it would be more like you know making brand model FHE practical and again you can break these things down into smaller questions but I I will not try to do

that. Okay. So I I gave this talk in Simons and that's why this is measuring time in terms of Simons. So I I want to just quickly say where we were where we are and where we want to be in Simons 2035. So okay the Simons 10 years ago like I was giving talks about treebased ORAM and then this mo most recent Simons you know we see ORM has large scale practical deployment. Uh so I think as as far as OMT are involved you know we want to actually make this more widely deployed um you know have more open source libraries to support people's development efforts or perhaps you can also be more hopeful and ask in 10 years

we don't want te anymore and this is why we want to have two and three uh so 10 years ago as I mentioned for garbled RAM for RAM model to PC and the state-of-the-art was like this these interactive protocols. Um, and then for P, you know, we started with classical P. So I I'd like to think that today we are kind of like at the similar paradigm shift for these other like, you know, because this was like a paradigm shift that made the practical deployment possible and I'd like to think that we are kind of at a similar paradigm shift today. So hopefully 10 years uh later we can see large scale deployments of these uh technologies as well. I I want to mention like there's

actually things beyond cryptography that are really important uh for this line of work like when is crypto meets programming languages. Uh and this includes not just formal verification but actually um language design and optimizing compiler is very important. You want to make it easy for people to program these things and also instead of like a posterior form of verification actually using type system and information flow to just catch possible mistakes a priority I think this approach will have a long way long way to go. Yeah. Okay. And crypto meets algorithms is also a I think interesting intersection that is often overlooked because like there's a lot of work that's trying to make crypto practical

these days and a lot of them actually requires algorithms techniques like for instance I talked about one example of using external memory algorithm techniques in the context of ORAM but there are many examples like this like people are trying to parallelize cryptography and there's a lot of interesting techniques in the in other MPC literature you know massively parallel computation literature that are potentially helpful Um and then another interesting connection is like crypto has a different model of computation like every different crypto like you know HSS uh homorphic secret sharing has its own computation model NPC has its computation model you know ZK has its computation model like R1CS and we actually don't understand algorithm design in these crypto models of computation so well like we don't have a

good understanding what tasks can be um um uh programmed efficiently like in these models Okay. Yeah. Thank you very much. >> Can can you explain again the the use case in the blockchain setting? I'll be doing a P over the entire ledger or some uh >> there are both use cases like for instance if let's say I just want to make unis swap transaction oblivious then you only need to do it for the the the the part of the database for unis swap transactions like all the unis swap accounts and but more generally like for instance vitalic wants this built in the RPC node like you know alchemy infur gas

so so This would just be enabling it for the entire blockchain. I think you we we'll start from the state because the state I think is querying more often than the ledger but potentially you know we can do it for the ledger too. >> I see. Then uh do you know roughly speaking on what order of magnitude that size is? Uh I believe the le ledger is like maybe on the order >> legend is the one or two terabytes but the state >> the state I think is on the order of 100 gigabyte someund 300 gigabyte some so because we also have reasonably fast uh linear P right now that's uh maybe one gigabytes per

second in terms of u processing speed. So if it's a 100 gigabyte database, we need 100 seconds. So that's still >> actually if you can give me like a cost. I think Signal cared more about the cost for linear P. Yeah. Because for them the problem it was like 300, >> right? But comparing to the number theory based ones, right? Using the latis based ones, it's uh at least thousandx better than that. >> Yeah. If you have actually updated measurement number for that, I think this so signals number was taken using the state-of-the-art scheme in 2023. So it's like two two years old.

>> I have a broad question. So from a practical standpoint, how important do you think is it to work on improving or making them practical versus improving oblivious algorithms, specific oblivious algorithms? That that that's a good question like I I think we need both because there are applications that just need all our oblivious key value star like like for instance Ethereum signal meta like I think they they need an oblivious database um but what's interesting is like while they are developing this oblivious database like signal for instance they want to make it distributed and when you start doing these things you end up needing like oblivious sort and like these

oblivious building blocks. So I think like they they're kind of they go hand in hand like even if you just want to optimize ORAM or distributed let's say oblivious key value store itself you you need to use like some primitives from oblivious S str and I think we are also like you know we did all this compiler work in UMD we are also trying to now make them like com commercial commercializable like production ready uh because yeah I think a lot of the times if let's say you have a customer that just want some specific computing task like you know you had this nice work graph SC right like for a lot of these parallelizable computing tasks we don't need ORAM we just need oblivious

start >> maybe quick comment following up on Ling's uh question I think there are ORAM light client protocols right or I've heard uh light clients um >> I I think there's a there's a company also besides our company there's also another company called automator and they are I they're saying they want to do ORAM. I I don't know. I haven't seen an actual implementation from them yet, but I think it's also on their agenda. So, I think Ethereum is also talking to them as well, >> right? Because I've heard some discussions, not sure what's the state-of-the-art or if it's um >> I I I haven't seen their implementation, but they are they have been saying they want to do ORM. Yeah,

>> I noticed that there are some uh data access protection paper under relaxed uh notion called differentially private opivers. Um do you think like how does that help to make the data access pattern um project more realistic and do you think this notion makes sense? No actually differential oblivisness can be important because a lot of times um uh so I think differential oblivis is most important when your case your worst case cost is very large and in practice you don't want to suffer from the worst worst case cost like let's say for database drawings like the worst case cost is quadratic and if you want to be fully oblivious this you that means you have to be quadratic whereas in in practice like most of the common queries

in practice are just linear or quasillinear so in these cases you want to kind of pat it with some nice so you actually just see quasy linear overhead in practice uh so so that I think is not just a log factor difference it's a polinomial factor difference so so even when we are working on this oblivious implementations like uh I I was talking to some uh company providing cloud service yesterday and they want to build in into container like let's say make the file system layer oblivious and there uh if you are doing that at the file system level there's going to be some leakages about the file length and that I think you can secure with this

differentially oblivious techniques.