ZK Paris: Samir Menon - Homomorphic Encryption for Retrieval of Witness Data

Transcript

okay so up next we have homomorphic encryption for retrieval of witness data by Samir Menon at Bliss okay can you go back good morning everyone um I'm Samir Menon and um today I'll be giving a talk about using homomorphic encryption to privately retrieve data so um I want to anticipate the first objection to the talk which is um you know this is CK Paris and it does not say zero knowledge in the title of the talk it doesn't even have a z so what am I doing here um

I'm I want to think like I'm an emissary from a different branch of cryptography and I think that um homorific encryption sometimes makes sense in a lot of contexts that you're using zero knowledge and so um I'll ground like what we're doing today or what I'm explaining in an example from a lot of common zero knowledge applications um so this is one this is one where where many people in this room are probably very familiar with which is uh proving set membership in zero knowledge so imagine that you want to prove uh that you're a member of some set without revealing your identity um we know there's a lot of fancy ways to do this um you can use polynomial commitments

you can use a Merkle tree but uh the the reason we want to do this is um it comes up often in in multiple contexts so it's not just it it is a useful primitive in a lot of things such as uh you know proving that you should get a batch if you have a certain number of assets uh proving that you have like a receipt for a cross stream bridge to kind of get your funds on the other side and even in voting right to prove that you're a member of the set of people that's allowed to vote so um I'm gonna I'm gonna prove I'm gonna we're gonna work through an example of proving set membership in zero knowledge that the super old uh dum-dum way oh I guess the lines are

missing um but you can probably imagine the Merkle tree here so um we're not using polynomial commitments or anything uh but uh yeah so let's say we're trying to prove uh that uh you know we have membership in some set committed to by R just really verbosely like the statement we're trying to prove in in this example um is basically you know I have some secret X um it corresponds to some kind of public version of X so I I've chosen like a key pair so um I have some secret key X and uh this corresponds to some public key why and basically my proof is going to consist of the statement I know uh uh I know values that hash to the root are so R is

some public value and I'm trying to prove in zero knowledge zero knowledge over x y and p I'm trying to prove that um you know uh I know some X and and the key is like I don't want to reveal you know which X I am so you know which Leaf node I'm proving membership for so to produce this proof as a client I need X Y R and P so that's you know the private key the public key the root and these this P this Merkel proof which is like a set the set of sibling nodes on the path from my leaf to the root um and the the thing is you know Gathering these for the client before

they can compute the proof locally is kind of a process right so so um in many applications like the client already knows X and Y so like for voting you know I know my private key and I also know my public key and um R is kind of public value that is safe to retrieve basically so so it doesn't reveal anything about my secret but um there's a complication for p so so I need to get these nodes in the Merkle treat that correspond that are basically siblings along the path up to the root but the problem is uh you know these sibling notes are uh if if I just kind of uh naively fetch them I will reveal which path I'm actually about to do a proof for

that's kind of a little bad you know so let's let's think about like what are our options here so so yeah so firstly if we just kind of if I'm on a light client right and I uh just you know send my RPC get storage at calls um to my full node that's that's serving me you know they're gonna immediately be able to tell uh which path I'm constructing a proof for and that kind of uh defeats some of the purpose of of trying to do the whole thing in zero knowledge um there are some other options so so another thing we could think about doing is using like Tor or a VPN so we could try to hide our Network identity like our IP address but that basically kind of doesn't obscure the association of

the fetch so if you know log n uh get story Jack calls all come in at the same time uh it's pretty clear that I'm like uh proving for some Merkle path and it's clear actually which path so if later you know immediately you publish a transaction uh to the chain that does something I can probably infer you know which identity kind of uh put forth the transaction um so so IP address obfuscation is kind of imperfect and then um this is actually the solution at least in my experience most people are still doing today which is another option is to download the entire tree so if you just download the whole Merkle tree then nobody knows what path you're you're trying to get but of course like

this doesn't work as soon as the tree is Big so if the tree is getting really large like if it has let's say a billion entries um it's not going to work to just download the entire one it's going to be gigabytes right so so um what are your options here um in this uh and uh I'll caveat here like sticking with this idea that we're doing set membership proofs with Merkel Merkle trees um what are our options so what we want is to get the Merkle proof the Merkle proof is the path up to the root of sibling nodes we want to get this proof without revealing which path we're getting the proof for so um there's actually a well-known problem in

cryptography this actually like predates uh even homomorphic encryption called private information retrieval it's a kind of simple problem to state but maybe hard to solve so the the problem is basically you have a database with n items the client wants to get an item at a specific index and the server should not learn you know which item the client gets and the naive solution to PIR is always to just download the entire database and the the premise of of par as a cryptographic problem is okay can you do better than downloading the entire database and we actually can do better or we can do a lot better we can actually do optimally like we can upload login data and we can download constant data

so we have solutions for par and just to see exactly what I mean by like PIR would solve this basically what we'd be doing is PIR at every level of the tree so um at the you know bottom Leaf node uh level we want to fetch exactly one node of these four and so the the uh the we want the sibling node of our of our Target node the orange one there and then we would do that for every level so we need to do you know log n par queries um so the title of the talk had homomorphic encryption in it I still haven't gotten to it so so where does homomorphic encryption come in uh basically the idea is uh to actually do

par to instantiate it to have the server somehow be able to give you this information without learning which item you're taking um we need this other cryptography called homomorphic encryption um this is not a long enough talk to just explain all of homomorphic encryption so I won't try but basically homorific encryption is a kind of encryption that uh lets untrusted parties uh compute unencrypted data so the idea is like at a very high level you can add and multiply ciphertext and the ciphertext that are after you add them will encode the addition or multiplication of the plain text um homorphic encryption has been around for a while

um like seminal work kind of outlined it about I guess 15 years ago um but it has a like a pretty bad reputation uh the the generic slowdown that you get when you try to run a computation in he is still like a million um it's actually something I've always been jealous of ZK for because things have gotten a lot better for ZK and at least verification is very fast it's not like that for homomorphic encryption we still have like very large slowdowns there's some good news which is for a very specific kind of circuit like a very specific kind of computation you want to do on encrypted data we can do much better than than a million basically we can we can do a lot a lot better and the

specific application is if we do this par thing using homorphic encryption we can go really fast and we can be really efficient um as a side note I'll say it's it is based on lattices so fun fact it's also you know post Quantum cryptography it's also in the event someone builds a quantum computer we will be using something like this um if you at this point people are usually like you know okay um I really just want to know how it works can you explain so I will explain roughly like how do we actually get PIR from homomorphic encryption so homorific encryption maybe I could believe that works but how do you actually use it to

privately retrieve data the basic idea is um you have the client encrypt like this large Vector of bits where basically they're all zero except for one in the position of the element that the client wants to retrieve and the client encrypts all of those and uploads them to the server and they encrypt them using a homomorphic encryption scheme so then the server can do this Big Dot product where it takes the entire database and the query dot products them and sends back the result so basically you'll get a zero for all the items you don't want and you'll get a one times the item you want and you'll send that back to the client this is kind of illustrative like we

don't actually upload order n ciphertext and we we do more complicated things than this but that that's kind of like the gist of How It's possible using homomorphic encryption um yeah I have like a blog post that kind of explains more about exactly how this works um I want to say a little bit about okay so like can can you use this um so the speed at which the server processes the database is is really important so par for privacy reasons you can imagine the server generally has to process the entire database for every query right it needs to touch every item in the

database because if it didn't touch an item you would kind of know that the person wasn't retrieving that item so you have to do this linear scan over the database for every single query you make which sounds like a lot I guess the good news is we've done a really good job of making that linear scan very fast in fact it's so fast that it's it's as fast as memory bandwidth so like as fast as you can read the database into memory that's how fast we can do this PIR computation so that means like at 10 gigs a second which is like a rough per CPU memory bandwidth Benchmark um you can for let's say billions of Merkle trees answer a PIR query in less than a second so

um we think this is like or I think this is like finally practical um there's been many years in the making but it's finally like possible to kind of use this in the real world for like this Merkle tree thing and actually achieve privacy at very low cost using homomorphic encryption which honestly has not really been done yet by anyone um so I think it's very exciting um this is like a much stronger kind of level of privacy than you would get if you you know just like use two or three different full nodes or you know use Tor or download you know only a Merkel sub tree like this is a very strong level of privacy right um you uh reveal absolutely nothing about which path you're proving for to the server

um my big asterisk especially with this audience is okay well we know there are other ways to do set membership proofs that are maybe a bit better so if you use a polynomial uh uh like set membership proof um you don't actually need to do this right you don't need to fetch this path to the to the root so um that's definitely uh kind of something to consider like it's like maybe an underrated advantage of the polynomial set membership proofs that that you don't need to gather this kind of um let's call it auxiliary witness data um but it leads to a broader point which is well you know if you're using ZK to put all this stuff on chain and make it

private then if every way that everyone accesses that data is like not private um you you might just like defeat your purpose so I have I think like a little maximum I think about is like yeah whenever you're building unchain privacy um and you have people using light clients that the question to me obviously becomes okay does the RPC node provider just see everything and and you know are we just kind of throwing our hands up at that and it I think that there's finally cryptography that can solve this problem instead of kind of more social Solutions or kind of just trusting the RPC node provider and so I think PR's PIR using homorific

encryption is like a really cool tool for that um yeah I I won't say it's like a silver bullet I think it's still good to use uh other like defense in-depth kind of good practices like you should also try to minimize Network leakage or use like heuristic defenses like using more than one full node but yeah and I'll say another thing which is yeah the costs are really low it's like the headline I think um if you want to like try this or see this we have projects today that can that use this for um or or have tested this for Merkle trees with like millions of notes so it's like practical um and uh yeah I co-founded a company

that just works on basically making this practical especially for like clients so yeah yeah that's that's it [Applause] awesome thank you Samaya do we have any questions for Samaya yeah thanks a lot very nice talk um so in in par you usually need uh to give the client certain hints for the database like basically some pre-computation values that you deliver right and those depend on the state of the database when those were computed

and usually when you the database changes you have to recompute that can you speak to that for a moment what like how your solution looks yeah yeah absolutely yeah so so definitely in academic literature um we the way we Benchmark everything is like we have an offline phase where you can shove like all the hard stuff and then you can just say like the online costs are very low so so one of the things that gets pushed to the offline phase is the hint um there are schemes that don't rely on a hint so so the scheme uh I co-authored uh doesn't so there's no hint there's no um client download on database updates so

um spiral um but you you pay for that I mean the bandwidth the the yeah the processing time is kind of longer but so there's a trade-off in schemes um yeah very good talk I have a couple questions uh one of them is is there a particular reason why you do the PIR layer by layer because the lowest layer already has n entries so it seems like you could just do one PIR for all the N different paths yeah so so there's actually a funny trade-off there so so we don't actually do it layer by layer because of course like the top layers like you say are

like really small right um we if we instantiate all the paths then we've actually made the database grow in size right so remember that the response time is linear with the size so it's actually kind of a bad trade-off to kind of instantiate every path because then we're paying like n log n um so we we do exactly something in the middle so the client downloads like a cap like the top you know whatever x 11 layers at the table and then they download like kind of subtrees of them Oracle tree makes sense and then um I guess my other question was whether the same thing or your protocol or have you looked into the problem of I want to

know like one other application of this is knowing you know did a transaction for me arrive right this is more is it called attribute something based uh PR or something where like I have a public key and I want to know all the data that is associated with it do you think you could do that with this approach or yeah there's there's actually really like amazing work uh on this called uh oblivious message retrieval uh I think it's sponsored by the zcash foundation actually um uh it's like exactly this like you need this public key if you do it generically like with fhe it's like insanely expensive and and slow the the paper comes up with a way to make like a

specially designed tag that you apply in addition to like the normal transaction signature that makes it easy to filter on so so you have to do kind of the the challenge with that approach is you have to do you have to change something about the protocol like all the submitters of transactions now need to add this tag but then it is easy to to do oblivious retrieval thanks huh the solution that you showed on the on the slides it looked to me like you only needed homomorphic encryption as opposed to fully homomorphic encryption is that correct for the actual solution as well yep yep that's why I don't say fhe so yeah um fhe is the one with the with the

million x slowdown today so um I don't use that uh so we we use I guess like the word has changed a bunch but yeah it used to be called leveled homomorphic encryption it just means a homographic encryption that can evaluate circuits of a bounded depth like uh bounded like a priori before we do the encryption yeah so so in in this um oh sorry uh oh maybe um in in sorry so so in the naive scheme I show no it's just linear um so with just linear you can uh get a root n like communication so you you upload root and ciphertext you respond

with root and ciphertext if you want like better communication then you need ciphertext multiplication so we do use ciphertext multiplication uh because it gets you much smaller queries and smaller responses um okay more than one I guess yes okay uh one last question for me it's um so there are other alternatives to fully morphic or fullomorphic encryption which are more towards the previous transfer line do you have an idea of how do we do they compare and why you wouldn't go for the obligence transfer idea yeah so so oblivious transfer is basically PIR plus the guarantee that the client's not allowed to learn more than one item so oblivious like if you have a one out of two oblivious transfer the key like guarantee is that the client's not able

to learn both both uh items in the one out of two they're only allowed to learn exactly one item PIR is like um doesn't make that I guess security guarantee so the client could learn information about in theory all the items if they yes so so oblivious transfer is kind of like a sub it's like a stronger problem if you have oblivious transfer you automatically have par you guys yeah it's it's just much uh slower so so if you just like for for uh n items on a single server uh doing oblivious transfers like slower than doing uh yeah so like if you have like 10 gigs of

data and you want to like oblivious transfer like uh like one kilobyte from it uh you know you have one out of a million or something um so that oblivious transfer is very expensive 28 dclman operations and then you use oblivious transfer extensions and you should be able to do it uh yeah it uh so like the uh sorry say that one first part 128 talk about this yeah thank you [Applause]