Episode 407 - Private Information Retrieval (PIR) with Alex Hoover

Transcript

Welcome to Zero Knowledge. I'm your host, Anna Rose. In this [music] podcast, we will be exploring the latest in zero knowledge research and the decentralized web, as well as new paradigms that promise [music] to change the way we interact and transact online. This week, Kobe and I chat with Alex Hoover from the Stevens Institute of Technology about PIR, or private information retrieval. Alex explains what makes PI such a unique primitive.

It allows a client to retrieve an entry from a public database without the server ever learning which entry they asked for. We trace the 30-year journey of PI from its information theoretic origins through single server computational constructions to the modern version which are using clientside pre-processing schemes. Along the way we cover the many variants of P keyword P batch P symmetric P. We also explore why P matters for blockchains from light clients privately querying state to Merkel proof generation for private transfers. And here where P is already deployed in the wild today. From the conversation, it sounds like P is one of those incredibly useful

primitives, a bit akin to ZK, and we do expect to see it to be adopted in a big way in the coming years. So, hope you enjoy. Now, here is our interview with Alex Hoover all about PI. [music] So today, Kobe and I are here with Alex Hoover, cryptographer and assistant professor at Stevens Institute of Technology. Welcome to the show, Alex. >> Thanks for having me. I'm excited to be here. >> And hey, Kobe. >> Hi. >> So for today's episode, we're going to be diving into the concept of PIR. That is private information retrieval. And this has come up a number of times over the last few years in conversations.

Kobe, I feel like you've brought it up a bunch of times as like a topic to dive into. So, it's very cool to finally get a chance to do an episode on it. >> Yeah, it's a topic I'm interested in for many years now. >> Why don't we actually start with a quick definition of PI or Pier as some people call it. Alex, do you want to just tell us what this actually is? >> Yeah, absolutely. So pier or pir is really powerful and also very unique cryptographic primitive. I would say fundamentally what it protects is a lot different than other types of cryptography you might see. So it's a lot different than like compared to encryption or even like authentication like signatures. The task of what private information retrieval protects

is that it protects an what's called an access pattern or you can think of this as like how a user is querying a database. So what we should have in our minds when we think about PI or pier is there's some database that's public. So we don't care about confidentiality of this database. If you want that you can use other cryptographic tools to get it. P is focused on a public database and you have a client who wants to learn some particular entry of this database. So think of the database just like as an array for simplicity. Some people think of it as like Wikipedia. Maybe we can think of it as like the blockchain, right? and we want to access some particular block of the blockchain, right? Everyone knows the blockchain if they want it, but some people don't have the, you know, capacity to store the

blockchain entirely on their local state. And so for these clients that don't have this much memory, they can use a PI protocol to obtain one of the let's say blocks from the blockchain without whoever's holding the blockchain learning which of the blocks that they retrieved. Right? So that's the simple definition and there are all sorts of P variants that have been defined over the years. This was introduced 30 years ago and there have since been lots and lots of variations to try to make this either more efficient or to get you some sort of specialized uh feature.

>> Yeah, I think I think it's pretty interesting. like I I'm sure we'll cover a bunch of the variants and what has changed in the last I guess 20 25 years but it has become increasingly important for like blockchain applications and a couple that come immediately to mind which were the ones that I've seen around me were around for example light clients so if clients want to learn the value of something in let's say the statry of Ethereum It's something that they would either have to get the entire state or they would have to ask someone but then they would give up privacy which which kind of sucks for some reason either for

reasons of just privacy. You don't want people to know what you're looking at but also for reasons of censorship for example that can be annoying. Another one that that I think captured my attention was around more of the privacy oriented protocols. So let's say identity or private transfers where there you really have to maintain a lot of data and to like synchronize the entire blockchain >> in order to just be able to even make a transfer and that's something that P if it is efficient enough can handle and help but >> let's see how efficient it is when we talk. [laughter] >> So Alex I want to learn a little bit

about you as well. Thank you for that definition for actually to both of you for what P is. We will dive more into it but yeah let's learn a little bit about you Alex. Why are you working on cryptography and why this topic in particular? >> So I started in cryptography during my PhD basically. So I went into my PhD I don't know like eight years ago now and I was interested in I guess the CS theory broadly and then while I was there I took cryptography class that was a lot better than the one that I took in undergrad with my someone who became my adviser David Cash and that got me really interested in cryptography broadly and so then I worked with him to finish my PhD and during that time most

of what I worked on were what I would call like either oblivious ious or encrypted data structures. So this is a very broad class of cryptography that's interested in trying to outsource some data structure onto a maybe honest but curious maybe malicious server and then supporting different data types like you could have an encrypted dictionary or an encrypted multimap. And so I studied this which is connected to other primitives like oblivious RAM. And then toward the end of my PhD, I went to work as a student researcher at Google and I worked with the crypto team there. Uh, and they were also very interested in this broad class, but they had me work on private information retrieval, which I kind of just fell in love with because

of all the different variations and there are just so many open problems and it's like this primitive that's right on the cusp of being like practically efficient for all these very many applications both like within blockchain and like throughout, you know, the ecosystem of secure computing. And so I just really enjoyed my time there and since have been working on it kind of persistently since then. >> Nice. It's funny because like I've heard it I mean we're at the Zero Knowledge podcast. I've heard it sort of from the context of ZK, but it's quite different, right? Like is it used in tandem with ZK? Does it borrow anything from ZK?

Could it be a ZK PIR? Like could it be a could you could you use ZK in this concept? >> So if you construe zero knowledge broadly enough, you could maybe think of it as a type of zero knowledge tend to on this show. Actually, >> I wouldn't say it if it's the traditional zero knowledge definition that you might get in like you know CS theory type class. >> Okay. >> But it there's a lot of applications where the two kind of coincide. So like >> in addition to the applications that Kobe mentioned like one kind of toy application if you just want like a really simple abstraction. If you imagine like a blockchain where like every transaction was like a zero knowledge proof of the transaction, right? So you have like this kind of uh you can think of this as like a write

privacy. like I write transactions on the block onto the blockchain but maintain confidentiality of what my transaction was >> and now you might care also about the read privacy right if I go and look at a specific transaction like I need to verify a specific proof and I go and grab it off the blockchain then the right was private but now the fact that I have gone and accessed that transaction might reveal something about the transaction that I'm doing now or who I am or what I'm interested in more broadly and so You can kind of think about it as like a type of read privacy >> in that type of application. Also, zero knowledge proofs can have applications in the deployment of P. So you can combine P with other crypto primitives.

Like I said, you can combine P with encryption to get confidentiality. You could also add zero knowledge proofs to provide some form of authenticity, which is kind of an active research field right now. >> Oh, interesting. To prove that what you're retrieving is actually correct, something like that. >> Yeah. So there's a recent line of work that has looked at what are called authenticated PI or verifiable PI or >> malicious PI. So these are all kind of I don't think we've settled on a name for this primitive exactly yet, but in some contexts you may want to protect against not just a semi-honest or honest but curious server. You might want to protect against a potentially malicious server who like might try to feed one

person one version of the database and feed someone else a different version of the database. That's what you want to prevent in in that setting. And like I said, this is very new. I think there are like some very generic techniques you could do to try to get some form of authenticity here. But the definitions are quite nuanced and the constructions are also interesting. Something that I'm currently like trying to pursue research on. So it's a little hairy. Alex in my knowledge there are a bunch of different constructions of P with very very different security assumptions computational assumptions and so on and this has been going on for a while for decades I guess so it would be interesting to learn about the whole journey that P went to and where it got

to like the information theoretic stuff computational constructions what's going on >> yeah that's a very long story, I guess, in in its entirety. But yeah, Pier celebrated its I think 30th birthday last year. It was introduced originally in 1995. Actually, it's older than I am, so I can't tell you the full story. I guess I wasn't there for it. But when it was introduced, it was actually introduced in like you said this information theoretic setting. So in this setting, you have you think of the database as replicated across more than one server. So you can I think two, three or in general K servers and then you have a client who issues a query to

each of these servers and gets back the database element that they want. And the security guarantee in information theoretic P is that each database's perspective the query sent to that or that server is information theoretically secure meaning that even given unbounded time that server can't learn anything about the particular query. But the real caveat in that definition is that there's this critical non-olusion assumption. So you have to assume that basically these servers don't collude with each other. If even two servers get together, right? So you have K servers in general and if two get together in a lot of these schemes, they can immediately learn the query that you

ask. >> And this is something that's been mitigated in the information theoretic setting. And like I said, there are lots of variants. But I would say that the focus after its introduction shifted away from this information theoretic P and toward what's called computational P or usually when people say P in the cryptographic community today they mean single server computational security. >> Yeah before we move on to the computational stuff. So just to try to clarify what it looks like for the information theoretic variants. So something that a lot of people in the let's say blockchain world are used to is kind of a threshold assumption where you know if you have a threshold

signature then t out of n can collaborate and construct a signature. So for example you assume that there is an honesty threshold but here it's very different like what you're saying is that if you have k servers then even if two of them learn like collude then you would have a problem already. >> Yeah that's right. So there are I will say there are variants of this information theoretic notion that have been defined and explored. There's not as much literature on them compared to that non-olusion variant. There's something called robust PIR where if you're are robust then you still preserve privacy even if our servers collude. Let's say there's also another variation. It's not called robust. I'm

forgetting the name now, but it's it's basically this you only need it's a threshold type assumption where you only need t out of the n servers to respond and the other ones could drop your query. >> Mhm. >> There are other ones where the servers that they don't just drop your query but they actually give you a maliciously constructed query and you only need t honest or like a majority honest type setting. So all of these have been explored. I think there are still open questions in the information theoretic setting for robust and threshold type PIR but a lot of the focus has shifted off of that in the community I would say.

>> So the focus today is on the single server computational model. What does that look like? >> So in the single server setting it's not possible to achieve a non-trivial information theoretic P. And so what I mean by that is in P there's typically a non-triviality condition because as I've described it right the client issues a query to a server and one trivial way to privately obtain the entry that I'm interested in is for the server to just give me the entire database. >> If the server just gives me all of the entries of the database, then I haven't revealed which one I'm interested in to the server and I can pick out the one that I care about and drop the rest.

Right. This is the trivial P. Yeah. Uh so that's the best you can do information. >> That's what people some people do that today. It's fine. Okay. >> Yeah. Sometimes you just have to download the entire database and if you do then that you know sucks but so that's the best you can do information theoretically in the single server setting and it turns out you can do better if you introduce some sort of computational assumption and there's a lot of literature on what kind of computational assumption you need. So in fact it turns out you need what's called like a public key type operation. So you can't do this just from oneway functions. That's a theoretical result.

So you have to use something like group operations on the server side or like lattice operations. So you have to use some sort of maybe expensive cryptography in order to answer these P queries and be computationally secure. >> Okay. But is that a bad thing? Is that something you're trying to like engineer away or is that just sort of like you can either do it where you download the entire thing or you will be using some of this expensive cryptography and it's kind of like those are the ends of the trade off space. >> That is a really really great question. So people aren't always happy with doing public key operations and so there have been other models introduced. So this lower bound that was shown basically only applies to PI that don't have any what I'll call client side

pre-processing. And this is something that's kind of taken off in the last 8 years. And it was introduced kind of concurrently by the some of my co-authors at Google introduced it in a 2018 paper and then kind of again by Corgan Gibbs and Kogan Euro in 2020 where they introduced this notion of like offline online private information retrieval. And this is one way that you can get around the need for public key operations. And in fact, it's basically the only way. There are some other lower bounds that show that in the kind of traditional non- pre-processing setting, you're going to need actually a linear number of public key operations. So there was a recent recent result that said P doesn't just require public key operations, but it actually requires a

number of public key operations that is linear in the size of the database. So you have to do like a whole bunch of like RLWE multiplications or something like that. >> Yeah. A bunch of Lis operations. So these lower bounds do they apply let's say if you're talking about offline online settings how how does that look like there is that [snorts] during each phase? >> So when you introduce pre-processing the picture gets a lot more nuanced. So the lower bound says that the total communication if the total communication between the offline and the online phase is sublinear then you must have used a public key operation.

>> Mhm. >> Okay. So what this means is that you either are going to have to use public key operations or the offline phase will have to be your expensive part. So a lot of these schemes will have an offline phase that can kind of be run in two modes. One is you stream the entire database upfront before you know the queries that you're interested in >> and then the client will store some sort of small localized hint and then online they're going to issue the queries using their hint and this online phase uses no public key operations. In fact, it barely uses any cryptography at all. All the server is going to do is like exor things together. It doesn't have to do any group operations. this offline phase. I mentioned that you have to do

it in the streaming fashion. That's basically to get around this lower bound. There are other things you can do. You could use public key operations in the offline phase. And people have proposed you could use fully homorphic encryption in general to compress the communication there. Currently, I think the FHE like offline pre-processing is too slow for practice and people have usually tested assuming this streaming setting. But that's also kind of an open question is to speed that up as much as possible for practice. >> Yeah. So the streaming setting for example could fit let's say the light client use case very very well if you allow yourselves to synchronize the blockchain once let's say because then you can query whatever you want.

>> Yeah there is like another bottleneck that comes up. So you do this one-time offline streaming phase. And the way that most of these schemes work is that you issue many queries using this one hint set, but while you're issuing these queries, you also have to kind of refresh your hints. And so you do ultimately have to like reddownload the blockchain, but it's amortized over many queries. >> That's one of the the caveats I'll say, but like >> amortized your communication will be like let's say square root in versus linear. So it's square root in per query.

>> I just want to kind of cover what you just said again because you kind of identified these like different ways that you're like retrieving this. So just kind of going back. It was like one is download the entire or like access all of the data. The other is use public key expensive cryptography and then the third is do client side processing on that first part I guess of accessing the entire data set and then some smaller and I'm guessing like less expensive public key cryptography for the online part and then you also mentioned using the public key in the offline. So yeah, I just I just am trying to follow like how do you shift that around so that it's the most efficient? Is that the question that you are all working on?

[laughter] Yeah, I would this is a very very active research field. So it's possible someone uploaded something on e-rint by the time you know this this goes out that you know kind of invalidates a lot of what I'm saying. Fortunately I think there are some broad things we can say and like recently I had a paper that extended some lower bounds and and showed that some things are impossible that uh we didn't know before. So let me slow down with the public key operations. So in these client side pre-processing schemes a lot of times the offline phase is flexible. So many of them are just trying to optimize the online phase as much as possible and then they say the offline phase can be done in one of two

ways. One of which is by streaming the database and one of which is by public key operations. Whichever one you choose there it doesn't matter for the online phase. In the online phase, there are no public key operations whatsoever. That's the >> main speed that speed up that they're trying to get. So they're the client maybe runs, you can think like as calls or Shaw 256 calls. They run those locally and that's mostly for compression. They send something to the server and the server does usually a very efficient computation. In many of these, it's literally taking database entries and like exoring them together and sending them back to the client.

Sometimes it's just sending the database entries to the client. It's just that the database doesn't send very many of these. And another thing that helps with this is that these online queries are much faster not just in terms of public key operations, but they're also faster in terms of their asmtoic behavior. So the each of these online queries only takes the server about square root in time if they're in database elements. So this server doesn't even have to access every single element of the database. the way that it would in traditional P.

So pre-processing speeds up the asmtotics and also can get rid of these public key operations that slow down a lot of things in practice. And the cost is that the client has to do this offline phase one time up front. >> Although that's pretty nice because you can imagine that the off phase you would be doing at home when you have a good internet connection when you're on your powerful PC and then you move the hints to your phone and then you can do whatever you want when you're on the go and on the plane with Starlink or whatever. So it's fine.

>> Okay. >> Yeah. I think it will depend on the application but I definitely I mean people have been interested in this I think for a reason because it does have some applications where it's acceptable to do this offline phase >> if the online side is not using any of the public key expensive cryptography what is it actually like what are you sending what how do you even like what does that connection look like is it interactive are you waiting for something to come yeah I'm just kind of curious what you're actually doing what are you sending >> so the it might help to go through a concrete scheme. I'll say up front that almost all PI are one round operations.

So they're they're not very interactive. Usually there's one query and then there's one response from the server. >> Maybe it's a good like opportunity to just jump to Plinko itself because then we could talk about that scheme, I guess. >> Yeah. So the the shape of these online queries might seem a bit mysterious, right? We haven't talked about how you would actually implement PI in practice and I guess for the purposes of you know right now we can just talk about this offline online or this client side reprocessing PI and so in this setting we can think of it abstractly as I'm I'm going to give a sketch of the original scheme of which like pretty much all the other schemes derive in in different variations and so the highle idea is in

the offline line phase I want to learn the exor or I'll call it the parody of some random subset of the database. >> What does that mean? >> Yeah, that's a good question. So >> noncomputer scientist here [laughter] >> imagine the client just sends like square root in indices. So the database is an array with in elements and I just want to learn square root in. >> So a small part of this array and I just pick these entries at random. I take them out of the array and I exor them together. I like add them mod two.

>> Okay. >> Okay. And that gives me one. So like if each of these entries is b bit long then I exor them all together and I get one b bit value. And I'll call that the par. >> And so the client in the offline phase stores a whole lot of these parodies >> which are like subsets of the larger data pool. >> Exactly. Exactly. And so the client will store also about square root n of these and we can pick the numbers a little bit later but the rough idea is that I want every single element of the database to appear in one of these random subsets.

So I just pick enough of them so that every element of the database appears in one of these hints. Then in the online phase what I'll do is if I want to query some index I then I'll find a set that contains I. Let's say so I have square root insets one of them has I in it and I'll go and find that I'll find that set and next to the set I have some par I have some B bit value that's the exor of those database entries now what I want to do roughly is I just want to take out I from that set and then send the set to the server >> like the the sort of the subset that where that lives is that what you're saying doesn't that reveal what you're looking for then

>> so what I'm sending to the server is a subset that doesn't have my index in it. >> Oh, >> but you're you're right to point out this isn't exactly secure. We'll fix security a little bit later. But yeah, so I I take this subset that has I. Yeah. >> I pull out I >> and then I send the remainder to the server. >> Ah, I see. >> Okay. So to the server, this looks kind of like a square root in minus one sized subset. >> But can it identify what the I is in that moment? >> Yeah. So in that moment the server could infer that I is not one of the indices that I did in fact send.

>> Yeah. >> So so you're right that we have some security loss there. We can fix this using a couple of different tricks. So you can either structure these hints slightly differently. That's what most modern schemes do. Another thing is that you just sometimes include I and you do this with a probability that makes the distribution like happen to match. So this is what the original Corgan Gibbs Kogan paper did. It was a really clever trick where like they just kind of fail sometimes. So if you do include I, you won't get the right answer, but then you can kind of just replicate it. So you can do it like 10 times and take like the majority vote and like you'll be able to get I most of the time.

>> Cool. Okay. So yeah, you send the subset minus the I and then do you get something back? >> The client is holding a par, right? It's holding some bit string that is the exor of every element in the set. And the server, let's say, sends back a parody that is the exor of every element in the set except for i, except for the index we're interested in. So what we can do as the client is we can just take these two parodies and exor them together and everything cancels off except the one entry that we care about this like specific entry at i.

>> And that's how you get the information that you want. >> Exactly. Exactly. Yeah. And to make this private, like I said, you have to randomly fail and multiply a few times. But actually, what's more common now is to structure the hints in such a way that you don't have to fail. You can just be a little bit more careful. Instead of picking random subsets, you can pick more structured subsets, but the same idea is is roughly there. >> Would you be picking subsets that sort of border on the eye? Like are you kind of I'm trying to picture this visually, but like are you kind of like mapping around this piece that you want?

>> Yes. Yeah. Yeah. Exactly. So you like in pretty much all of these schemes, you have a subset with I and then you know that parody and then you remove I and then you learn the par of the subset without I. That's almost all of the schemes. And sometimes when you remove I, you can set up your hints in a more complicated fashion so that you don't have to sometimes fail. >> You did something a bit different in Plinko though, right? >> Yeah. So, Plinko in particular builds on two different prior works. So I would say Plinko kind of as a paper shows how to improve two prior works to obtain

better algorithmic efficiency. >> So in both of these prior works, I don't think I should go into all of the details of of how they work. I'll tell you I'll try to focus in on what what Plinko is doing in that paper, but we can go into the details of the schemes if it if it's helpful later. But both of these prior works have some particular way that they construct their hints. And in particular, they they construct their subsets so that every single set has one element from each of what I'll call like chunks. So if you imagine your database is in elements, then I can chunk the database into square root in consecutive chunks. Right? So the first chunk is just indices 0 up to square<unk> n minus one

>> and then square<unk> n 2<unk> n minus one and so on. Right? So I just chunk the database and for each of these chunks I'm going to pick out a random offset of that chunk and then that's going to define my set. Okay? So I just pick like here's offset, here's an offset, here's an offset. And the way that we derive these offsets for efficiency, right? Because if the client stores the sets directly, the client storage is going to be way too big because each set takes like square root in bits to write down and if you store square root n of them that would take >> n bits and that's unacceptable, right?

We could have just basically downloaded the whole database and stored it locally. So instead what we use to derive these offsets and derive these random sets more generally is some sort of pseudo random function. So you can think of this as like a or shot 256 or your favorite pseudo random function. In this way we can basically just store one key per hint and then use that key to derive these offsets whenever we want to issue the query. And actually this also lets us more efficiently test whether or not a specific index I is in a set. Right?

So if you give me an index I, I know what chunk it belongs to. And so for each of these hints, all I have to do is run the PRF, the pseud random function for that particular chunk to figure out whether the offset lines up with the index i that I'm interested in. I don't care about any of the other indices in the database. It's either like the offset matches on this chunk or it doesn't. And so I can kind of just scan through by hint. That's how prior works did it. And what we observed in our paper is that this linear scan through the hints in order to test whether or not a specific index is in a hint comes

with some knock-on consequences. So backing up a little bit, one big drawback of client side pre-processing P is that you have to pre-process on the database at a particular point in time. And in practice, a lot of these databases are dynamic. They change all the time. This is definitely the case in like blockchain. you're doing append of course and in a lot of other contexts you have database updates and that causes all sorts of changes to the database but we've pre-processed on the database at like you know time t and once it goes to time t+1 it's actually just not clear at all whether your pre-processing is useful or not and so

this was something that hadn't really been explored in prior works except through like very generic and inefficient constructions so this linear scale and comes with a lot of knock-on inefficient things. And what we do in Plinko is we show that actually you don't have to do this linear scan. We can use a new primitive called an an invertible PRF in order to do this lookup much faster at least asmtoically. >> What did you just call it? An invertible PRF. >> Yeah, an invertible pseudo random function.

>> Oh yeah. Okay. >> So, so pseudo random functions let you go one way. Usually they just you take an input and then the output looks uniformly random. >> But if I give you a random output, >> can I find an input that matches to that output? And this sounds like a bad property, right? You don't want this for someone who doesn't know the key. But for someone who does know the key, this is an okay property to have. >> Cool. You just you mentioned the prior works and I I don't know is it your prior work or these what what are they which like I don't know if we want to reference them. The two that we improved directly on are piano >> uh >> which was a big breakthrough paper that kind of showed how to do multiple

queries kind of concretely efficiently and then another paper by Ling Ren Muggies and Sun >> which was a follow-up work that achieved I would say better concrete efficiency and also reduced the server response size compared to piano. to both of these and actually since then there are other schemes that use kind of a similar hint structure. This is a very very general hint structure that we can kind of speed up. It's not quite in a blackbox way but for anything that generates these hint offsets from PRFs. There's a decent chance that an invertible PRF could be used to speed it up algorithmically. You keep mentioning hints and I feel I feel

like earlier we talked about kind of the sending the subset minus the I but I don't know is that the hint or does hint means something else? >> So hint means the when I say hint yeah I should have clarified this earlier I'm referring to the set that you pre-processed together with its parexor of those entries. So that quantity together is one hint. And what the client does in pretty much all these schemes, you know, there's no reason it necessarily has to do this. It's just the way that it's worked up until now. The client stores a bunch of these hints. So square root in of these hints >> and whenever they want to issue an online query, they find a hint that is useful to them. I see.

>> So they basically scan through these sets until they find a good hint. So yeah, sorry. I I maybe I should just call them sets, but usually it's important that you have the set and the parody together and this is kind of like one object in the algorithm. >> And in the in the Plinko work, have you changed that approach or are you still doing are you still treating hints this way? >> We still treat hints this way. We have to change how we derive the offsets of the hint. So in fireworks every hint right you had the set and the way that you compressed the set was by using a pseudo random function key a pf key >> in plinko instead of having a pseudo random function key per hint we have to shift it and so we have a pseudo random

function key per chunk right so we have square of these chunks >> and so we have the same key that's shared across all of the hints this is kind of necessary in order to do a fast search over the hints. If each hint is independently like drawn with no shared key or anything, then there doesn't seem much hope to do a faster search over the whole set or the whole collection of hints. >> Yeah. Just to find even the hint that the index that you're interested in exists there, right? So that is like the problem that you're trying to solve because otherwise the client side does a lot of work to even find a relevant hint.

>> Exactly. This especially matters in settings where you want the client to store more in order to speed up the server's computation time. So there is an inherent trade-off in these schemes where the client they don't necessarily have to store square root in hints. Maybe they store like into the 2/3 hints. And if they do that then the server's query time and also its response will become like into the 1/3. So there's this trade-off where like the client can store more and the server will run faster or the client can store less and the server can return more. That that's a trade-off that >> uh previously you couldn't explore the whole trade-off there, but with Plinko you can actually pick any client storage size and obtain the matching like

runtime of the protocol. So one one way that you mentioned that you know we can solve the privacy problem that Anna mentioned with the hints was okay let's do a boards but I if I remember correctly the way that you do it in plinko and also I guess in piano uh before that is that instead of sending just that subset that you're interested in you're basically sending the entire set of indices you just don't tell the server which one you're interested in.

>> So, it's a little bit more nuanced than that. If I send the entire set of indices, then the server would know wi with I in it, >> the server would know that I'm interested in one of these square root in indices and that would also break privacy. So, what they do in piano and something similar is done in later works >> is you remove I. If we imagine these hints as like one per chunk, then we remove i. And so now we're missing some index from that chunk. And so what we do is we just replace that with a uniformly random index within the chunk.

>> So like we send basically the whole set except now we've just swapped out i for a new random value. And because of this, it comes with a downside is that the server can no longer just compute the exor on their side for piano. And that's because if the server did compute the exor of these entries, then you would get back the original set minus i but plus some random value. >> And so if you exor these parodies together, >> then you kind of lose the the benefit that you had.

>> Mhm. >> And so what piano does there actually a number of ways you can resolve this. The easiest one is you just have the server send back the database entries directly. Right? So the server sends back square root in database entries and the client will just compute the exor on their side locally without any problem. Right? So they just ignore the entry that they kind of randomly added. They exor these together and then they exor it onto their par bit and then they'll recover the information that they wanted. So I feel like we have sort of explored the hints, the subsets, but I think what we haven't really discussed is the

information, the eye. I'm curious like what is that? How big is it? And like when you're actually trying to get information, are you usually like doing multiple eyes or like I guess different? Like are you searching all at the same time for a bunch of things or are you always searching for one thing? >> It depends on the context unfortunately. So PI in general I mean it's a good thing and a bad thing. It's a very powerful primitive that has all sorts of applications and in some applications you might be searching for many I at once. So this is usually what's called a batch PIR or a batch query.

>> And there are general techniques you can do to convert any P into a batch P. And so in a batch P let's say I have like a thousand queries. Then what you can do actually generically is batch these thousand queries and instead of paying a thousand times the normal PI cost you can just pay like about the normal P cost maybe with like a factor two or three. So you can batch many things together without increasing the server computation by that same factor. uh and there's a line of work that kind of specializes in like trying to make batch P as efficient as possible and that might be useful in some context. In other contexts maybe

you only care about one particular query. So like one kind of fictitious example is like in a DNS lookup if I imagine that the like DNS server who like anytime I type in some URL it goes and pings this DNS server to figure out what IP corresponds to that server. I might want that to be implemented by a PI so that the DNS server doesn't learn, you know, which URLs I'm navigating to. >> And so in that one, it makes sense that like I might only care about a single query at a time unless you're doing pretty insane browsing.

>> I see. Okay. The batch P you just mentioned like some work on that. This is also useful for us because we can add these to the show notes if people are curious about that. Who's working on that? So my co-authors at Google have a paper from a couple of years ago called don't be dense that builds an efficient keyword PIR and I think that they also talk about generic batching. >> Okay, >> there are a couple other papers that I'm forgetting the names of that use something called probabilistic batch codes to build these batch PRs. There's another work by Ling Ren that does vectorized batch private information retrieval VBPIR

that comes to mind. Yeah, but like I said, this is a popular field. I I can't remember all of the papers off the top of my head, unfortunately. >> No worries. No worries. >> But people can look at those papers and the references there in and who cites them and that will give them good pointers. >> In the case of Plinko though, you're talking about a single eye, right? Is that like is the construction really it's not about bad chain, it's about a single one. How big is it? Like I say this almost because I I think in my head I'm thinking like you're you're going into a database. You're pulling out something. I realize it's not exactly that, but yeah. How how big could it be?

>> Are you asking how big the like index I is or how big the database entry is? Those are two different Oh, both. Okay. The I >> So it'll depend on how many entries you have in your database. >> Okay. Um it's actually a good question though because there are there's another dichotomy in pier as with almost any question you can ask there are people who explore variants of these different notions of P. So what we focus on in Plinko and what these client side pre-processing P to date that I'm aware of are what are called you can call them point PIR or array PI. So the index I is just like an array index. So the database you treat it like an array.

It's indexed from you know zero to n minus one or one to n and then the client just they're interested in some particular index i. So this is only like log in bit. So if we think of in for practical deployments might be making this up a little bit but like 2 to the 32 or something you can think of i is like a 32bit number. So it's not i itself is not very big. It's interesting if you could try to build P for bigger databases, but that's still kind of a research question to try to make the efficiency get to that level. But there is another variant of P called keyword P or keyword private information retrieval. So like I said, don't be

dense builds one of these keyword PS. And in this setting, you're you can think of it as a private dictionary retrieval, right? So you treat the database not as an array but as a dictionary that has values for specific keywords and maybe not for others, >> right? And I want to be able to look up the particular value that I want given a keyword from maybe an a very big universe, right? So here we don't really care like it could be gigantic and we don't have an entry for every single thing. So this might even be more analogous to something like the DNS application where I don't want to look at like google.com is not an index but I could look it up maybe as a keyword in a

dictionary that maps to the IP address that I want to connect to >> and you can still use all these techniques you described like with these exor and the subset and even for words. So there are general transformations from this point or array PIR to keyword P. >> Wow, >> I'll say that up front. The efficiency of these transformations may or may not match your, you know, intended use case. And I would say it's a I think it's actually an open question to build client side pre-processing specifically for >> keyword private information, private information retrieval. usual constructions can convert one into the other via something called cuckoo

hashing uh which is just particular way of storing keyword entries into what amounts to an array. And so then what the client has to do is they just hash the particular value that they're interested in. So if they have a keyword they just hash the keyword and then out of the hash or multiple hashes they get some indices and they query those indices using the point pir. >> Cool. And I guess if you're seeking a bigger eye, that's when you start looking into the batch PS, right? Like you're like if it's not just a word, it's like that word anytime or multiple account information. I don't know if you need that for some reason or like yeah interfacing with a like what interfaced with a contract and you want to actually

see a number of of individual information points. Yeah. Would you then use batch P or is batch P only for the array index type? So you can do batch P in either setting. So almost every you know like binary decision like this you can kind of choose your own adventure and end up with a different definition of P. So you can have batch keyword you can have batch point. Like I said there's this transformation which I think a lot of the batch keyword PS make use of. >> Yeah. And there are settings where like this batch might make more sense like yeah if you know that you need to issue a query to like these specific nodes or like let's say so one application in blockchain that I think I know and you

guys can correct me if if not because I'm not perfectly familiar with everything here is a private Merkel proof generation. So I don't store an entire Merkel tree but let's say I'm interacting with someone who stores an entire Merkel tree. But if I want to generate a Merkel proof for a Merkel tree, one thing that I have to do, I have to learn the like intermediate hash value at a bunch of these internal nodes. Or maybe not a bunch, but log the depth of the tree. I have to learn that many intermediate nodes. And if I have the location for the place that I'm trying to generate a Merkel proof of, then I already know what all of the like indices or like what all the locations I need to query are. And so this would be

an example of like where I just need a batch PIR and I could maybe be more efficient because I could query all like log in of these >> uh at once and that would be a little bit faster than querying each one individually especially if the depth of the tree was pretty big. >> Ah cool example. Yeah. And this and this is like a very relevant application because this is exactly what you need to generate identity proofs, private transfer proofs, like you need to know the path to the root to put it in your snark to show that you know what you're spending or what you're using as your identity. So I actually wanted to ask about the alternatives a bit in the sense that for example one of the

disadvantages of that style of client side prep-processing is that you have to go over all the database at least once and you have to keep track of it maybe before the disadvantage. So one advantage that I think it has is that the server doesn't have to store anything per client, right? Like the server stays the same for everyone. They don't need to know anything about a specific client or anything of that sort. So the alternatives to client side pre-processing we covered. So one of them is by introducing another server, right? So if you have some non-colision assumption, then you have an efficient PI. uh and that's kind of been solved

for over 10 years now. But another solution if you still want, you know, the same strong guarantees that P gives you would be what's called like server side pre-processing PI. And usually in this setting, the holy grail is what's called doubly efficient PI. and a doubly efficient P which I don't really like the name but what makes it doubly efficient is that it's a P where the online phase has sublinear communication and sublinear computation.

>> Mhm. >> Okay. And ideally you would just have all the pre-processing done on the server. So there's like one expensive server prep-processing phase that's done once and for all. It's not done per client. So that's a really big benefit of the server side pre-processing. And then the online phase like you can think of this offline phase as basically encoding the database to be in into some like pir friendly form right. So we have lower bounds for like what the server has to do. The server has to do like it has to do linear computation when the database is just encoded as it normally is. But if we re-encode the database in a friendly way there's some potential for some speed up.

>> Mhm. And this like general approach was introduced long time ago. But what was really notable is that Lynn Muks and Wixs in 2023 showed that you could actually build this doubly efficient pier theoretically from something called ring lwe which is a pretty standard assumption especially in postquantum crypto. And they showed that you can actually like do this one-time server prep-processing phase and then online your queries would be like would take poly log like logarithmic time in the size of the database. So this is like a crazy asmtoic speed up and it was a [clears throat] breakthrough result and very awesome.

>> It's also not practical. It's very far from practical. There have been, I think, two works that have tried to implement their scheme through like very aggressive optimization of the theoretical results and some of the data structures that they rely on. And I'm not familiar with the like concrete optimizations that they put in. But I know that the like server encoding size just blows up so much. Like even if you want like a gigabyte size database, you have to store I think like terabytes of information that may or may not be perfectly accurate, but it's far from practice especially compared to the other more traditional PS and even the client side PS. But that would be like

the holy grail and that's kind of what everyone hopes to achieve one day. And the in those constructions the theoretical ones that are not practical let's say what does the client have to do in terms of storage or in terms of offline work. >> So actually in their scheme the client doesn't have to store anything. It's a very I mean it's called unkeyed doubly efficient P. People have considered public key doubly efficient PR where the client would have to store some public key or it could just be posted somewhere that the client could uh maybe trustworth like like grab it every query. But yeah, the client has to doesn't have to store anything. All they have to do is generate their query just like in a normal P. They just have to know that the data the databases is encoded in a particular way and then the

server does some computation and sends it back to the client. It's actually a really asmtoically an amazing scheme that doesn't require the client to to store anything. >> Mhm. And what about like this concept of I think I've heard stateless P. Yeah, I think stateless P would refer to the traditional P setting, but I think I know it might depend on the context exactly. I'm not familiar with the technical term, but in the normal P setting, you don't think of the client as storing anything. The client has no like information that is, you know, related to the database at all.

>> Mhm. >> And they generate a query. The server processes the query and returns it back to the client. And so that is stateless in that sense. There are Ps for a while now that have considered pre-processing in a way that's not the client side pre-processing and it's not the doubly efficient PI. So these are schemes where the server is still going to perform linear computation. So the server is going to do all of that computation >> but you can get some concrete speed ups through some other form of pre-processing. So one scheme that does this is called like simple PIR and since there have been lots and lots of works that build on simple P where basically there's like a matrix multiplication

that can be done beforehand. It's something that is independent of the database and that you don't have to have the client do online. You can do it beforehand. And so in simple P you imagine like basically releasing this matrix A to the client as well as some particular like matrix multiplication. And this information can be stored by the client. And so this is stateful in the sense that the client has pre-processed something with the server and then you can run online queries faster. But it's different from the client side pre-processing setting because this pre-processing is basically done by the server once and given to all of these clients. And it's also independent of the actual database itself. Mhm.

>> Is there ever a situation where the database itself has privacy components? Like I'm just curious with the PS right now. I feel like we're we're only looking at the privacy side for the one who's making the request for information. Like I'm the client. I want to access something in that database and I want the server to know what I'm looking for. Or I shouldn't say database like data space like thing with information. But then what if you were dealing with something like a more private data pool and you as a user of that do have access to certain things but not everything and you still don't want them to know what you're seeing.

Would that over complicate things or is that something that's even explorable? Like the case in my mind would be something like the Zcash shielded environment and you have viewing keys and you want to do like a search on those viewing keys but you don't want the server to know that you're doing that search and maybe it already is all zk and it you don't see anything anyway but I'm just like say you have like multiple points of entry where you can get information you don't want your search your query to be tracked but the thing itself is partly private like are there any cases like that that you've encountered And would that affect how a P would work?

>> I can think of applications like the one you mentioned that have this like fine grained confidentiality requirement and this hasn't really been a focus in P literature that I'm aware of. And I think it's usually because you could solve this with other cryptography. So if you just imagine the database is encrypted with some sort of you know identity based encryption or some other like access pattern respecting encryption then the client who like wants to access some particular entry can just run a p over this and they're not going to be able to decrypt anything that they don't have the key for. So the client will like have their keys and these keys will will let them decrypt

some elements and not others and so they can just grab the entries that they're interested in and if they happen to learn other entries then they won't be able to decrypt it. >> H >> there is a notion of P I'll say also called symmetric private information retrieval where you do have confidentiality of the server. I don't think this would really fit the use case you're talking about. But here you have a client who wants to learn a particular database entry. All right. And so you have one side of privacy where you want the server not to learn which entry the client learned.

>> Yeah. >> But what makes it symmetric is that you now just want the client to only learn the entry that they queried and to learn nothing else about the database. >> Interesting. Yeah. Yeah. Yeah. >> So this is a type of like you can also think of this as like one out of in oblivious transfer for anyone who knows what oblivious transfer is. This is a basically an efficient form of oblivious transfer. >> I don't think it really maps on to what you're saying. And also there are kind of generic transformations from PI to symmetric P using other cryptography. So there's a very easy transformation using something called an oblivious PRF an oblivious pseudendant function and there are other tricks you can use as well.

So, I don't think that also like hasn't been studied as much because these like generic transformations exist. >> And also, apologies for the slightly clumsy description on my part. It's like it's it's like a halfbaked idea right here, but it just Yeah, I sort of wondered about the other direction and like or limiting what the client could actually access or something. >> Yeah, there might be open questions there. I just haven't thought about it significantly. Alex, one thing I've seen around me is a bit of confusion about the concepts of oblivious RAM and P and how they relate to each other. Uh, so I was wondering if you could touch on that a bit.

>> Yeah, this is a really easy thing to get tripped up on because they sound like very similar primitives and at some level they're doing a very similar thing. So, Oblivious RAM is a primitive that I've worked on that purports to protect access patterns. So it takes any RAM program that like accesses the random access memory. So it accesses an array at v various points and it can kind of compile it into an equivalent program where these accesses are what are called oblivious. Basically they don't reveal anything about which entries the program actually wants to access. Mhm. So this is a very related primitive to pir but it's critically different in a few ways and maybe the

main way is that in oblivious RAM there's only one client whereas in P you have many clients. So in oblivious RAM there's usually like a secret key that the client is holding and you usually also think of the array as entirely encrypted. The thing that oblivious RAM is attacking it are these access patterns. And it assumes kind of beforehand, it's not even in the security definition. It assumes that all of the data it doesn't reveal anything about the access pattern to the adversary sitting on the server. And so what the client can do is they set up their key both for encryption and for the OAM beforehand. And then that one client who has that one secret key can run some program using the secret key

and make their access pattern oblivious. And that's a lot different compared to the PI setting where in the most general form you have a database and it's public. Everyone knows it and any client is allowed to query it. There's no like secret that's being used by the client to like encrypt the database let's say. So, OAM is used in like this one particular like one client, one server setting. I should also add though that these two primitives can be used for very similar things. So, one application that's kind of illustrative of this is usually what's called private contact discovery. So, we can imagine that there's some database, a public database that's like a list of users maybe. So,

this is actually something that's come up in like the signal messaging application, let's say. And if I have like someone's phone number and I want to know if they use Signal, then I want to look up whether or not they're in this database. So, one thing that Signal wants to do though is they don't want to know who you're looking up, right? They're a privacyoriented company. And so, they would want you to be able to issue some query on this big database in a way that doesn't reveal to them which contact you're looking up. They don't want to get a map of who everyone's friends are because that's just something that they don't want to know. And so you could use private information retrieval for this.

But actually, interestingly, Signal, as far as I know, has chosen not to use PI. And they did that mostly because of efficiency constraints. So, at least as far as I'm aware now, and also when they wrote like a blog post about this a few years ago, private information retrieval just wasn't efficient enough for like the number of users they had and the size of the data. It just wasn't something practical that they could do. And so, what they opted for was using oblivious RAM plus secure enclave. So if you combine oblivious RAM with the secure enclave in certain applications, you can get something analogous to what you get with private information retrieval. So in their solution, as best I remember it, a client will communicate

with the secure enclave. The secure enclave will perform the lookup on behalf of the client using an oblivious RAM to access this database. And so when it uses this oblivious RAM, if no one has access to the interior of this secure enclave, they won't be able to learn who you're looking up the just the fact that you have looked someone up. >> Yeah. So like if someone let's say looked inside the program that's running in the enclave, they would have seen what's being accessed, but like you're assuming that you can only see kind of some pattern of queries that are being made and that's what you want to hide using oblivious round here.

>> Exactly. That's right. Yeah. I mean, if you're in the enclave, you would literally see the client sending you the phone number. >> Yeah. Okay, cool. That's awesome. >> So, what is the status of PI today? And maybe what work should we keep our eyes out for? >> I would say it's a very exciting time for PIR broadly. It's already been deployed by a bunch of big companies. I would say mostly for like niche applications like Apple uses it for a type of caller ID. Google uses it as a subprotocol of something they call private set membership. Basically like trying to check passwords like if you have a reused password, they don't want to reveal that password to Google. So it

has a lot of these kind of more niche applications that work because of the sizes of the database and the sizes of the entries there. And people have made P efficient enough that it actually does get deployed and it's really exciting. M >> unfortunately things have kind of only been getting better and P is such this fundamental like primitive that has all sorts of applications and so what's really exciting is that as it gets more efficient I think that the applications are just going to explode in terms of like what it can be used for and finding different models >> you're going to see it in lots of places then >> yeah it's just such a like low-level primitive that could be used in so many places but just isn't for efficiency reasons and so >> I think the thing to look out for is

just like big landmark like efficiency updates in terms of you know either pre-processing or even just in normal PI being able to do it faster through other means. >> Cool. Well, Alex, thank you so much for coming on the show and sharing with us P kind of going in depth letting us ask all these questions to sort of tease out what this is exactly and some of the techniques that you guys are exploring and yeah, thank you so much for explaining it to us. >> Thanks for having me. Yeah, I'm happy that we have a P expert on the show.

Like I said, I wanted to talk about it for a while, so it's very fun. >> And now we have an episode to point to when it comes up in the future, too. [laughter] >> True. >> Nice. All right. I want to say thank you to the podcast team, Henrik, Rachel, and Tanya, and to our listeners. Thanks for listening. >> [music]