Oblivious RAM: From Theory to Large-Scale Real-World Deployment with Elaine Shi | a16z crypto

Transcript

uh all right good afternoon everyone uh welcome to today's a16z crypto research seminar very pleased to welcome Elaine she uh professor at Carnegie Mellon University uh Elaine has worked on all kinds of different things across computer science for example she was visiting us last summer give us talk then about mechanism design funnily enough today she's speaking about the very first thing I ever saw her talk about many years ago oblivious RAM and getting us all up to date about uh sort of the Practical impact of it so Elaine all yours thank you so much for the introduction so I'm going to tell you about oblivious Ram or RAM for short and how it evolved from Theory to actually large-scale real world deployments So the plan is the following I'm going to first tell you a signal story and

it's also the like motivating example for the talk and then I'll tell you how to construct oblivious Ram I think some of you may not have heard about oblivious RAM and it's a simple algorithm which I teach to my undergrads in my crypto and algorithms class so you'll learn about it today and at the end I'll talk about the applications and the challenges towards real world deployment okay so let me begin with a signal story okay so signal you know as you know it's a private messenger app it provides end-to-end encryption for the messages you send and they also want to support private contact Discovery so in contact Discovery uh it is what you think right uh Tim sends his address book to signal

and Signal tells Tim okay you know here are your friends they're also on Signal you you can connect to them you can send them messages uh okay so this is very useful future but Tim is worried that you know of course his contacts are top secret so he's hesitant to do that and so what do you do here's a naive solution so let me first start with the strongman solution and then I'll tell you what signal is doing so here imagine signal has some trusted Hardware a secure CPU in the cloud you know Intel sjx for instance and and you can think of the secure CPU as creating a hardware sandbox so anything outside is encrypted like the communication is encrypted data

at rest is encrypted and the data is only decrypted inside The Enclave where the computation takes place okay so you may think this solves problem because you know other data contents are encrypted we must be safe but actually if you think about it more carefully encryption alone doesn't quite solve the problem and it is well known that access patterns to even encrypted data can leak very sensitive information like in this case and if signal observes that the server is accessing let's say a record corresponding to etai then they can know that itai is Tim's friend and and you may be tempted to think that just by promoting all the user records

on disk can solve the problem but actually this doesn't really solve this problem in particular if you just promote the data a signal can still learn the social network graph like even though it's anonymized and what's wrong with this uh you know if you actually have a non-social network graph with actual user identities you can correlate the structures structure of the two graphs and the anonymize everyone in this anonymized social network and this was actually work um you know so I had to work along these lines and also Arvin nariana and his co-authors also had several papers the anonymizing social networks and the moral of the

story is like even though graph isomorphism we don't know an efficient algorithm for the worst case instance for these real world instances it's like very easy okay okay so so this is like signals problem but access pattern leakage itself is actually a really more General problem so let me show you some other examples of access pattern leakage so here's a medical example let's say you are storing genomic data in the cloud let's say 23andMe and the doctor is accessing certain Snippets in the genomic data so for instance if you see the doctor is accessing Snippets related to liver problem um you know you know maybe the patient is being screened for liver problem and this is sensitive medical information

okay and this is another example everyone's familiar with binary search like you know if you have a database you want to do binary search on top of it you would look at the middle element depending on the result of the comparison you either recursed on the left half or the right half so now imagine you can see the sequence of other axises you can learn exactly what key is being searched right so this basically leaks everything about the query um so more generally from a programming language perspective if your program has a conditionals that depend on secret variable let's say this if depends on the last bit of the secret key and then depending on the uh which branch is

taken you have different memory traces in each branch and in these cases just by observing the memory traces you can learn the value of the secret variable okay so so finally here's another example this is an actual attack that was launched by um some researchers in UT Austin and Microsoft research and they showed you know suppose I'm running some off-the-shelf image processing software inside sjx enclave and the only thing I can observe is very car screen access patterns namely which Pages memory pages are being fetched into the enclave and even with such car screen access patterns they can pretty much recover like you know the location and shape of the objects so this is a a pretty significant problem and the question we

want to ask is how can we probably defeat access pattern leakage and meanwhile preserve efficiency so this is what we are going to answer today okay so let's go back to Signal story right so signal encountered this problem back in 2017 they came up with a solution they said okay we are going to linear scan the whole database upon every query linear scan is always safe because it doesn't leak which record is being accessed and they're actually doing something slightly smarter which is a batch linear scan so whenever a batch of queries come in they answer the dispatch in a single linear scan this is a linear cost scheme obviously so n is the total number of memory blocks a total number of user records beta is the batch size

uh and because they had this linear overhead they had to have 500 servers um to basically work with the load they have okay So eventually you know time move forward in 2022 something exciting happened they got rid of the batch linear scan and they changed to pathogram which is an algorithm that we had published back in 2013. actually Hubert is one of the collectors on this paper and he is also in the audience okay so you know now we have basically log squared overhead instead of linear and they were able to cut down the server cost by 100x after deploying path around and also yes Tim so did they just find your paper did you did you tell them

they should do this instead or what's the story it's there's actually a story because back in 2017 they published the blog post and they were claiming that the batch linear scan was outperformed in pathogram so likely they didn't have a the correct they didn't Implement pathogram in the way that they should have done um okay and also actually the I will mention later that this log squared has very small constant so it is like just really log squared actually in practice it really just behaves more like log n and I will explain why later as well so basically if you are a signal user and Signal you know asks you to send contacts just feel free to feel safe to do that they are running my algorithm it must be very very secure

yeah okay all right so you know let me actually tell you about how I believe this Ram algorithms work um but I'm also going to tell you a little bit story about this whole area how this area evolved over time so what is oblivious RAM and or Ram is an algorithmic technique that can probably obfuscate the memory access patterns and the security you get is very strong you can think of it basically it gets you the same security as encryption right um so at First Sight it's counter-intuitive because we know we can encrypt data but access patterns are a side effect of a program's execution so how can you actually encrypt side effects and and if you look under the hood I'll

tell you how these algorithms work but just at a very high level these algorithms are promoting the memory blocks and they keep shuffling them as you access them and in this way they can obfuscate access patterns and okay if you think of Oram here's kind of like a diagram that says what it does and the input is a sequence of requests every request is either read some address or write to some address okay and then um it will translate each request into a multiple physical accesses and the security it promises is that you know the distribution of these physical reads and rights should be independent of the input request the the

secret input data okay and um just just to distinguish like sometimes we also call these addresses The Logical addresses and the physical reads and rights are called physical addresses and if you ask okay what is the security boundary when you actually deploy or RAM on The Trusted Enclave this is what happens like you are actually running Oram inside the secure Enclave right this Hardware sandbox I talked about earlier and so everything inside is secure and you know the memory you can think of it as being the adversary right adversary can observe other memory accesses okay so let me go back to um or Ram right so

Oram was initially proposed by godric ostrovsky back in the 1980s and they showed that actually there exists asymptotically efficient or Rams right so remember the naive solution linear scan was linear overhead and they could construct something with log cubed overhead which is like very non-trivial in asymptotical sense unfortunately these algorithms are very complex and they suffer from astronomical constants so basically you really cannot Implement these algorithms the way they're described okay and on the other hand they also showed if you want a generic Oram scheme you have to suffer from at least login overhead so the overhead is defined and by comparing the overhead of the secure algorithm and versus the overhead of the

insecure algorithm so this is a multiplicative blow up question what does generic mean in this context uh generic if you want to have a compiler that compiles any program to oblivious counterpart so if you ask about any specific computation task it may not be subject to this lower bound but if you want a compiler that works for any program take an insecure program give me a counterpart that's secure that compiler has to incur login overhead I started working on Oram back in 2011. and back then uh there were actually a line of work already that tried to improve godric ostrovsky but they were still kind of working with the same framework they had proposed so it was

all these schemes are within the same framework but with some optimizations you could get rid of One login so you get log Square n but nonetheless all these schemes are very complex they basically suffer from the same drawback of godric gostrovsky they're not practical okay so I you know I looked at the space and I I asked okay so you know what are the important questions uh for Oram I mean obviously the first question is can we ever make Oram practical and the second question you know I was interested in is like oh there's this obvious gap between the upper bound and the lower bound can we bridge this theoretical Gap okay so I uh started working on Oram and I guess in the next I don't know maybe more than 10 years we were able to like answer both questions I mean the first

question I told you like about the large-scale deployment of Oram I'll tell you actually the algorithm um for the second question I will not focus on this theoretical question in today's talk but we also were able to bridge this Gap and we were able to construct an optimal RM with login overhead the theoretical construction and the Practical one happened not to be the same one I mean it would have been nice if there were the same one but the theoretical is like actually not practical so I'm going to be focusing on the Practical side today okay [Music] um the space is actually complex a little bit complicated there's like um there are simple algorithms that are actually optimal if your block size is

large but if you want to be optimal when the blocks the block size is just like log n and which is the standard assumption in the word Ram model in other algorithms literature then you the scheme we have is complicated uh so yeah I mean I guess it's not easy to explain why it's complicated but but anyway maybe when you see our construction um I mean the construction I'm going to tell you today is log squared overhead in theory it behaves more like login overhead in practice okay so let's see how to construct an Oram so actually I'm not going to directly tell your path or Ram I'm going to tell you a scheme that's predecessor to pathogram it's called the binary Trio RAM and basically this binary or Ram itself is a framework for constructing

orams and once you understand the framework I can tell you what pathogram is in just one sentence and also by the way this framework basically completely departs from code break and ostrovsky original algorithm so let's first think about destroyment I mean this is actually the same straw man I mentioned earlier so what if you know you just take all the memory blocks and you randomly Premiere them and now what do you get from this if you access some block you don't know which logical address it is so it seems like this gives you some security but it's actually not too much security and the issue is because if you go back and access the same block you are linking statistical information you'll see okay this block is accessed

more often than others or maybe these two blocks are often accessed together and you can then have statistical inference attack and this is for the similar reason like deterministic encryption is not secure because it leaks statistical information okay so permuting things in memory gives only one-time Security in other words if you only access every block only once then it's secure but if you you know access the same block multiple times it's no longer secure and tomorrow we should learn from the story is that it seems like every time you access a block you have to relocate it because if you don't relocate it the next time you access it you create a linkability you leak statistical information so that's

why I want you to keep this Insight in mind it will come up again when I talk about the scheme so this is the key inside the blocks have to move around in memory and in fact as soon as you access it it has to move around okay so as I mentioned we have a binary tree based approach and this is like a sometimes it's a simple data structure that I teach to my undergrads um every node in the tree is called the bucket the bucket has finite capacity a bucket can start two types of blocks real blocks and filler blocks so the filler blocks they don't include any useful data they're just there for security okay so the most important invariant of the scheme is that every block is mapped

to some random path uh so here uh let me first cheat a little bit and assume the CPU can start an entire position map which records where every block is so this position map as you can see is very large it's linear in size eventually we do want to get rid of it and we will but for now let's just live with the idea there's a position map and let's say the position map I want to access block X I can look up the position map study my CPUs cache and I find out okay X is on the blue path and now all I have to do is I just have to read this blue path and I'm guaranteed to find the block X somewhere once I find it I will remove it from the corresponding location and now I'm

holding it in my hand in the CPUs register okay so at this moment remember what I said the key Insight was right at this moment um it is important to relocate this block I have access because otherwise the next time I access it I will go back to the same path and let that leaks information so how do I relocate it the most natural idea is just to pick a new random path let's say I happen to pick the Green Path I want to move the block x to the screen path and I mean of course I have to update my position map to reflect that but I also actually have to write the block somewhere on the Green Path and how do I do that

this is a little bit subtle because like you know the question is where on the screen path can you write the block X can you write it to the leaf node you find a filler bucket huh you find a filler orchid but the issue is I guess the question is it secure to like let's say just write it into the leaf also by the way maybe I didn't make it clear I'm going to assume everything is encrypted so the only thing that adversary can see is the access patterns okay so I'm now going to just repeat the encryption again and again yes Jacob I'm missing something because if the adversary can see that you've read one

block wherever you write it like that was I want the adversary just be able to see that you just yeah exactly that's the reason so it's not secure to write it to the leaf node right because the leaf node reveals the whole path like you cannot Leak with the whole path is because if you lick it the next time let's say you are accessing the same block you you can see okay you know this block from the blue path was relocated to the Green Path and now I'm going back to the same path so that leaks information so you cannot write it here that's crossed out and for similar reason you cannot write it to any of the internal nodes so even though the internal notes are like similarly more secure they still leak partial information about the path okay so the only thing left is the root

I mean of course it's safe to write it to the root because the root is on every path if I write it to the root I don't leak information about the New Path right so let's do that and I mean we are going to encounter a problem if we always write to the root but for the time being let's say we are doing that and if this is this is actually the scheme then we can actually think about the security the security is actually easy to see because every time you access something you are going to visit a random path and not only so the path has not been disclosed before it's a fresh random path you haven't you haven't seen the choice of the path before yes just to clarify are you reading every are you like taking a read from every bucket along the path yeah

you have to read every location because you cannot disclose which location actually contains the block you want but when you're doing the new right you're just writing what's to block the you have to do a fake write on other positions so you also cannot tell which was the location it was written to okay yeah but that's actually a great question so essentially the implicit assumption is like the reader and writes they always go hand in hand when you read it you always write it back you either write the original blob back or you write an updated blob back and you always re-encrypt the new new thing that you're writing back okay so um this is very nice but there's one remaining problem we have to solve and the problem is obvious because okay

there's a problem and the problem is just like we cannot keep writing to the root because the root will over overflow very soon so how do we deal with this question okay so basically what I'm going to do next is first I'm going to tell you how to resolve this overflow issue and then remember I've been cheating so far I still have this position map in the CPU cache I will get rid of that and then I'll talk about some improvements to the algorithm including pathogram so let's first think about how to resolve this overflow issue okay so to prevent overflow our idea is also pretty simple we are going to have some background eviction process and the

eviction process is like some maintenance process that tries to move the blocks up the tree towards the leaves um in a way such that no packet will overflow with extremely high probability so the question is how do you design this eviction process there are two seemingly conflicting goals like we want to spend a reasonable amount of work on the eviction right so we if we spend too little work then like things can become crowded and overflow if we spend too much work then the cost is too high So eventually when we count the cost we are going to amortize this background eviction process to each request so the cost will be amortized to each request okay so how can we kind of balance these

two goals so here's a first attempt and this is approach suggested by the original binary tree Oram so the idea is also very simple every time we make a request we are going to pick two random packets at every level for eviction I mean of course I mean the root level has only one bucket so we're just going to evict that bucket twice okay so what does it mean to pick a bucket for eviction so here's what it means suppose this packet is chosen for eviction what I will do is I will scan this bucket find a real Block in the bucket and I will evict the real block to one of the children and which child should you write it to there's only one correct answer because that block has already been assigned to a random path and depending on the path you have

assigned it to you should either go left or go right so in this example let's imagine the block you have chosen should be going right so on the right hand side you are making a real eviction on the left hand side you have to make a fake eviction you have to pretend you are evicting to this packet by reading and writing every position in the bucket and this is for security it hides which child you are actually writing it to okay so similarly if you happen to pick this packet for eviction and the bucket doesn't have any real Block in it you just make fake evictions on both sides to hide the fact that the bucket load is empty so if you do this you can see actually the eviction process itself doesn't break security because the access pattern of the

eviction process is completely independent of the request so because for every request I'm just picking two random packets at every level for eviction and I'm reading and writing that bucket chosen as well as the two children right okay so as I said the eviction process doesn't leak any information and this is easy to see and what remains to um um I I still need to convince you that this actually solves the Overflow problem and in fact we can prove if you set the packet size to be roughly login then with extremely high probability none of the buckets were ever overflow and if you want to prove this you can either use queue in theory or use like

measure concentration bonds I'm going to give you a very rough intuition of the proof so in fact the intuition is if you look at every single bucket the decue rate is ties as high as the encure rate and this is why I'm choosing two buckets rather than one at every level for eviction so that two matters so if the DQ rate is twice as fast as the incurate you can roughly think of it as an mm1q and the Q length the probability the number of jobs remaining in the queue exceeds are is exponentially smiling r um so this proof is cheating a little bit because there's actually dependency on these buckets but if you just apply like the discrete version of the Burke's

theorem um you can essentially think of each bucket as being independent what do you do with the leaves what do you do with the leaves oh leaves is guarant leaves we use a just Cherno Bond how did you think leaves is like you are throwing empowers into amp beans and everything like if the bean size is Logan there's no overflow with extremely high probability so because everything is assigned to a random Leaf right so you're throwing M bars into Ambience actually you only need to have like the last level only needs to have like and over log and buckets so if you throw empaths into an over log and buckets like you're fine

the the last level you don't have to evict yeah because the boss and beans that already covers it okay um so this is our um first algorithm and the cost so far is like for every access I claim it incurs log Square cost because you are reading a path and then you pick two random buckets at every level for eviction right bucket size is login so login Times login you have log log N squared um okay so I still have to convince you how to remove the position map because right now I'm assuming the CPU starts this large position map and this the answer is one word recursion okay so how how do you get rid of it you

have this position map you start it in a smaller or RAM and then your recurse recurs until the position map is constant in size and then you start that in the CPU cache so as long as your block is large enough to start two um indices like the the path information for two blocks every time you can reduce the size of the orange by a half and after login stages you'll get down to constant so this recursion does incur an extra log n overhead so basically log N squared becomes log Cube but what I want to mention is actually this recursion login is a different set of log n because in practice this recursion depth is like usually two or three and that's because this log has a large base like

the block usually can store Many Many indices so that's why like for this team it's log cubed in theory but in practice it behaves more like log squared um and we can get rid of one of these logins which is the bucket size login like so so like right now the bucket size is login at you know the question is can we make it constant and indeed we can and this is exactly pathogram but if you make the bucket size constant you have to make the eviction more aggressive so what does this mean like in the binary tree program I talked about the eviction is kind of silly right because I'm I chose this bucket for eviction I'm scanning the whole packet anyway but I only ended up evicting a single block why not just try to evict as many blocks

as possible because I've already touched in this bucket right so okay so pathogram says okay we are going to try to use the most aggressive eviction algorithm possible and this allows us to make the packet size constant I mean of course the proof of this is like a pretty non-trivial um so the idea is every time you read you are going to evict along a path and you will take the other blocks along the path and you will try to pack them as close to the leaf as possible so evict as far as possible except that you have to always be subject to the path invariant so remember every block is assigned to a random path and you you can never break that environment during eviction so this

is the basic idea of the pathogram algorithm if you do that log Cube becomes log squared in theory in practice it's more like login because one of the log has a large base okay so the advantage of this algorithm is like it's really simple the pseudocode is like 16 lines of pseudocode it we are even counting and different and four it's so simple you can print it on a t-shirt okay so let me summarize tree based orams right so these are like simple data structures in my opinion they're actually even easier to you know describe than buying the research trees for me it's easier to teach this than buying research trees when I bet you

mean balance binary yes but balance binary search trees exactly okay so um the key Insight is like a block is remapped to a new random path every time you access it and and you have to relocate the Block in a way that doesn't reveal the New Path and that's the key insight and and for the eviction process we have to design it in a way such that you know there's no overflow and typically for these constructions proving no overflow is actually the hard part like the security proof is always kind of trivial okay what do you do with those overflow and so I mean you can actually tune the parameter such that the Overflow

probability is as small as encryption failure and so I mean in that case if there is indeed overflow depends on whether you want to go for security failure or correctness failure there are two choices if it's you want to go for security failure you want want to be perfectly correct then you just like somehow retry a different path okay so let me talk about uh the applications right right now there's like a lot of interest in industry and about orams and okay so I saw on Twitter like Andrew Miller used to have this decision tree about do you need a blockchain so I try to do something similar for Oram do you need an Oram okay so here's a very simple decision to

do you need trusty Hardware pretty much if you do you need Oram like this is basically it goes hand in hand with Intel sgx and other chassis however unless your program is not interesting unless your program is like a simple straight line program that doesn't you know have branches or it doesn't like have data structures I mean but the set of such programs is very limited and and I I'm not talking about cryptographic secure multi-party computation at all in this talk but the answer is the same for secure computation like this is actually it's not often talked about but if if uh secure multiple computation actually becomes practical you also don't want to take these programs and convert them to circuits you'll be using Oram because converting programs to circuits will incur polynomial blow up so anywhere you

need secure multi-party competition and your computation task is interesting you'll also need Oram okay so of course I'm going to talk about blockchain applications right so our Ram is gaining a lot of attention in blockchains and here are you know some applications I've heard of and privacy preserving transactions and smart contracts I'll briefly tell you the flashbot use case and I'll tell you about like privacy preserving lightweight clients I'll just go over them pretty quickly so privacy preserving smart contracts and transactions so I'm actually still in Andrew's slide okay so there's like several layer one blockchains that are encrypting transactions on chain and

then the miners are running basically Intel sgx or classic Hardware to run these transactions okay so you think like you know encrypting the data gives you security but actually you know it does not um and the problem is that so these are some of these companies that are doing this and the problem is like I think this is Andrew's attack like he looked at the um this memory trace for secret Network and from this memory Trace you can actually pretty much learn all the information they claim to hide like the Sanders accounted receivers account uh so you got like basically no security okay so I mean what's the solution to

this problem and of course you want to like use Oram right Oram will hide the access patterns and you can no longer see who's the sender who's receiver I mean of there are other like examples like let's say your smart contract is accessing some nft and if the miner can see that okay you are interested in this nft they can front around you and like you know basically buy the nft to jack up the price and so so like they can do this Arbitrage okay flashbox is also interested in Oram and this is their scenario okay so what is flashbots and so you may have heard of like D5 and you know uni Swap and Arbitrage opportunities opportunities

and blockchains right so I don't have time to go into details but at a very high level so there are these um parties called Searchers and they're just watching transactions posted to the public pool and they're looking for arbit charge opportunities so let's say they find some transaction that they can Arbitrage and how do they do the average charge they are going to both front round and background the transaction this is called the sandwich attack and they create a transaction bundle and now they are going to work with flashbots to submit this bundle so they basically submit this bundle to their private pool and flashbot Promises okay you know I'm going to create a blog that contains your bundle and we are going to split up the profit for instance on okay and so what flashbot wants to do is

like they want to run this private pool inside sgx Enclave because they want to guarantee um the security for their customers like they're also saying you know even individual users not just searches like even individual users you are encouraged to submit through our private pool because we can't give you the protection against front running and back running but of course they also have to like convince their customers like they themselves are not running their transactions right so I mean again whenever you have trusted Hardware you'll need sgx because you need Oram because otherwise you know flashbots can still see or you're looking at this nft I can front around you that way so this is another potential scenario and I think Andrew actually mentioned to me they are actually looking into Oram

for this reason because they want to like earn their customers Trust um privacy preserving lightweight clients is another application like your phone cannot start the whole blockchain block but it wants to access some transactions so mobile coin is like using Oram for some some purpose like this but but they actually they actually have two different usage usages for Oram this is one of them okay so so these are the potential applications in blockchains I'm sure it's not an exhaustive list but so if you know other applications I'm very happy to talk to you about it and before I conclude I want to mention our ongoing effort and some of the challenges we Face to deploy this technique in

practice and so we are building what's called oblivious STL so this is like a standard library for oblivious algorithms and more specifically you can think of it as the oblivious counterpart of the standard STL library right now C plus plus LTR Java also has its own Library like but we want to provide that I believe it's counterpart and we want to offer things like data structures like map set priority queue range query data structures we want to have common algorithmic building blocks like sorting shuffling graph algorithms and so on and so forth uh so let me explain why I think there is an urgent need for such a library um so even though as you have seen Oram is like a very simple binary treated

structure that's actually still interesting there's still like challenges towards deployment and the first challenge is just lack of awareness like for instance signal it took them five years to realize they should be using a pathogram rather than like a naive linear scan and it's also very interesting to contrast or RAM and zkp like zero knowledge proofs I mean of course these are very different algorithms they're used for different purposes but like zkp has like a lot of awareness in the blockchain community the algorithms are actually much more complicated than Oram I would say uh the the the this Market is very segmented because there are so many different algorithms and there's no one-size-fits-all algorithm because every algorithm is better at this but maybe not so great at something else

and the barrier of Entry is higher like if you want to find programmers to program ckp I think it requires a lot of expertise whereas in comparison orm algorithms are actually very simple but there's like less just less awareness that you need Oram um there's actually for almost every task you need there's a unified solution um the barrier of Entry is also lower like a lot of these techniques are actually very mature from an academic perspective um it's probably worth saying I mean go back a slide yeah I mean a lot of the current interest in the left column is driven more by scalability concerns than privacy concerns yeah whereas there's no kind of scalability story on the Oram

case that that's right I mean unless you are doing linear scan then that will be a scalability concern all right okay so there's another reason why we need to have this oblivious Str like you know one question is why not just like throw a Ram at everything right just Implement pathogram and call it done and the problem is that if I know what I needed is a map a priority queue I need sorting I need this graph algorithm like breakfast search you don't actually have to go through the generic Oram transformation there are often a much more efficient oblivious algorithm for your specific task so if we are going to create a library for these common data structures and algorithms you can often get like a login saving on top of just

naive Oram everything okay so there's a line I'll work on you know I believe it's algorithms uh there's a mismatch of performance metrics uh and let me explain what this means like when we study algorithms let's say undergrad algorithms right when we teach algorithms we implicitly use the word Ram model and this is when your CPU is reading a memory but you can read and write data in bytes in single bytes and in this simple model it's very clean and the nice thing is like the competition overhead is the same as the memory overhead so that's why when we learn algorithms we talk about running time there's only a single overhead metric there are no two different metrics but when it comes to sgx it's not the

case it's like if your enclave wants to access some data that lives Outside The Enclave so your enclave may need to access some encrypted data that lives in insecure memory or disk you have to do a page swap you have to talk to the operating system hey operating system get me this page and the page is at a 4kb granularity if you just want to read one byte you still have to pay this 4kb granularity costs so this this model actually has a name in the algorithms literature it's called the external memory model I mean external memory model was invented initially not for sgx it was for something else but sjax is actually a perfect fit for the external memory model so what we really

need is external memory algorithms and why is are these page swaps so expensive because to do a page swap you have to do a context switch you have to do a system call you have to encrypt and decrypt the page right like the thing you fetching you have to decrypt it but you also have to catch something out and you have to encrypt that sometimes if your data cannot fit in memory you also may involve at this swap which is heavy weight okay so so let me show you why external memory is important for sgx and type implementation so this is a work that came out of Berkeley it's prior work a BX so we uh so the number shown here is is not their exact algorithm because we couldn't run their code we asked them

for help and we couldn't compile their code and we didn't get enough help to compile it so we created a version that's better than their algorithm like we did some some things they didn't do right we did it correct and what happens is like we can see the page swap is more than 90. so I think for their actual work is probably even higher than this because we already did optimizations um so that's the dominant cost and then we basically we did everything using external memory algorithms this paper is appearing in usnik security and my student Alfonso will be giving the talk in August um so we are saving like a 10 to 100x factor that BX on real world data sizes

and with this Improvement the page swap is only like roughly 60 overhead and compute is like 40 percent uh it actually I mean initially it should be quite surprising to you like for something as simple as like so this is I believe it's map not Oram but it uses exactly the same techniques as or around the algorithm I showed you um it's like some some simple binary search tree um some binary tree data structure so it should be quite surprising that we can get like so much saving out of like a simple data structure and finally there's a challenge which is like the security of the implementation itself and I guess we can also look at a blue X as an example like if you look at their code it doesn't actually achieve

the security they claim to achieve like because um the code they are running inside The Enclave like it has this branches that conditions on secret variables and every branch has a different memory Trace so like if you can do cash timing attack like you can actually learn the access patterns inside the enclave so this scene this kind of problem is like not something we should leave the programmer to figure out because there's actually very nice uh formal method technique it's called um memory Trace I believe it's type system like with my collaborators like we had several papers that show how to just automate the task of making sure your pro your program is memory chased oblivious

so you said there's a cache timing attack here uh so in the sjx context and the weakest security you want is like the page swaps are oblivious but that's usually not enough because if there's a co-resident and user application the user application can do a cash timing attack like it can pollute some cache line because the user application and Enclave application they are sharing cash so by doing these cash timing tricks you can learn exactly inside The Enclave which memory location is being accessed and there are lots of papers that show how to do this cash timing attack so we understand it very well I see yeah I mean that makes sense but then is the example here actually cache timing or is this just just uh you know

this one is a cache timing issue because I mean like like sometimes you can even just attack like by measuring the the runtime of the program like depending on how bad it is because like because each each branch has like different memory traits like even the timing Behavior will be different in some sense um so but anyway like from an academic perspective this is again a solved problem like these techniques are very very mature uh it's like what remains is just to like actually get them deployed in the real world okay um so this is why like I think oblivious Str will overcome a lot of these

challenges we face in terms of like deploying Oram at a large scale and we also want to go for like these features uh in the medium term like we want to have parallel versions of these algorithms we do have some you know algorithm algorithmic works on these topics like I believe it's parallel algorithms we want to implement some oblivious programming abstractions so if the programmer uses these abstractions we can convert them to an oblivious counterpart much faster than generic Oram and I mean we want to use these type system techniques compiler optimizations to make sure your I believe is uh implementation is the fastest possible okay um we have started working on oblivious STL but I think we really want to scale

up the effort and so so far we have released an oblivious map and our next step is to release oblivious sorting algorithms but we have a lot more things to do and there's some preliminary open source code you can look at and mostly this I believe it's STL is in the first URL and the second one contains like reference implementations of like all Ram algorithms okay so to conclude I want to show you another large-scale application of Oram apparently if you go to Pittsburgh you can buy or Rams Donuts at coffee shops so I will take you out and buy you an Oram if you come to visit me do you need an Oram yes thank you yes I have a question about orange so I

guess in your implementation whenever you fashion data from the lift level you first put it to the roots right then I guess it takes certain amount of time for it to migrate from the route to the leaf again and I guess you cannot access that piece of data in that time period otherwise you can like because the read is accessing the whole path so as long as you are always moving it along that path you are reading that path you can always find it somewhere oh so you pretend I I read all the way to the leaf level but I don't actually yeah the read reads the whole path so it means it reads the root every time I see yes yeah I guess there's kind of a gap between the linear scan and the logarithmic ones so in practice do you

see cases where you know square root n or into the one over K will be better trade-off for some some use cases squared is more like a login and these constants are very small so so if there's an asymptotical difference that you can probably find some very narrow region or when where you can argue or maybe square root N is a little bit better but it's like I think very very very narrow reaching probably yeah so I think one of the challenges that might remain and maybe all of these applications is about distributed um trusted Hardware clients so like even in Mobile coin I think they have um I understand they're one of this the the

pastor they talk about it but they they it's kind of an unsatisfying things if they want to have lots of servers then each server has to either have like a Shard of the data or something if you want that's actually a really interesting question so if you have a map reduce or spark you can get constant overhead it's no longer login uh so I I think this is one of these citations I I hit there parallel like I guess one of these papers is about okay mapreduce and uh spark in the algorithms Community it's called the massively parallel computation model it's another MPC massively parallel competition and we show that any massively parallel computation can algorithm can be made I believe it's with constant overhead and

that constant is a small constant and so so there's a different interpretation of your question I think I've been talking to some like companies who might be interested and another kind of parallelization they need is it's like I think it was systems people call Shady but it's essentially I believe it's parallel Ram uh like I mean you don't want to implement a previous parallel Ram in the way they are described in the theory papers like I think Snoopy is like maybe one practical example of oblivious parallel Ram so essentially these Oram algorithms are very amenable to shutting they're just naturally designed like to shut you can cut off the the part near the root of the tree and then it becomes multiple subtrees and the access pattern is

naturally load balanced because every request just goes to a random subtree so that's why they're so amenable to shining oh actually also back to your question you asked about square root n but the thing is also we don't know any algorithm that's square root n that's like simpler to implement than the login version the log squared and version and I think that's another reason why you don't want to go for square root 10. um actually uh yeah two quick questions I guess so is there kind of Interest or something special happening for like MPC friendly Oram if you know going back to Andrew's question yeah and the other one is about maybe Hardware friendly over like is would something change or would you do the same thing yes that's a great question so um I assume by MPC you mean multi-party computation

if you want to implement the Oram not on kind of one you know one secure Enclave but basically as a as a multi-party computation yeah so I think for most MPC type scenarios what you need is circuit or Ram so what I talked about is path and the difference between circular RAM and pathogram is in circuit Oram you want the Oram it's algorithm itself to be implementable in a small circuit um and there you need to change the eviction algorithm you can get exactly the same asymptotical bonds as pathogram but you are changing the eviction algorithm such that the eviction algorithm itself can be easily implemented in a small circuit because you are going to compute that circuit with NPC whereas for Hardware trusted Hardware scenario really you can just work with pathogram but like for

something like Intel sjx you don't want to just Implement pathogram as is like as in the original paper you want to apply this oblivious external memory algorithm techniques on top so you can minimize the number of page swaps yeah and also I think there's also some details I omitted like basically if you want um if you want to resist cash timing attacks that you want even the access patterns inside The Enclave to be oblivious then you actually need to implement the Oram the eviction algorithm itself in an oblivious Manner and this is like um there's some some tricks to to like do it I believe it's like efficiently like what you need to do is use oblivious starting

um I guess like for instance a BX paper I I guess for some strange reason they were using a quadratic some improved version of a quadratic algorithm but actually it's actually well known what you should do is like you use like two oblivious sortings to implement the eviction algorithm yes if you had to run all around when the distributed fashionist you're saying cut out the top of the tree and then maybe distribute the sub trees and can you is there work to making that Byzantine resilient like if you want to allow for fail I you know I've actually seen the paper that has the title Byzantine and something all around in the title I haven't looked I I confessed I haven't looked at the paper but I

think these are very good questions because from my experience talking to these companies like a lot of them are interested in some extra property on top of Oram like sometimes it's maybe crash fat tolerance I mean yours is a stronger version of Crash Valley they want to talk tolerate crashes they want to like maybe sometimes have some database type guarantees um so I think these are also you know some of these um engineering efforts we have to make to make these games like uh suitable for these uh these types of deployments 10. so so obviously you need randomization in a lot of these algorithms is that kind of a self problem like getting good Randomness kind of Within These uh yeah how to get good Randomness I I

mean I guess there's this is like a somewhat orthogonal question I I guess yeah I mean there's like some work by afghanists I've seen some papers he has looked at this Randomness generator implementations in Linux and proposed like some more secure variants so so I think we can just directly rely on that line Network you can use I mean I think all you need is like generating Randomness once and then you can use a PRT to extract it to stretch it right you can use like AES to to stretch some short random C to non-randomeness and this would suffice here so so really you don't have to like

always sample true Randomness for the whole algorithm okay ah thank you so much yeah if you are interested in oblivious STL talk to me I'm happy always happy to talk about it okay sounds good thank you [Applause]