ZK12: Private Large-Scale Similarity Search - Aurélien Nicolas

Transcript

[Music] hi everyone um Orel from inverse Tech so we are a firm in the R&D of crypto you heard that yeah so yeah thanks there we go uh so what is the hogp so this this is about uh search uh protected by cryptography right like privacy preserving search

yep there we go so the problem statement is we want to do a similarity search like look for similar images or documents so it's a very common uh problem in AI is known as embeddings so basically we have Vector of numbers and we want to find like the most similar one or the top 10 most similar ones uh except that the database and the queries are both private and what it means to be private there are variations depends on your on your application what you want to protect from from who right uh we'll see it's very flexible that's

why it's written that way and the database is very large so we're interested in scalability and it's also High dimensional and the high dimensional as we see that excludes a lot of options so our Baseline is the exhaustive search so you have a new query com in scan the database do all the comparison like between vectors like calculate a distance like an aan harming distance cosine similarity then you have all these distances you compare them to find the minimum right and I always insist on you

calculate distances then you have an object which is a distance and you can compare distances to find which one is the smallest right so that's a map ruce um so that is uh very expensive that's the big problem with that obviously all right does anyone have any idea how to accelerate this I already sh this slide so so it's funny everybody every engineer who works on this has to go through the five stages of grief you

know where um first you want to do lsh right like a locality sensitive hash something like this right or you want to do clustering uh like you're going to train K means find 100 clusters and then you say I'm going to look only in the best cluster for my quer and then is 100 times faster or only the top 10 clusters and so on you can try to redefine the distance to be fast CU I said it's going to be high dimensional so it's the distance is expensive to compute so you could say I'm going to make a much cheaper distance

approximation reject everything that is like really far away and then look only at the subset right okay so and I can do layers on that and then I I'm faster still a linear time but faster um you can go for something like Bloom filters and all this family of data structures right that are um approximations based on hash functions basically and there's a really interesting uh family of constructions that's uh that are based on error error correcting codes like FY commitments and

that's that is really cool really cool techniques um but we'll see bet so FY commitment is like like an error correcting code um and you leave out part of it so if the query is close enough to be correctable by the code so you correct it you find a code and the database contains only a a hash or digest of it so you try to correct and if you find the same Digest you you know that you have you have a match so you can construct a search engine that way so all those techniques when you are

in high dimensional High dimensional uh data it doesn't really work like you get a small speed up and accuracy goes done really fast like it's very hard to do like a 99% uh 99 9.9 we call right and speed up is going to be like 3x 10 x at best but we there's very bad tradeoff of accuracy and speed like that's high dimensionality that's just because of dimensionality and you have to make assumptions right if you're training a clustering algorithm or

something and we don't want to make assumptions about the dat actually we don't know of any like so we have one application for this um and there we make no assumption like the data is like random vectors from our point of view and some of them they have like a strange concept of privacy like the error correcting codes for instance it's uh it's a little strange right because you're leaking like part of this a code right yeah like it's not it's not like in cryptography where you leak zero bits here you leak a number of bits that just

enough to we construct and that depends on the uh on the entropy that comes with the data right like data is trying to encrypt itself in a way that's you have very strange tradeoffs and if you want more accuracy you have to leak more so yeah okay so what what we came up with to do that is to use an algorithm which is called hnsw so that's a very famous in the AI world or that's that's how image search in general work or the rag Pipeline with your llm right that uses this if you use

quadron chroma pipe CH yes what does it stand for hierarchical navigable small world so small world that means a graph Network navigable that means it's going to work really well to to walk through it and here call so already with the network with a graph you see that we're going to have a logarithmic speed up somehow right and yeah she call that it's actually multiple graphs so you have a small graph which is course so to first

um find some locations in the larger graph of the next layer and next layer and the bottom layer is everything but you start from a good uh point in the bottom layer so that's the hierarchical part um yeah so then this search is going to um look like we'll make an example that's that's maybe better [Music] um yeah this this search is you start at an entry point and you maintain a set of candidates and you try to improve your candidates so you look

at the next candidate look at the neighbors pick like what is an improvement so that opens opens up New Paths and you update your working set of candidates that way so the extreme if your working set is just size one it's like a a walk right f v graph but you're maintaining more than one maintain maybe 100 candidates at a time and you improve them all at once right so it's like 100 hands and working over vqf so we get a logarithmic scale which is way better than all the others

starting at a certain scale so in the T or hundreds of thousand database size and up millions and so on it becomes very interesting it the the logarithmic scaling kicks in really fast like once like the difference between 100,000 100 million that's like you know almost the same like it's it's a small factor um and it works in high dimension uh it has no assumptions by data so it works on random vectors you can sample random bits and it's still going to work right it's going to pick up a small signal

from Neighbors to neighbors and yeah so that's is very very useful um so hul pack so hul is the bird you know who present the search the the accuracy and the pack that represent the decentralization so so what we want to do is to connect this algorithm to privacy preserving techniques like homomorphic encryption or MPC so the NPC network is the pack and we have two implementations one is in worest and that's where you're

going to plug in the crypto so this wor library is going to drive your cryptographic protocol right so um in the application you have to choose uh how you're going to do MPC what technique you use and hpac is going to tell you what to do like like the sequence of steps and we have a python implementation because you have a lot of parameters in there and you want to also be confident about like what accuracy you get and you want to predict your performance so we have python implementation with a lot of counters and metrics and and it's easier to to hack with it you know we have notebooks

and things like that in there so that's uh what I explain so the beauty of hnsw is how little assumptions it makes so we don't care about vectors we don't care about distances we only care about this you have vector vector identifiers okay just just ID identifier A and B and C and I want to know uh from base C Is A or B the closest right and that translate into the decision of going through a path or

another so the result of that is is a is a Boolean it's not a number so let's say you make a database uh where what is distributed right like it's a secret shared for instance or it's homomorphically encrypted and the algorithm is going to ask this question okay this ID this ID which one is best and then you want V MPC output a bullet so we the buan and then the algorithm can take the next decision so how exactly you protect the

vector and how exactly you compute it that depends on the application that depends who are the actors and the Privacy model so and we have explored both like a maybe if H it's just H H sorry it's um and NPC as well so ultimately we preferred MPC because um because it was faster oh even with homomorphic encryption you're going to have an NPC to decrypt right it's uh but doing a full MPC it does the advantage is that when you calculate

distances in some MPC protocols you can do an um inner product which is very fast we like the inner product of Dimension however many thousands counts as one multiplication in the like MPC on so okay at challenges we do have some leakage so we leak the path of the search queries through the graph right because we we reveal those boan go left go right and whatever system it is that does res search it's going to see these booleans and the

path uh through VF so that can be acceptable it's okay that's that's like quite removed from the content if you're trying to protect only the content of the vectors but then you can add layers of security on top like a te run the algorithm itself in a te so only te sees the path or we also working on on this we're thinking how to do something with oblivious wi R like a cryptographic protection of this path as well and of course that adds a big cost on top of it

right can still be faster at the exhaustive search uh but you're going to have hnsw plus oblivious weal of the shares or Cipher text and then the MPC computation on this tyer text um still end up faster but of course that's like not very easy to do and how you can do that that depends on your application right like who is the uh oblivious server and client and so on so um okay the other prod is that you have a high latency with that so if you do the exhaustive search yeah it's very

expensive but in principle you can put 10,000 processors on it in parallel and it's low latency right um like in the like GPU processors um and in hnsw you do have a a walk so so that's a sequence right so that gives you some latency so the total computation is much smaller but it's more sequential uh and we can parallelize a lot of it so um but but it's it's not as trival as map reduce right you have to really uh have an implementation strategy in it to

decide what you can do in parallel in advance some of it you can do uh speculatively and I have go about this uh you can can also do in parallel a speculation some of the things you computed are not going to be used after you know the decisions from like the over threads uh but you still La way smaller latency so yeah so that's the main thing that we working on right like that's that's how to parallelize this um I want to show some so this I believe I

already explained so so if you want to if you have a similarity search problem that's your process so Define the privacy and the crypto protocol for it you need this operation as I said then what you can do is uh count how many operations you or how many times we're going to call it right so that you can predict your performance and the other side of the coin is you want to measure the accuracy so if you're only interested in the top one result or the top 10 or what what is your metric and then you're going to tune the parameters so there is a whole family of parameters uh that control the

connectivity of the graph and how uh broad the search is and of course that's a performance accuracy tradeoff uh let me just 5 pictures so that that's the kind of scalability that you you you can get so with the datab base size increasing and you see very clearly the logarithmic scaling and when you multiply this by one uh to to the right you're going to be very happy that it stays flat and you have um those

two uh operations right like how many distances you have big vectors in high dimension you have to compute a distance you have an encrypted distance now in your hand or you have two of them so from the three vectors A B C that's ab and B no AC and BC and then you have to compare them right and the comparison is actually in our case it's like way more expensive because you have to do a binary uh decomposition right you you have a uh a ripple carry Adder inside to do the comparison and that's like way slower than the giant inner product for

some reason uh so you count those multiply by how long it takes and that's your prediction yes can Define the Operation here like as that's one of vector yeah you have two vectors and you calculate the distance like a CLE distance something yeah um yeah

those are are very large parameters for very high accuracy if you you might you can probably get do a lot a lot smaller uh but uh and that's without parallelism yeah so that's the total so you might do maybe let's say 100 operations in parallel right so you're doing some 100 things in parallel and 100 times in a sequence right and that's like 10,000 operations that's the that's the order of magnitudes asking it's very interesting problem so very curious to see where the

advances go yeah so so you do have this this High latency so yeah multiply by the number of RS multiply by milliseconds it's it's really intended for um like in Data Center and PC that's not like a worldwide um MPC with hundreds of milliseconds of latency right that's like a millisecond latency between the the servers yeah and again that's that's the high high end of the range right um what else I want to show another thing you you might want to

measure again on your data right that's like totally dependent on your data but that's you can observe uh How Deep The search goes into the graph right so it starts at an entry point jumps to the next neighbor and next and next right uh until it finds some kind of local Minima so it has a working set when it's full uh and then it goes uh it unrolls so it kind of rolls back to the next next next next best candidate and so we back at a lower depth right and then walk into another direction right so you you can observe this that's from that's what the python

implementation does right like keeps track of all those counters and so on then you can uh grab them and then you can use that to optimize your latency and parallelism and the parameters of the algorithm anything else uh yeah that's the justification for the parallelism um so what you see here that's so towards the right that's like time that's we progress of the search and this is the the frequency of actually improving your set of candidates right so at first it's empty

so okay you just add uh and and then it's it's it's kind of random right whatever is the entry point so that's what you have in your working set at the beginning then you find better vectors and better and better and better and once you found them it's becomes very unlikely that you continue improving right so you you have a quite fast uh convergence like this and that means after this phase right once once you're here in this search process um that means what you're going to do you always look at you you are somewhere in the graph you have all these neighbors and they're all bad right kind of so so

you just go to the maybe sometimes one of them is an improvement and you go that way but uh that that means your working sets doesn't change that much anymore that means you can do speculative um computation right in parallel and it's going to work like is you're going not going to waste a lot of speculative computation because it's inv it is invalidated not very often that's what this trying to show anyway um yeah I think that's times is up

um thank you [Applause] anyone else have any questions we have time for a short question or two quick a little faster thank you thanks for for your presentation uh is there any reason you you haven't used orams for let's say obfuscating the access part of the queries have you looked into that approach uh yeah that's that's uh an axis for us that's next but we still working on the on the main one already and that's would

be the next phase to to Perfection right like to perfect privacy yeah but uh the difficulty is is like think of oh uh is is this setup like who is the client and who is the server right and that doesn't match exactly we have to invent something okay for our particular application and for your application maybe it's you have a cent server like this or not and yeah okay thank you hi hi uh thanks for the talk also and um I think on slide nine you showed us your GitHub repositories um I checked that one out um but you said there's the

the cryptography the MPC and the H part is not in their right so um is there the cryptography that you're using for your benchmark is there also a public GitHub repository that uh we that I could check out and if not which um MPC protocols and H protocols say are you using for your benchmarks yes so so so we have a proprietary application like with an MPC custom proprietary uh project so far it will be released uh I I think maybe next year or what whatever there will there will be announcements um so that's the we the crypto part you

have a a trade an interface in us and that's where you plug it uh I don't think we have an example we have plain text examples overwise yeah okay thanks we have also like database Integrations with pogress to store V graph and yeah okay thank you thank you