A deep dive into PIR. Revisiting Spiral & Respire - by Prof. David J. Wu

Transcript

uh in the computer okay so just to give a very brief introduction um Professor David wol from the University of Texas uh came today to guide us a bit through his uh work or his several works on the P field uh kind to give us an introduction and a sense of all of the different or some of the different flavors of p and for what P can be useful so thank you very much David for for coming today and joining uh mainly just one thing before starting do you prefer to get like interrupted with questions or do you prefer to keep questions at the end please interrupt I'd be happy to discuss that during the

time itself so thank you very much the floor is yours all right great thanks a lot Carlos for the introduction and thanks for inviting me to to speak uh so I'm very happy to tell you about some of our recent work on private information retrieval or p uh and this is based on joint work with my students and collaborators Alex spon and Samir m so let me sort of set the stage for what the Primitive that we're interested in is uh so this talk will be about something called private information retrieval or P or Pier I'll sort of use these terms interchangeably uh throughout this talk but the setting is as follows it's a two-party protocol uh where we have a client and then we have a server and the server holds a database so the database contains let's say

records R1 up to RN and the client is interested in a particular record I uh and the goal of a P protocol is for the client to retrieve the I record from the database so at the end of the protocol the client learns the I record the Privacy requirement uh for p is the server or the database here should not letar anything about which record the client is interested in um so at the end of the protocol the server has no idea which query uh which record the client requested and so if this is the objective it's actually very easy to satisfy we can just have the client simply download the entire database so this is what we call a trivial P scheme

where the client simply downloads the database and now it knows uh all the records in particular record number I so I think it's important here to note that we do not require privacy for the database itself the database contents is usually assumed to be public uh the client is trying to privately retrieve a record from this public database if you want uh privacy also for the server's data then there are other protocols uh like oblivious transfer than ures that but that's outside the scope of this particular talk um so having Define the trivial uh P construction uh that's not very satisfying because for any for many practical applications where prer might be considered which I'll describe a little bit on the next slide it is

infeasible for the client to always download the entire database right the database could be several gigabytes terabytes La big uh and so it is unrealistic to expect that the client can just download everything so for pier to be interesting we also impose an efficiency requirement uh which essentially says that the communication should be sublinear in the size of the database and ideally the communication should even just be poly logarithmic in a number of record in the database so you can think about it as if the we did not require privacy then uh all the client would have to communicate to the server would be the index eye and it would just retrieve the record eye from the server and nothing more and essentially what we want in P is that we

want to do this in a privacy preserving manner but with similar kinds of efficiency uh from the client's perspective the client does not have to fetch many or download many bits of the database in order to reconstruct its record so Pi in recent years has become um sort of a Major Tool or major building block in a large number of ver of privacy preserving protocols uh so I've just listed a couple on this slide but there are many many more um so a couple um uh applications that might be a recent interest is Apple for instance has re released an SDK uh for supporting private information retrieval and homomorphic encryption uh primarily for

their application they're looking at uh doing some kind of private uh voice call uh caller ID uh type of application so it's like your phone is Rec received an incoming call uh you want to check whether this call caller is or this number is known to be spam or not uh so the idea there is that there will be some database of known spam calls uh spam numbers and basically the phone when it receives an incoming call will query the database to learn whether uh the incoming number is actually in this list of spam callers or not and of course you want to hide uh who is calling you that's a potentially very sensitive information so private information retrieval uh is used to

facilitate this kind of application there's also been proposals of using uh Pier to do things like certificate transparency auditing so if you want to um check whether a certificate that you receive uh is deposited in some in a in a certificate transparency log uh you want to do that without revealing let's say your browsing habits uh to the server one of the proposals for that is to use private information retrieval so this is a this is an application where we have some uh existing browsers so for instance Chrome has uh deployed some mechanisms uh to perform this kind of auditing uh with weaker types of uh anonymity guarantees so something called K anonymity one of

the proposals is that maybe using private information retrieval we can get much stronger cryptographic guarantees uh and anyhow the this is hopefully just gives you a snapshot of the kinds of applications that people have considered for private information retrieval and from my view is that one of the simplest building blocks or simplest uh privacy preser serving protocols so of often times if you have a particular application uh where you demand privacy for one or both parties private information retrieval can be something that fits in uh or plays a a role in enabling those kinds of guarantees okay so when we look at private information retrieval uh and this is going to be the focus of this talk there's a several ways that we're

going to measure efficiency or there are several quantities that we care about uh so as I mentioned uh this it's a client server protocol and I'm mostly going to be focused on two part uh two message protocols so the client sends a query to the server server sends back a response so what are the efficiency metrics that we care about well one is the size of the query right how many bits does the client have to upload in order to uh retrieve a record in a database so that's uh that's the first metrick the second is how fast can the server respond to the query and usually the way that I'm going to measure this in this talk will be bi aetric called the server throughput so in particular this is the ratio of the database size

divided by how much time it takes for the server to uh respond to the query uh and the reason that this is um this is a useful metric or a relevant metric is that in a model without pre-processing the server actually has to do a linear scan over every single record in a database in order to answer the query and the reason for this is because of the Privacy requirement right because if the server does not know know which query which record the client is interested in it basically has to look at every single record if there's one record in a database that the server does not look at well that means that the client could not have asked for that record and that immediately compromises privacy uh so this is why when we look at server throughput it's really the

time it takes to do a linear scan over the database size and the question is how long does it take to perform that linear scan I will preface here that there is some recent work that actually shows how to get around this uh this sort of linear scan barrier uh where with some pre-processing so there's some encoding of the datab base that the server develops ahead of time uh that is then used to reduce the online um computation time that there is a way to do that but uh for the purposes of this talk I'm only going to focus on constructions where uh little server has to do a linear scan and for the most part today all of the efficient constructions of private information retrieval that U

could potentially be deployed they all work in this particular model there are some exceptions which I'll mention at the very end of this talk but for the most part this is sort of the state-of-the-art in concretely efficient private information retrieval from a theoretical perspective we can do better uh but those the constructions from the theoretical world are not efficient uh actually to run in practice and next the metric uh the one of the more important metrics is something I'll call a rate which is the size of the response as a function uh sorry the ratio of the record size to the size of the response so this basically measures the communication overhead in the response so how many bits does the client have to download to get a particular record uh and

essentially we want the rate to be as close to one as possible right if the rate was one that means that if the client wants to get one bit of record then it only needs to download one bit of information now it could be the case that the client wants to retrieve one bit and it needs to download a million bits right it needs to download uh or even a megabyte or something like that then the rate would be much smaller so now would be like one over a million if it's downloading a million bits um so if we want a protocol to be high rate that means that the communication overhead is minimized and finally for the constructions that I'm going to be describing in this talk um I'm also going to allow the client to upload a

set of public parameters to the server so there's an initial communication of some public parameters this is a reusable set of public parameters that the server will use uh to process the query uh you can think about the public parameters as a public key so essentially at the beginning of the protocol the client generates a public key and sends it to the server and thereafter the same public key can be reused for many queries so the reason that we decouple the public parameter size from the query size is because uh the public parameters only have to be transmitted once so if the client is making many queries let's say one query every day uh it only has to send its public key once so like when it logs into the system it uh sends over the

public key and then thereafter the server can just look up the public key it does not have to be communicated with every single query okay so this is uh this is sort of the the metrics that I'm I primarily care about does the notion make sense are there any questions right now it doesn't seem so in the chat NE okay sounds good all right so let me say a little bit about what does the landscape of P look like so it turns out that over the last couple years there's been a lot of work uh on developing a faster and more efficient private information retrieval constructions uh and we made great strides into bringing private information retrieval to be uh more practical so here I have a graph

sort of showing the the different tradeoffs uh in designing single server peer protocols and basically I'm plotting communication versus computation these are the two main metrics that I described so for communication here I'm basically uh defining it to be the sum of the query size plus the response size so how many bits have to be uploaded SL downloaded to perform a query and then the throughput is basically how fast can a server process uh the database or process a query and for comparison purposes I'm focusing on the case of retrieving a 256 by record from a database with a million records and I'll show more benchmarks for other settings later on but this is one particular case uh that may be of interest this is

actually a very small database if you think about it it's 256 megabytes uh but I think it's uh still a relevant one to sort of show uh the different tradeoffs uh for the different constructions uh so basically constructions you want constructions towards the top of the graph and towards the right of the graph so to the right of the graph that means server server throughput is very high and communication is very low uh towards the bottom of this graph that means we have have high uh High communication and low throughput so that's a negative so you want things to be uh in uh uh towards the upper right corner of this graph um so so first we have a bunch of schemes where that's into sort of this client pre-processing model where the

client has to upload a public key before performing a query and then thereafter uh the server responds the nice thing about this model is that we can actually get very small communication so if you look at it we have some earlier schemes so cop and fast P so this is roughly pre 2018 or so so this is maybe uh five or six years old and then we have much more recent constructions like onion pier spal and respire uh that get uh much lower communication so for instance for Spire if you want to recover retrieve a 256 byte record the communication is something like four or five kilobytes so or maybe 6 kilobytes so it's not that much bigger than uh the record you're interested in uh versus for previous

constructions uh maybe there's more overhead so something like hundred a few hundred kilobytes that we made great strides in reducing the communication cost uh for private information retrieval the throughput tends to be still on the lowed side so something like processing a database at 200 to 300 megabytes per second uh for a single processor so for large databases uh this is still going to struggle uh but there's been other other works uh recently uh that's try to make made improvements in the on the throughput angle uh so for instance the simple P protocol is this extremely fast P protocol it basically process the database at roughly 10 gigabytes per second this is essentially the memory bandwidth of the system so the F the speed at which the server can respond to

a client query is basically the same as the speed it takes to read the database from Main memory and this is sort of a bottleneck uh for any P protocol if you're doing a linear scan right because you have to do a linear scan over the entire database so the speed at which you can read in main memory will ultimately become a bonck for the system simple P basically achieves uh that memory throughput uh uh limit for single server Pier so this is very nice and the communication is actually not so bad it's only about 100 kilobytes of communication uh to retrieve a record from the database the drawback of simple kyir is that it's in a slightly different model where instead of the client uploading a public key it actually has to download a hint from the database first before it can process the

queries and in practice this hint actually turns out to be very large so so the hint can be something like hundreds of kilo sorry hundreds of megabytes uh for a reasonably sized database uh so potentially if you're using simple P you'll need a way to download this you have to make a large communication up front and moreover you'll need to store this hint if you want to make repeated queries so this can in introduce additional burdens on the client side but in terms of throughput and in terms of online communication this is a very lightweight very uh simple protocol uh and very useful for many applications uh right so so natural question then is well what if I don't want this hit right I don't want this initial High download

is there anything that we can do and so there's actually a more recent line of work uh so hindess pi and my own work with the Samir on white Pier which basically shows how to remove the hint uh from a simple Pier like system at a modest overhead so the nice thing about these two constructions here these two very recent constructions from uh uh from uh late 2024 so this is maybe 6 months old at this point uh these constructions are no there are no public parameters and there's no hints this is what we call a Silent Communication or silent setup model where it's basically a P protocol is exactly a two shot protocol client shows up sends the query gets back a response no setup whatsoever so no hint upload no downloading a hint

right so this is a very appealing especially from a practical perspective there's no authentication or anything needed just send the query get the response who two shock protocol um and in terms of the throughput it's not as fast as simple P but uh I will preface here that as the database gets bigger the performance basically gets to Ser gets to um memory bandwidth so uh there's some fixed costs of the protocol so for a small database like 256 megabytes we can only process let's say 2 gigabytes per second with yier uh but if your databas is let's say 16 GB or 32 GB already Y is about 95% of the throughput of simple so why the scw put y here actually approaches the

memory bandwidth of the system because the fixed cost for the the overhead uh does not depend on the database size so there's a fixed cost that you pay uh that does not scale with the size of the database so as database size gets bigger the cost of the linear scan actually becomes the dominant factor and so you basically approach the memory bandwidth limit uh and in terms of uh communication it's going to be something like about 3 megabytes of communication uh for this particular case so again modestly higher than simple P but has high throughput and doesn't require any of these uh hits so this is roughly what the state of the art is uh as you can see there's not really a one-size fitall solution right there's no point like on the upper right corner of the graph here

uh you know we have points that are towards up towards the upper half of the graph but they're on the left half of the throughput side versus we have things in sort of this quadrant here which is high throughput but High communication so uh currently we don't have anything uh that's sort of has high throughput and low communication and that's a fascinating open question and something that we are still thinking about here but uh that's sort of where what the trade-off looks like uh for modern P protocols yeah so one question I have well two questions ined so the first one is um what about schemes like Newton p uh which uh also show some let's say good tradeoffs in in performance results

like are not noted here because like it would be like like just too many dots at the end if you put them all or you you didn't this particular construction I guess uh do you know what it's based on I think it directly uh goes against simple PR if I recall correctly but I uh I can I can say off the top of my head now I think it builds on the top of simple p and oh yeah I don't know I I I could lie so don't quote me on that my understanding is that sort of the uh the extreme ends of this uh of this graph so for in terms of throughput and communication are basically reflective of the current

stateof the art so I'm not aware of any protocol that's faster than simple K maybe you can get a little bit more communication out of it but uh I think uh not by a significant margin so I think as my as far as my understanding is as of let's say two or three months ago uh the schemes I'm represented here are represent the current current State ofthe art uh in single server Pier yeah so there are many constructions that I'm not listed here uh and usually I I did not list them because uh they are not competitive uh or they don't dominate the schemes that already shown in the graph yeah okay that makes sense and the the second question that I had is um mostly regarding the online

communication cost that most most of these protocols incur um it's I mean it's it's not a communication overhead that uh seems like prohibitively expensive uh let's say uh especially if it's a fixed cost independently of the size of the thing that you are quing right so uh do you think is like it has that much relevance at this point the the online communication that the protocols incur on if we are already at like let's say kilobytes uh because kilobytes I mean of course it takes some seconds to the load kilobytes but it's a size that it's acceptable enough I would say if you want to pay on that for

privacy or for extra privacy it's not like prohibitively expensive so what's your take on that I think it depends on the application so for instance for if you're let's say doing uh certificate transparency auditing and you're doing that on a per connection basis or you're doing that uh very often then the communication can add up right is imagine that if every TLS connection you're going to make a p query that's probably not uh you know tens of kilobytes for every single TLS connection you make that's a lot that dat up very quickly uh now granted if you're doing certificate transparency auditing you're probably not going to be auditing every single TLS connection you make you're probably going to be batching these queries at the end of a week or at the end of a session uh in

which case maybe you're only making a small number of queries uh uh periodically in that case uh a modest communication overhead like tens of kilobytes Mega even a couple megabytes is actually very reasonable so I think it really depends on the application uh what kind of frequency are the clients actually going to make queries and what kind of bandwidth uh is available uh to sort of service those queries uh so yeah I absolutely agree that for that once we're in the regime of tens of kilobytes hundreds of kilobytes we can actually process these queries uh pretty regularly so the communication overhead uh it does not become super significant I will say that as the database size gets bigger as the size of the records vary uh you know the the parameters will

start changing so there will be some dependence on the on the size of the database uh so again it really comes down to the application what do you say is the maximum communication that you're willing to tolerate per uh for let's say a single query and then depending on that uh that bound different constructions might have different uh advantages and disadvantages so I think again it really depends on any kinds of application you're looking at uh uh what makes the most sense but uh for many applications I think the communication is already good enough um there is theat you know you do need these public parameters and public parameters are not on the order of kilobytes right now so they're on the order of megabytes to hundreds of megabytes so uh those are those are more substantial uh but if

they can be cashed or stored then that could be less of a concern good point Thank You yep okay cool so what I'll try to tell you today is I'll give you a flavor for some of how some of these communication efficient uh P protocols work so I'll Focus mostly on spiral and then the resp spiral protocol is sort of an improvement on top of spiral uh for a particular parameter regie uh so to give you a sense uh for how these PR protocols operate uh I'm going to describe the basic blueprint by Kush owski of constructing private information retrieval from a homomorphic encryption scheme so the idea here is um I'm going to take my database and I'm going to start by arranging it as a

square right so let's say n is the number of Records in a database I'm going to rearrange it as a as a square that's square root n by square root n okay so I've just put my database into a square and suppose I'm interested in one particular record in this database I'm interested in record uh in row three column two so the way the protocol works is as follows I'm going to start by encrypting an indicator Vector indicating which row my record lives in uh and in this particular case my record lives in row three so I'm going to encrypt a one for my in row three and I'm going to encrypt a zero in all of the other rows so I want to indicate which row I'm interested in and I'm just going to encrypt an indicator Vector accordingly and essentially what a

homomorphic encryption allows you to do is it allows you to perform computation on the cipher text themselves so for instance given an encryption of one and an encryption of two I can take those two encryptions and I can actually hold orphic add them together to get an encryption of the result so in this case 1 plus 2 so I would get an encryption of three uh so here what I'm going to do is I'm going to take the encryption of my uh query and I'm just going to multiply it by each component in uh uh in this uh in my database so basically I'm going to take zero I'm going to multiply by each of the records so again that will give me zero I'm going to take the second row I'll multiply each record by zero take

the third row each record gets multiply by one take the fourth row each record gets multiplied by zero so the the server doesn't have any idea what's Happening Here Right the server only sees the cipher text but it can perform these homomorphic computations and notice that if I perform this computation where I take the first row multiply by the first Cipher text second row multiply by the second cipher text third row multiply by the third Cipher text and so on and then add them together because there's only a one in one particular row what I end up with is exactly the row of the database I'm interested in so I get the a row of the database and then I send it back to the client the client decrypts uh and learns the element that they're interested in they learn some other elements but we

don't care okay so this is the basic blueprint goes all the way back to 97 uh and this is the blueprint that has been very successful in constructing private information retrieval using a homeomorphic encryption scheme and so here uh because the database is actually available in a clear we only need additive homomorphism so we actually don't need things like fully homomorphic encryption so uh okay so once we do this we send back the response Cent decrypts so notice that the total Communication in this protocol is an encrypted query which has size that scales with the square root of the database size Yeah question I I think someone was unmuted

or something I see I see okay yeah I have I have one indeed uh could you elaborate a bit more on why FH is not needed in this case uh maybe give a a bit more context so you said the database is open in the clear let's say therefore fom morphic encryption is not needed uh that's that's assuming basically that the the database that the user wants to query uh doesn't have any private information that the owner of the database doesn't want to link yes yes yes okay that's right that's right yep yep so and in fact uh if you want to hide the content of the database using fully home morphic encryption does not help you uh just because then you have to ask under whose key is the database encrypted under uh

and it has to be encrypted under the client's key in order for it to be meaningful but then it's not clear how the database gets encrypted under the client's key right so so yeah so so so this is why additive homomorphic encryption is sufficient for this because we're assuming that the database is all in a clear so only the query is encrypted so you just need to be able to add uh and and multiply Cypher text by scalers okay good and then the response is just a single row of the database this has size that's grows uh with the square root of the database size so the question then is okay well square root is great but what do we want to do better right can we have better communication can we further reduce

communication and in practice square root uh square root is often times very good already like for a million records like a megabyte the uh the square root of that is something on the order of kilobytes uh but if uh if the database is let's say 100 gbt then the square root of that is 10 gbt which is still uh a prohibitively large uh amount of uh communication so can we do better than square root uh and the answer is yes now what we're going to do is instead of viewing the database as a grid right as a as a root n by root n Matrix instead I'm going to view the database as a hyper cube right it's going to have many many dimensions uh so here I drew a three dimens dimensional uh figure and

essentially what you can think about it is what are these query vectors doing well this query Vector here is selecting along one of the dimensions of my grid right it's selecting for which Row the database lives in so if I have a hyper Cube you can think about it as okay what is my query going to do it's going to select along the First Dimension so in the case of a three-dimensional Cube it basically tells me which slice of the cube am I looking at so here it says I'm looking at slice number three of the cube so I do the same thing I did I did before uh and I basically project using my query onto the third layer of the cube and now notice that we have a new database right it's a database now it's a grid and what do I want to do I want

to retrieve an element within this particular grid so I can repeat the same protocol we had before I can send you an encryption uh which Row the database which row my record is uh within this Cube and then that will project it all to a single row and then I can say Okay within this particular row my and my record lives in the First Column and so now I get a projection again I do I do multiplication and suddenly I only end up with a record I'm interested in so just by doing this uh we can actually achieve communication that's cube root of n with with a cube and more generally poly logarithmic in N if we have a log n uh layer so we have a hyper cube of

Dimension log n now we can actually just project project project and extract the element we're interested in the caveat here is that we do now need homomorphic encryption and the reason or fully homomorphic encryption the reason being that once I do my first layer processing I take my database which is in the clear but after I process it I now have an encrypted database right the server doesn't know which where the element lives and I want to project again but now this setting is different I have a database that happens to be encrypted so in order to the next layer of projection sort of this uh this uh inner product like operation now I need homomorphic multiplication I need a multiply Cipher text together that this

is where fully homomorphic encryption uh comes into play okay good so uh so this is the basic blueprint this was known in '97 and in fact you can actually already just take your favorite fully holomorphic encryption scheme and use it to implement this protocol turns out that the performance is actually really really bad if if you just do that because fully homomorphic encryption is very expensive so uh the server cost will be uh too big uh if you just do the naive uh construction so the the technique that we use in spiral uh and sort of many subsequent Works in this family uh it does use fully homomorphic encryption but it does so in a very particular way

that gets us better concrete efficiency and the key idea here is we're actually going to compose two different fully homomorphic encryption students so it's going to follow a paradigm first introduced by Gentry and hevi of uh building uh what's called compressible uh or high rate fully homomorphic encryption so let me let me give a little bit of background on how these schemes look like so we're going to be using Lattis Bas cryptography so luses is basically Lattis Bas cryptography is the is the only mechanism essentially that we have of realizing fully homomorphic encryption uh so that's what we're going to be using the cryptographic building block in our scheme uh and what I'll give a little

bit more background on what these things look like but the way that you can think about it is the cipher text in the Lattis Bas scheme they're basically noisy encodings of the message and as you do homomorphic operations the noise in the cipher text increases and if you have more noise you need to have larger parameters to tolerate it because if the noise becomes too big you cannot decrypt anymore right if the noise is bigger than a signal then all you have is no and that's not useful so as you perform homomorphic operations on encrypted data the noise accumulates the parameters get larger you get less efficiency so most of the work in trying to use homomorphic encryption to do something useful is really a question about noise management how can we uh make sure that the noise

doesn't grow too big too quickly but other if it does then we're out of luck right then we have to pay with a very high performance overhead so what we're going to do uh and the construction of spirals we're going to consider two different homomorphic encryption schemes with two very different types of properties so the first is reg encryption scheme uh this was actually goes all the way back to regas original work introducing the learning with errors problem and regas encryption scheme has a very nice property in that the cipher texts are small so for instance uh if I want to encrypt let's say 18 kilobytes of message I need a cipher text that's only like 43 kiloby so only 2.4 times bigger than the size of the message and as the message gets bigger this actually gets

better right if I want to include one megabyte my cyer text has only 1.3 megabytes long right uh so this is nice if if you're trying to build a P protocol that wants to support large records right suppose a record is at least 18 kilobytes or 1 Megabyte and encryption of the record is only not much bigger than the record itself so that's good so it's good for communication it's compact unfortunately though reg's encryption scheme does not support full homomorphic encryp fully homomorphic encryption it does not support homomorphic multiplication the only thing it can do is homomorphic addition so it seems like if we use reg encryption scheme we would be stuck with this Square Root construction we wouldn't be able to uh uh get better than square root n communication so we

cannot do multiplication uh that's the drawback the second scheme I'm going to look talk about is the gentri of high waters encryption scheme so the GSW encryption scheme this is a fully homomorphic encryption scheme so it's a very uh sophisticated Construction has a lot of capabilities and so it supports homomorphic multiplication and moreover the amount of noise that's introduced in a homomorphic multiplication scales additively with the number of multiplications right so most homomorphic encryption the amount of noise that's accumulated scales exponentially with the depth of the computation here it only scales multiplicatively every time I I multiply I get an additive amount of noise added

to my Cypher text not a multiplicative amount so this has very good noise growth the way that it achieves this though is it has gigantic Cipher texts you have to have very big Cipher text in order to support homomorphic multiplication and have very good noise growth so just to give you a sense for how bad it is if I want to encrypt one bit of data I need a I need a I need a cipher text that's almost 20 times larger or sorry two million times larger right this is it goes from one bit to 2.5 megabytes uh so this is a extremely large cyer X expansion and you can imagine if I have to encrypt a uh database using the GSW encryption scheme that's a million x overhead so a

gigabyte becomes a th000 terabytes right this is uh this is something that's uh not going to be practical but it has very good homomorphic multiplication so the question is okay yeah sorry David one question uh in here is there any particular reason why people avoid um using other FH schemes like I don't know dfh whatever anything uh and basically they do bootstrapping to reduce the noise not good uh at least for for the ti application if you just use off the-shelf FH schemes let's say you just using TF to implement things it be signicantly significantly

slower uh qu like query wise or encryption of the data wise uh so uh so the encryption of the database will be much slower and processing will be much slower okay so well okay I see yeah yeah I think I would guess that the overhead would be at least a THX oh wow okay okay I didn't thought it was that bad okay thank you right right right so in fact a lot of works that have tried to use fully homomorphic encryption um they basically don't even don't try to use homomorphic multiplication at all they actually use other mechanisms to avoid using homomorphic multiplication just because the overhead is so high um so because there there have been some improvements on U bootstrapping efficiency meaning

some some for example are um going back to circuit bootstrapping and basically try to enable a parallelization of all of them there's also amortization of bootstrapping where you pay for one but you execute all of them the constants are massive of course but there's maybe some hopes uh do you think if the situation gets better then it would make sense to go for this uh morphing multiplication and it still will not be the case I don't think think so I think for p because the type of computation is so much simpler than uh General computation you actually don't need very sophisticated homomorphic multiplication there are actually always going to be better lce techniques uh that do better so homomorphic encryption uh the reason

that it's slower is because it's more General it can do a lot more than the kinds of things that we're going to need for p so the P application I view it as we want to do homeomorphic encryption for a very very simple uh computation basically comp linear functions almost uh Computing inner product Matrix Vector products and for this if you uh try to design a tailored scheme you can actually do much much better uh so that's sort of what all of the the recent line of Works have done uh to actually make p practical as scale uh using tailored homomorphic encryption schemes can give you significant improvements in terms of concrete efficiency thank you yeah uh so the main question in spiral is uh can we get the

best of both worlds so we have these two schemes one that's fully homomorphic one that's only additively homomorphic but has small cyer text can we do both uh and that's exactly how what the underlying design principle on for spal is we're basically going to use the GSW this uh this nice homomorphic encryption scheme to perform homomorphic multiplication but we never want to communicate GSW Cipher text because they're so big so we're going to use reg encryption scheme for all of the communication so let me just give you a sense for what that looks like uh so I'll start by talking about reg's encryption scheme so in reg's encryption scheme uh I have a message I have a secret key and I have the cipher text and the invariant that you should

think about is If I multiply the secret key by the cipher text the the secret key is a vector Cipher text is a vector I multiply them together I get the message yeah uh and technically everything is working over pooms but that detail will not be relevant for this talk uh so essentially if you have the secret key and you have the cipher text you get a noisy version of the original message right uh you just multiply them together you get the message uh and to support decryption uh basically we just scale up this message so we have to somehow get rid of the noise so all we do is we just scale up the message by a large constant and we say that as long as the noise that's added is much smaller than a scaling factor or sort of

the size of each region then we will be able to decrypt so we have recovered a noisy version and then we round to the nearest multiple of the scaling factor and that's it okay um so if you think about this uh uh type of encryption scheme the rate where so how big is the cipher text relative to how big the plain text is uh this is basically uh saying that the pl text is a log P bits so it's a it's an element of zp so integer mod P and the cyppher text is two elements mod q and Q is usually something like uh twice the size of p in terms of the number of bits uh so you can get something like uh the overhead where expansion factor is something like a quarter so the UNM scheme in fact uses

this uh this exact encoding scheme and basically the cipher Tex expansion is a factor of four okay turns out that you can actually do better uh instead of encrypting one bit at a time you can actually encrypt an entire Matrix at a time and the reason that this is better is because you can actually reuse the randomness that you're using to encrypt each component of the Matrix this actually does not compromise security and so this actually reduces the size of the cyer text uh so essentially instead of having a rate b 1 / 2 * log p over log Q now it becomes n^2 over n^2 + n I'm encrypting n^2 things but my cyer text only needs n^2 + n uh number of things so the N the factor of extra

factor of n here this is just uh the randomness that's used to encrypt so in particular uh if you use if you encrypt matrices out of pine you can pack more information into a single Cipher text with less overhead so this will be this will be useful the second observation is that this is additively homomorphic and this follows just by looking at the at the decoding invariant right so again the cipher text is an encryption of M If I multiply by the secret key I basically get M right s * C gives me the message so if I have two Cipher texts let's say C1 and C2 that encrypts M1 and M2 that means If I multiply them by S I get by the secret I get the corresponding Matrix so you can observe that if you

just add these two relations together you get that C1 plus C2 is an encoding of M1 plus M2 so uh so regs gives you additive homomorphism for free okay so the second encryption scheme that I mentioned is this encryption scheme of gentry Sahan Waters or GSW uh this is actually the same encryption scheme that's at the base of tfh so tfh is actually based on the GSW incription schemee uh and in uh in GSW basically what happens is I now have a very redundant encoding of the message right so the invariant that I'm going to use is the following C here is the cipher text S here is a secret key If I multiply the secret key by the cipher

text before I just get the message in GSW I don't just get the message I get the message times something I get the message times the secret key times the gadget Matrix what is the gadget Matrix is his powers of two thing so basically it is the powers of two along a diagonal okay so this is the gadget Matrix uh the construction will use more General versions of this but again I won't get into the details okay and the way that you can oh and the reason that we care about this gadget Matrix is uh it has this nice binary decomposition like property where if I have a vector v if I take it binary decomposition and I multiply by the gadget I get back V again so there a way to take a dense vector and make it short

so that that's the only property you'll need uh for this talk okay and uh as you can probably see from the picture the size of the cipher text is significantly larger than the size of the message right the message here is a single bit mu is a single bit and S and G are these gigantic matrices now right uh and if you want concrete parameters uh basically to encrypt a single bit you need a cipher text whose size is D so that's the that's the that's the size of each of these elements * n +1 2 that's the size of the uh and sorry n+1 s * log Q that's the number of entries within uh the cipher text Matrix right so concretely you plug in these parameters you get something

that's pretty abysmal like the cipher text are very big uh and the reason for that is because the cipher text you can view it as a very uh uh redundant in coding of the message that turns out to have very nice properties so the nice property that we will using so this is the key algebraic step in this talk uh is this very nice uh homomorphism between regf and GSW and this was introduced in the context of tfh so this is actually one of the we one of the major Innovations in the TF scheme is how do you do this sort of compos this multiplication between regf and GSW this turns out to have very nice properties and the idea is actually quite simple if I have a reg of Cipher

text I multiply by the secret key I get the message if I have a GS W Cipher text I multiply by the secret key and I get the message but I multiply by the secret key multiply by the gadget Matrix so what you can do is the following suppose I take my GSW Cipher text and I multiply by G inverse times the regf cipher text so G inverse makes this uh makes this regular cyhex into a binary thing and now notice what happens I take s times this GSW cyer text by the GSW invariant that just mu * s * G right so I get * s * G * G inverse of the reg of Cipher text G * G inverse just cancels out so I get S * reg of Cipher text but what is

stimes reg Cipher text that's reg decryption that just gives you the message back so notice that what we are able to do by taking a GSW Cipher text and multiplying it by the regular Cipher text and actually get an encryption of mu * m okay so now I've gone from a GSW Cipher text and a regf cipher text back to a regf cipher text that en Cod the product of the two inputs so we have basically done a homomorphic multiplication between a reg of encryption and a GSW encryption okay uh with the noise terms uh this this is what the relation looks like this is actually not so important I just want to show that for correctness uh all we need uh is just multiply these

together and you get uh you get homomorphic multiplication okay all right good so just to summarize we have on the left we have the regev encoding on the right we have this GSW encoding and another way that you can think about the GSW encoding is I said that s * C Is mu * s * G if you actually write out what that looks like it basically looks something like this you have one block of Cipher text and then you have mu * I 2 * mu * I and so on and so forth so it's a very redundant encoding of the message me the Mew is encoded many many times in uh in the cipher text uh and the key property that we're using is that if you have a reg encoding of the message M and A GSW encoding of the scaler me you can get

mu okay so what does the Gentry Hy blueprint look like now how are we going to use this to build private information retrieval so the database recall is represented by hyper Cube so I'm going to say the first dimension of the hyper cube is two to the new one and then all of the sub subsequent Dimensions have Dimension two okay so that's just the configuration of my hyper Cube the way the query looks like what the query looks like is it's going to consist of many reg of Cipher Tex basically encoding the indicator Vector so encoding which bit I'm looking for along the First Dimension so this is exactly the same thing I presented earlier with the grid right I have an indicator Vector that shows which row I care about here I'm just saying which which uh which slice of the hyper Cube am I

interested in so that takes care of the First Dimension and for the subsequent Dimensions I'm just basically they're their binary Dimensions right so there's only two elements in within each uh uh each uh each slot I'm just I'm going to have a GSW Cypher text that indicates which index I'm looking at in those subsequent dimensions and that's it uh this is the this is the this is the construction uh and the point is that um I guess that doesn't matter uh the point is that the response will just be a single Matrix regf Cipher text right so I encrypt using regf the queries along the First Dimension and then I'm going to do a homomorphic multiplication with each of these GSW cyer texts and notice that the homomorphic multiplication has

the property that it produces a reg Cipher text so at the end of the day I get a reg encryption that's good because reg encryptions are compact right they're small okay so what does the overall protocol now look like uh I take the I take my database I use my reg encryption of the indicator Vector along on the First Dimension to basically project onto the First Dimension right so now I get a regab encoding of the database slice and now I just use the GSW encodings to select for the subsequent components so here I'm selecting for the for the first for the for this row oops and then I'm selecting for this column right uh and at the end I get a single

reg Cipher text and that's it okay so that's the overall protocol makes sense so it's using homomorphic multiplication but the multiplication is done by using regf multiplied by GSW okay it does make sense at excellent uh good so at this point uh you might say this qu there's something looks fishy about this picture it looks like you're communicating GSW Cipher text and I just spent a lot of time telling you that GSW Cipher text are humongous right so doesn't that mean the queries are humongous uh turns out the answer is yes uh in fact each of these single bits encrypting a single bit is 4 megabytes uh for the concrete parameters we look

at so this is going to be a gigantic Cipher text and in fact uh if you plug in all the parameters the overall query size for the original Gentry heli construction is something like 30 megabytes uh which is in the case of the size of the DAT relative to the size of the database might be like 10% of the database size but this is a gigantic query in a gr scheme of things I also note that there's a clever technique using polinomial encodings by Angel that shows how to compress many regab encodings so I'm not going to go into details of how that works basically you can actually compress uh the regive encryptions but GSW 1es we don't have a mechanism yet okay and if we compare against sort of Prior P constructions based on just

regf style encryption there the queries were much smaller something like 66 kilobytes because they only needed to communicate regf Cipher text they did not need GSW so it seems like using GSW is great because you can do homomorphic multiplication but the cyer Texs are so big that uh you don't gain anything in the process so the key idea underlined that finally how am I doing on time I think uh I might be running we're 8 minutes away from like the formal time but I mean it doesn't I don't think it matters like it it's much more important that you can explain everything like okay sounds good so I'll just keep going but yeah if I'm running short on

time and you want to stop just let me know and I can no worries no worries that's not the case no worries about okay great okay good so what we do in spiral is we're going to expand we're going to sort of show how to compress these very large GW Cipher texts we're going to compress them using reg EV codings uh and I should note that this was also done in a prior work uh uh by muis at in the onion P construction they consider this case for the spiral H sorry for the scaler case and in spiral we give a more General toolkit uh for switching between regab and GSW uh and it turns out that the Transformations that we develop are both useful for query compression and for response packing so I'm not going to go into the

full algebraic details I just want to give you a picture of sort of what's Happening under the hood inside spiral so our goal is to somehow build a GSW Cipher text right so GSW Cipher text is one with the following property if I take the cipher text and I multiply by the secret I get basically the secret times this gadget times the message right so what let's take a look at what my goal is I'm trying to build mu * s * G what does that look like that looks like a c0 and Then followed by many redundant encodings of the message so basically the message me scaled by the powers of two where does the pow of two come from is basically this gadget term here and what I want to do is I want to

construct a cipher text C such that when you multiply C by the secret key you get this picture here okay so that that's my goal so let's just first write down s * c yeah s * C will look something like this s * a and then s * B and so on so the first observation is that if you look at what's going on with these blue and purple blocks it's saying that I want to find a b0 such that when I multiply by the secret I get the message me I want to find the Matrix B1 such that when I multiply by the secret I get two times the message four times the message and so on if you look at this picture this looks like reg of encryption right it's a matrix that when multiplied by the secret key gives me

the message right so you can think about the GSW Cipher text as you have a header that's c0 and then a bunch of reg of encryptions of the powers of two multipli by the message this is an equivalent way of thinking about GSW okay so that's that's one thing the second thing is we need that this s * a here to equal c0 I'm not going to go into details of how this works but this uses somewhat standard key switching techniques uh from homomorphic encryption so there's a a way to construct a matrix a such that s * a is actually the first block of the GSW Matrix this requires this is basically a key switching mechanism but we can do it so what this picture is showing is that essentially I don't need

all this F Cipher text what I can do is I can just have many reg encryptions of each of these smaller uh blocks components but so far it doesn't seem like we bought we got anything because we have a lot of different regab encryptions so it's like if I give you each of these components that's no better than just giving you the GSW Cipher text so the second idea then is the following let's take our query the query has these regf Cipher texts and these GSW Cipher texts the regf cipher text I said we can pack using the um uh the already is small right so we don't do anything fancy here and the GSW Cypher text basically it's just taking a message multiply by many powers of two

right so what I do is I can just have a bunch of reg of Cipher texts that basically encode the powers of two times the message right and then from these reg of Cipher text I can sort of recompose them together or sort of combine them together to actually get my GSW encoding okay so suppose I can do that so so far it doesn't seem like we made any progress right we we have a lot we still have a large number of Cipher texts sure we Tak in the GSW Cipher text and broken it up into different pieces but there's a lot of different pieces right so we don't have any compression yet so the second step is that uh well the progress that we made is we went from these Cipher text into exclusively regf Cipher text and I showed you or I claimed before that if I have many regf

Cipher texts we can actually pack them into a single regf Cipher text so this is the technique by Angel atel and in and further improved by chenel where basically they show that um if I'm encrypting many different scalers so here I'm just encrypting many Z1 values or one times powers of two I can actually pack many different scalers into the coefficients of a polom and then just encrypt the entire polom at once right so instead of encrypting one bit or one scaler at a time I can now encrypt a vector of bits at a time and that's exactly what we do here so we can pack all of these things together into a single Cipher text so now we started with something very big we have something much smaller now and we can also use similar

techniques to actually reduce the response size so the same kinds of homomorphism and compression uh we can actually use uh multiple ways okay so to sort of summarize now the overall spiral protocol operates as follows uh we have the public parameters the public parameters are uh basically the public key so it's the public key used for homomorphic evaluation uh these key switching matrices these cyppher text expansion and translation matrices all of these are basically key switching matrices from uh the homomorphic encryption World these are the public parameters for the scheme the query consists of a single M RAV encryption so I just send you a rega cipher text uh to the server and what the server is going

to do is it's going to use the aformentioned homomorphic expansion procedure that I just described to actually produce these large queries right these regga Cipher texts these GSW Cipher texts and then I just use the protocol I described before I do the I project a the First Dimension then I use the GSW to sort of select aot the subsequent dimensions and then uh now I have a final reg of Cipher text we can use sort of the same sort of the the inverse process of the expansion to compress into a single short Cipher text and this gives us uh a communication efficient construction uh so just to give you a sense for whether this works in practice or not uh here I'm comparing against

some earlier schemes so this is so spiral is about 2 years old now so I'm only looking at schemes from over 2 years ago now so these are older constructions I'll talk more about newer constructions at the very end of this talk uh so here I'm looking at at a configuration where we have 8 GB database so each record is something like 30 kilobytes and there's about a quarter million uh Records in the database um so sort of compared to the previous state-ofthe-art we get improvements in both the communication and the comp computation simultaneously so we almost double the uh the throughput uh and we reduce the query sides and response sides by over a factor of two uh the drawback or the limitation of spiral where we pay is the

public parameters are larger because we have larger key switching uh components but again this is a one-time setup cost right like if you have an application where you're making many queries over a period of time you generate your public key once and then uh that's good enough uh for all future use okay so I'm not I'm currently not comparing against some of the later constructions like froto Pier simple Pier piano and so forth I'll mention those at the very end of this talk um one quick question uh also in that regard so um obviously I mean there's um the communication overhead is definitely much smaller uh yet still you need to let's say uh send some stuff uh could you benefit from the fact of not

needing uh TLS or basically any kind of uh encryption Through the Wire anymore meaning your queries are already encryp let's say so it's it's not that you really care I mean you can get in other regards but as for leaking private information let's say about your query you don't need TLS uh for that sure sure that's a good point yeah so we don't rely on TLS for any privacy guarantee anymore I think though that because the overhead of TLS is so small I don't think that makes in the bottom line yeah but for the protocol we don't need to assume a secure Channel anymore all the are yep that's a good okay and if you want to sort of get

a sense for the scaling here we have a throughput um uh for for um different database sizes so uh as a function of the number of the size of the database in terms of the number of records and how long it takes for the server to to respond to a particular query uh so you can see that the spiral protocol so the one shown in blue here we can get something like 300 megabytes per second uh on a single thread single core processing so again if you have multiple cores all of these things are very parallelizable it's just really just doing a linear scan over the database you can get much faster performance that way I'll mention a few optimizations that might be relevant uh so this is for the large record setting I'll talk about the small record setting in a little bit

as well so the large record setting is often times what I call a streaming setting uh where the same query is used to retrieve a very large record in the database or used to uh used to retrieve records from multiple databases so the same query used on multiple databases this is a setting that's suitable for things like a private video stream where the I copy of the database contains the I block of the media content so imagine you're trying to do a private Netflix right you want to stream a movie without revealing which movie you're interested in so you your query will be your the movie index and then you would basically just be reading it over the duration of the of the movie it's also useful for things like private communication so private voice calls uh so if you want to

do a voice voice call uh using p basically the database would uh be the The Voice stream and you would just be repeatedly pulling the same mailbox to get the latest content so this is the setting where I where here is used in a streaming fashion to retrieve data and then often times the goal here is to minimize the online costs of the protocol and the nice thing here is that uh any fixed cost like public parameters or large queries they can be advertised over the lifetime of the stream so imagine that uh I'm trying to retrieve a 2 GB record so let's say a movie from a database uh that can happen over a period of time and uh the initial query and the large public parameters those

will essentially be a small part of the overall cost of actually downloading the record itself right so uh in this setting we can have some different optimizations uh so for instance uh we we can remove some of these uh these compression uh techniques this allows us to get uh smaller noise growth in in the underly homomorphic encryption and get better performance so uh for instance here we can drop some of our query compression techniques Al together and just send a big query in a clear sure the query is 30 megabytes but if you're downloading 2 gab of media the initial 30 G megabytes of communication may not be such a big problem anymore so we now we really care about throughput uh and it turns out that once you do this you

indeed can get much higher throughput so the purple lines here basically show the version of spiral uh for the streaming setting where we don't do query compression anymore we just send a big query over uh and then we just have the server respond notice that the throughput can be something like uh 4X to uh 6X higher so we can guess throughput on the order of uh uh like I think 1.5 gigabytes per second to something like 2 gigabytes uh per second right so uh we Peak at something like 1.9 gabes per second this is is over 12x faster than any previous P construction uh so again it shows that using these lightweight holomorphic operations is

regf and GSW is great for throughput is on a server s uh you com at the cost of communication but if you don't care so much about this compression or compressing uh the upload now suddenly you can get a much better performance um one question may didn't regards of that um so do do you think how can I frame this um so let's say I I basically um do like I'm I'm doing this query right uh are we assuming that the server is using all threats and basically all its

computational resources in order to give me this throughput meaning can a single server serve content for and people at the same time uh without it affecting significantly the throughput do you see what I'm yes so this is actually something that we investigate in the context of white here so we developed This Not So currently everything I'm describing is single client and then a server is using a single thread to process the query so certainly you can use multiple threads that will give you a modest Improvement uh to the throughput there's a limit to how fast you can go because ultimately it'll be bottlenecked by how fast you can read main memory so that will be the ultimate bottleneck

uh so with multiple shads that doesn't help you there uh but yeah but then the question is what have what I what if I have a thousand clients all coming at once making queries do I have to do a linear scan for all 10,000 of these clients one after the other that would be very burdensome for the for the server uh so one of the things we do in wi here is we actually do this something called cross- client batching uh so the idea here is that I have a batch of clients all independent so they're not communicating they're not coordinating they all send their queries at once and basically what we show is that the server can actually use a single linear scan over to the database to actually process all of the queries at once so you don't have to do like if you have K

clients you don't have to do K independent linear scans you can sort of advertise the cost of the linear scans and process all K queries up once so uh so that's a way that you can get effective uh much higher effective uh throughput so basically the the let's say the amorti throughput can actually be higher than the memory bandwidth of the system because taking a single linear scan and using it to respond to four or 10 or 100 queries at once so yes this is something that we can do and I think for practical purposes this is essential uh because often times a server will be servicing many different queries simultaneously and we don't want to have to basically pay the full cost of a linear scan for every single one of those queries so yes we can do it uh and

different constructions will have different trade-offs uh for that but generally speaking in white here we show that this optimization applies for most of the existing PR sches out there so you can you can do this kind of thing makes sense thank you yep okay good so sogg just to give you a sense uh for the fastest version of this spiral it gets a throughput of something like 2 gigabytes per second the rate is actually very good so 08 so this means that uh the inverse of this is 1.25 so you only pay a 1.25x in increase in communication right so if I want to fetch 1 gigabyte of data uh I only have to download 1.25 GB bites of uh of information so uh the the overhead in terms of communication over direct

retrieval is actually quite small so that's a one appealing aspect of this construction but of course we pay for it with very large public parameters and very large queries so this is really only meaningful in a streaming setting where you're really downloading large payloads uh from the server for small records you never want to do this but for large records this is very very interesting uh right and in fact if you if you model AWS compute costs as a uh as one metric for how expensive something is the cost of privately streaming at 2 gigabyte dat movie from a database with something like uh what is two to the 14 it's something like 16,000 movies this is roughly only about 2x more expensive than directly downloading

from AWS now this is a little bit misleading because you would never use AWS to actually serve a movie uh but uh if you do that the cost of this protocol in AWS Compu and communication cost is only a factor of two over the no privacy Baseline of course if you serve a movie over a CDN where the cost of communication is much lower uh I don't then there will be a bigger Gap but I don't have the numbers for how expensive it is to to serve a movie over a CBN so this just give you some perspective on how this translates to monetary uh costs okay good so so I'm mostly done describing spal so basically it's a it develops new techniques to translate between these schemes and they give

a new way to explore communication computation tradeoffs and single server p uh and the techniques that we I described here sort of this translation between regev and GSW this is used for both query compression and response compression in our final protocol uh we also have some automatic parameter selection which I think is is very useful in a setting of any kind of Lattis based system so with ltis based cryptography there's always a lot of parameters that you have to pick and the parameters basically dictate the overall performance of the construction uh with spiral we actually have a systematic way of going about this where you just tell me the size of the database so number of record size of each record and it automatically figures out what lce parameters to use uh to basically

optimize it for your uh for your requirements uh and uh just to summarize these are the sort of the base versions and the streaming versions of spiral relative to to Prior work so in the time I have left which maybe another 10 minutes or so uh I'm going to tell you a little bit about how handle small records so this is a more recent Improvement on spiral called the respire system uh so before spiral I said was optimized for the very big records that's the streaming setting it was okay for these for moderate size records like tens of kilobytes uh but what did the records are very small what if I want to retrieve let's say a 256 byte record so maybe like a DNS record if you want to do like private DNS usually those records are on the order

of a few hundred bytes uh maybe you're trying to retrieve a shot 256 hat then it might only be 32 bytes uh so these are applications uh so let's retrieving a hash value is useful for both the certificate transparency auditing is also useful for doing things like password breach monitoring so if there's a password dump and you want to see if your password happens to be in this list of compromised passwords usually you'll be looking up a hash of the password so these are settings where the where the entries in the database are actually very very small uh and so the previous constructions where you are uploading like hundreds of megabytes of information for a single query or for a small number of queries they don't really make good sense uh anymore so the respire protocol is a way to offers or

optimize things so let's first uh take a look at uh at spiral so if uh this is the original example that I described so with spiral if you have a database with let's say a million records each 256 bytes the size of the query and the size of the response are already on the order of kilobytes uh and both the query and the response are significantly larger than the size of the record right so in absolute terms this is not too bad but uh if you're making these queries often like let's say for private DNS these queries might be happening quite often you don't want to be paying these tens of kilobytes on every on every query right so the question is can we do better uh and the reason that things are big is that lat Cipher Texs are big right that's the whole that's always has

been the issue with l space cryptography things are just big right the parameters are large and you it's very hard to get things to be compact right Lattis space signatures are much bigger than let's say ecdsa signatures again because lce parameters are big and so the question is okay what can we do right there seems to be a fundamental limit uh and in fact if we look closer it seems even more fundamental because if we look at the query it's a regf cipher text right it's an lwe Cipher text and an L single lwe Cipher text is large right so if you just look at the parameters you know the dimension of this Vector is 24 8 the modulus is 56 bits or 7 bytes if I just give a single Cipher text that's already

14 kiloby and it seems a little bit farfetched that you have an encryption scheme you're using an encryption scheme to build a p scheme and yet you don't even communicate a single Cipher text right like a single Cipher text should be the lower Bound in a communication like you can't do better than communicating a single Cipher text because less than one Cipher text is zero cyer text and you can't do anything with zero Cipher text so it's like as soon as I communicate one Cipher text I'm already doing right I already incur 14 kilobytes of communication so the question is okay so what do we do can we get small communication when the records are small so it's also the case with the response size right the response is a cipher text I need something to be secure right the server should have learn what it is so it seems

like both the sides of the query and the both sides of the response the lower bound that we use a Lattis based construction is 14 kiloby of query 14 kiloby of response I need to communicate a single CER Tex and if that's the metric then spiral is actually pretty good it's uh pretty close to to the Limit already right this indeed the spiral the query and the response each consist of a single Cypher test so the somewhat surprising aspect is in our work on respire is that we actually break both of these barriers uh so the query size is only 4 kilobytes response size is 2 kilobytes uh for this particular setting and the throughput is the same so we don't pay on throughput but we get a substantial reduction in the in both the cipher text size and the response size and the question that you

should ask then is okay this is a this is a lce based construction and I'm telling you that I have a construction where I'm not even communicating a single Cipher text anymore so what what in the world is going on here okay so we get fairly substantial reductions so the observation comes back to the query compression technique so let's look at spiral query compression I basically have take all of this this gigantic query and going to squish it down into the single reg EV encoding that's what I do and if we think about it what is this reg encoding well it's basically a representation of some Vector right what is the vector is some kind of polom so here I've I've shown the example suppose the polinomial was 1

plus X Plus X Cub I basically take the coefficients and stick it into the coefficients of the polinomial so constant term linear term cubic term right and let's say the degree of the polinomial sort of the dimension of the vector is eight so when a database records are very small and when a database is relatively small the observation we have is that most of the coefficients in this polom are actually zero right I actually don't need to put pack that much data into the polom itself like this D here I don't get control over this D is set by the security parameter this is always 248 or or bigger so that means that I always have I can always encrypt 2,000 things but if I only care about five things I'm using 2,000 slots to encrypt a very small number of values so there's a lot

of waste so can we exploit that somehow uh and that's exactly what we do in the respire protocol so in respire there's two parameters of Interest there's D which is the ring Dimension this is the dimension of the vector that I'm encrypting and then there's H which is how many elements do I actually care about right if H is much much smaller than D we can actually get savings and the idea is as follows let's say h equal 4 and D equals 8 so I only care about four things but I have to encode everything using a vector of Dimension eight because that's what the security that's what the scheme gives me what I can do is I can just encode the part I care about and I basically just going to truncate the cipher Tex polinomial right

the cipher text polinomial will have eight components in it if I encrypt anything whether it has zeros or ones doesn't matter the cipher Tex is agnostic to that it has to be right it can't leak information about the message but what I'm going to do is I'm just going to truncate it I'm going to not give you the full components of the cipher text and now this could be a problem for correctness it's like I'm only giving you half the Cipher text can you still operate on it so it turns out that the answer is yes there's actually some robustness in how the cipher text encoding Works uh where we can actually develop an efficient decoding procedure that takes a truncated Cipher text and expands it into a full Cipher text that has zeros in all of the subsequent components I won't have time to go into

the details of how this is done uh but if you look at the algebraic structure of the rega encryption scheme you actually get this kind of property that if you TR TR de Cipher text basically what that does is it replaces the truncated pieces with garbage right so the parts that I'm not looking at because I don't give them to you uh basically that's as if I communicated random values in those slots and it turns out that there's a there's an algorithm that we can use to actually zero out all the slots that we don't use so we just have that server do the zeroing out and then we are back to where we started so yeah and the way we do that is we use these homomorphic automorphisms so these galwa autom isms that modern FH schemes all support okay so that's how we compress

the query right we just truncate drop everything that we don't care about and have the server sort of fill in the gaps as it does the computation so what about the responses right so here again normally in a response we would have to communicate a full Cipher text but what if the response is much much smaller than a single lwe Cipher text right if the response is let's say if I have 248 components in my in my in my Cipher text but let's say the response only needs two components do I have to communicate the entire Cipher text and the answer again is no uh and uh basically if the record is much smaller we can use a

another algebraic transformation this is something called ring switching that was actually very old came from the first early days of FHA which basically says that if I have a cipher text defined over a large space I can translate that into a cipher text over a small space a cipher text namely over a sub ring and that's basically what we do the caveat that wants we project into the sub ring we cannot do many homomorphic operations anymore right so you can ask why not just use a small ring to begin with we cannot do enough homomorphism in order to do enough homomorphism we need to work over the big ring but the point is that once we are done doing a computation once we don't care about doing more computation we can sort of compress we can project down into the smaller ring and that's what we do here

uh so this is the way to get response compression and if you combine these two pieces together you can actually get a construction where both the query size and a response size are both actually much smaller than a single Cipher text you can actually compress both okay so when one question so by by basically applying ring switching what you're basically saying is um my new ratio in a cyer Tex of useful information and potential error it it already starts at like 50/50 or or 4951 let's say like the minimal such that you can now recover but if you do one extra operation everything is noise and there's no going back that's exactly yep y

y where I cannot do any more operations so but I'm done at this point I already have the answer so I just need to compress that's okay thank you distilling the LA Cipher text into only the part that contains the the part I care about okay good so just to summarize I want to say a little bit about some of the more recent developments in also inp so this is mostly not my work but I just want to give you a sense for what's going on in the field so I mentioned at the very beginning the simple P protocol where the client downloads a large hint at the beginning so the simple p and its extension double p uh has a property that is very high throughput basically the server processes the database at basically the speed at which it can read

the database into memory uh this is very good for databases with very small records because the rate is very poor so uh for every single bit of the database you might have to download a few hundred kilobytes um so if you have a very large record this is going to add up very quickly but if you have very small records this is actually extremely fast and extremely uh uh uh extremely simple um so it's a very nice protocol uh the one of the drawbacks it has it has a very large hint so a hint for a reasonable siiz database might be something like hundreds of megabytes few hundred megabytes that you have to download this is also a little bit uh tricky if uh the dat is constantly updating so for applications like certificate transparency when a database is constantly updating it means that

every time the database updates you need to download an updated hint the updated hint can be very large as well so uh there's a lot of Maintenance uh involved uh in this particular type of construction do do hints sorry David do do hints have any kind of like incremental property meaning you can profit from previous SK to already let's sayable so if I only touch a few I only change a few rows of the database then only a few bits of the hint has she has to change okay yeah only issue is that for applications like certificate transparency usually what happens is uh I have a bloom filter so the database is actually a bloom filter of all of the issued certificates there's like every

time a small even though I only add a small number of things to it many rows of the database actually changes and then you end up having the download the hint all every time no sense depending on the application it may be the maintenance could be more difficult than otherwise but yeah for some applications if this database is mostly static or has only local changes then this is perfectly reasonable right so a question then is can we get rid of the hint so this was a re this was a recent line of work from last year so by some folks at Google the hint lless pier and then my work with the Samir on white Pier uh we basically show how to remove the hint from simple Pier again using sort of the same kind of Machinery that I described in this

talk using homomorphic encryption and composition we can get comparable throughput so essentially memory bandwidth throughput uh at the cost of slightly more communication so we don't have the hint anymore so that's as a result each of the individual queries are slightly larger uh not by too much maybe a few hundred kilobytes but uh slightly larger but no hint whatsoever this is very well suited for a uh Dynamic databases there's no maintenance involved uh here uh and then there's also this another line of work by piano so this is by elain shei and her students uh where they actually explore this fascinating domain where the throughput on the server is actually can be very high and this is uh very

important if we want to scale to databases that are significantly larger so right now all of the schemes I described in this talk and all of the schemes described up here the server has to do a linear scan over the entire database uh so a linear scan will become too expensive if let's say uh the database is 100 GB let's say you can read memory at a rate of 10 gabes per second it's going to take 10 seconds to just read the database so uh for the when a database is big enough uh existing constructions are not going to cut it anymore we really need something that has a sublinear server computational cost so piano is an example of such a construction it has a sublinear server computational cost uh so in fact the server cost is roughly square root of the database size so this

is amazing uh from a throughput perspective it does have a very uh the Li liting Factor though uh is that uh it also needs a pre-processing step and unfortunately the pre-processing step is extremely costly it requires the client to basically download the entire database once you don't have the client doesn't have to store the database so this is almost like the trivial P construction where you're downloading the database once you don't have to store it but you do have to be able to download it so sort of it's um the parameter regimes where this is very interesting is the case of large databases but then the fact that you have to download 100 GB of database case uh makes it very difficult to deploy from that perspective but I think it offers a very interesting new point in

this trade-off curve that I can trade off offline communication for online throughput so I think it's very interesting to explore this uh further as well there's I have one question in regards of that which is um we've been also considering the fact of um performing like bucketing in order to have a search that is not linear of course that in into issues with privacy because you are like you are leaking which buckets you need to go and so if you do that then you're you can kind of track things somehow let's say you are revealing a lot more than you were previously right uh so how does this play with things like Oram for

example uh where it can maybe serve as this uh I don't know uh alternative to the linear scan maybe it's not the state of the is not good enough but know yeah so the tricky part with Oram is that it's single client single server usually so it's not clear how to actually use Oram to support a lot of these applications just because for Oram you need per client State uh and basically the client and the server had to have a lot of shared state in order for Oram protocol to work so every single client that joins the system uh will need to have different state on the server and essentially you need like a different replica of the database sort of of this Oram data structure for every single client so at scale it's not clear to me that uh uh that Oram would uh would be

effective just because there's so much per client storage that you need uh with versus with P you know you just need one copy of the database you don't need to preprocess the database differently for every single client so that's uh that's sort of the main difference between the two now of course or you very nice uh other properties it gives you stronger privacy guarantees uh and it can also do some of these things in a sublinear manner but I don't think it's a protocol that uh that works with let's say millions of clients all quering a single server so do you foresee any uh any let's say technology alternative that allows skipping the linear scan which of course currently no uh at the right now

I think you know schemes like piano and sort of the the follow-ups are the are the best concretely efficient uh mechanisms that skip the linear scan uh but there are some very interesting theoretical work s this notion of doubly efficient P where there is no pre-processing whatsoever it's a silent setup just like hlis here and white uh where the server does a one-time encoding of the database and then it answers all of the queries in sub linear time so this I think is an amazing development in a sense that uh it gets around this uh the the server computational cost is much smaller uh this is uh this is quite amazing the communication is very small uh the only problem is right now is that this is a purely theoretical construction but the fact that we have a theoretical

construction shows that this is a feasible notion right and you know we don't have a practical way of realizing it today but the hope is that maybe five years 10 years down the road we can actually see this uh working as scale uh so right now we're very far from that but the fact that something like this is even feasible and that we can do it actually gives us hope that uh this linear linear scam barrier is actually not uh so significant that potentially there are ways around it now certainly today we don't have good ways of getting around it but uh you know for upcoming in the future I think uh there is a potential that something like this could be doable makes sense thank you yeah so so just to sort of wrap up there's a lot of other directions that people have been

exploring for p they're looking at handling batch queries supporting keyword quer search uh doing some kind of authentication so there's a lot of other ways that we can augment basic private information retrieval protocols to have stronger and better efficiency and security requirements uh and these could be useful for different applications uh so I think this a very exciting time to work in uh P there's a lot of very recent developments the field is constantly evolving and we made Extreme uh uh we made a lot of great strides and bringing this stuff closer to practice we're starting to see deployments of this so I think there's a lot of interesting opportunities uh to explore uh in this space uh so with that I'll conclude I basically told you about

the spiral and respire which is one sort of data Point uh and there very crowded space now uh this is basically the approach if we want to take to get a very communication efficient constructions I didn't have a chance to tell you about how to get the high throughput constructions uh but hopefully this still gives you a sense for uh uh for know one particular Paradigm uh for realizing private information retrieval so thanks and I'm happy to take any further questions now thank you very much David that was really nice I think Janis had a question or yes uh thank you David for the for your presentation you was super compiling I do have a question around like the security assumption and the Privacy Assumption of the scheme like one thing

one intuition that I have is that as soon as I send like my encrypted bit vector and I we do the the scalar multiplication to select the layer that we need to like the in that I have I I'm not an expert in Hardware I know I know very few of it but just my intuition is that like um there is like there might be like some side Channel attacks like because I guess that the CPU is doing less work when it's multiplying by zero than one I don't know no so because it's multiplying by cyer texts uh you actually can't tell whether it's an encryption of zero or encryption of one so they actually look the same so if you look at the amount of work that the CPU does it actually does not depend on a query okay and that's that's the linear

property of the yes exactly exactly so because I touch every element in the database and the amount of work I do for each element is exactly the same you actually don't learn any information okay nice thank you thank you thank you very much and also I do have a question about like the setup of the database how how is it proceed like how what's what's like let's say that I'm I want to set up my encrypted database is there any like specific setup about like processing yeah there's some pre-processing so uh so you do want to encode the database uh using these latest based encoding schemes uh beforehand but it's sort of a one-time cost so it's like once I tell you the database so I have a list of records and together with the index uh

basically you do a pre-processing operation on each of the individual records okay nice thank you I have another question um so today's 29 so yesterday there was a new paper uh called distribution distributional private information retrieval from the MIT people and this kind of seems to maybe bridged into like I don't know if it has it's directly I haven't read it but is it directly related to not needing this uh linear scan directly based linear scan uh because they're building off of

simple P so I'm not sure they get around the linear scam but I think they they make other they have other optimizations that actually allow you to uh further increase improve the throughput and reduce the communication so I don't know the full details yet but uh it's a it's sort of a very varant of simple p uh for for settings where um you you sort of relax the correctness requirement so I think uh what happens there is that for most queries for the most common queries is guarantee is very close to being correct for sort of rarer queries there may be some small probability of error and Bas because you allow for this small probability of error you can actually get away with uh with much better uh

performance yeah when I saw it it I thought it fitted pretty well with uh one uh demo that your your coauthor built uh which was Private Wikipedia Artic right I was going to show the demo but I think inde I think that's the case which is in Wikipedia there's pages that a lot of people look for and there's others that probably no one takes a look in a lot of time so maybe a scheme like that could could be like a way to enable people to try try to see the lucky let's say and they can get this query privately and otherwise they they go back and relay on the normal let's say right exactly exactly yeah so I think

something like that could be could be quite interesting like really showcase uh uh showcase this type of uh this type of system right but yeah I think I think a lot of these constructions are at the point where they are efficient enough to handle you know reasonable workloads not every workload possible but uh for many for many simple applications I think the performance that we currently have both in terms of compute and terms of communication are actually at a level where uh they can actually give uh privacy preserving Solutions uh to some of these uh these challenges that are out there today thank you thank you very much David I think there are no more questions I will just send you in the

chat the paper of Newton P okay sure yeah I'm happy to take a look and I can follow up about it offline and I will post