Large-Scale MPC: Scaling Private Iris Code Uniqueness Checks to Millions of Users - Roman Walch

Transcript

hello everyone welcome to a new learn session I'm Vian Placencia and today we have Roman who will be talking about large scale NPC scaling private Iris code uniqueness checks to million of users so as usual you can write the questions in the chat and Roman will answer all them at the end of the presentation you can also unmute yourself at the end of the presentation to ask questions and welcome Roman and thank you so much for being here and the floor is yours feel free to start whenever you want um hello from my side as well thanks for having me so this is a about the project that we have that they have

been doing the last months together with bircoin to solve some of their privacy problems and they mainly involve people rcoin and Philip from bcoin and Daniel and me from Tapo so this talk will be structured as follows so first I will start with an introduction about the problem that we want to solve and then we give the actual protocol which we want to translate into the Privacy preserving setting of secure multi body computation then I will talk a little bit about the basics of MPC so we will all be at the same page after this uh few slides and then I will talk about our main techniques that make this uh NPC application efficient and I will give you um some concrete instantiations of the protocol and finally I will talk

little bit about the implementation and benchmarks and a small conclusion about this um project here so let's start with an introduction so um this talk is or this project is an application of secure multi computation and if I would have to um describe MPC with just one sentence it would be that MPC allows Mutual untrusting parties to compute a function on a combined private input without the requirement of sharing these inputs with each other so the inputs actually stay private and NPC has been researched in the last decade heavily in Academia and it's a very flexible technology where we have tons of different protocols we can instantiate MPC with different security

levels for example the semon security level where the protocol is considered secure as long as everybody honestly follows the protocol but we can also have a malicious security setting where we detect if other parties actually deviate from the protocol or send malicious messages are similar but in this talk we will mainly focus on the semi honest setting to get more performance out of the whole U whole MPC protocol so MPC is in some sense quite similar to fhe so fully morphing encryption and Z knowledge in that sense that it can be actually applied to tons of different use cases to enhance privacy and examples in Academia you often see um new NPC protocols applied

to machine learning or data analysis in a that free infrastructure you have seen MPC applied to threshold signatures and threshold wallets and in this project we will actually use MPC to decentralize a database to bring more privacy to a given database and in this project we apply MPC to the world ID infrastructure so I will talk a little bit about what world ID actually is so this is something that is um um hosted by ver coin and what they want to achieve with bir ID is to bring an unique identifier to humans to the internet you can then later use this identifier to authenticate for different services for example also with Z knowledge proofs but um we mainly look here at the setup base of this um of

this word infrastructure so we are not conservative your knowledge in this doet all so what they want to achieve with this unique identify is that it's only possible for humans to sign up so no AI models um no spam or Etc and it should only be possible for humans to sign up exactly ones and they enforce this with a storing um a biometric information of all signed up individuals in a database so in this setup phase what you have to do is you have to go to this uh to a specific op station so they call this op station you see um an OP here on the slides and what this op does is it scans your eye and deres an so-called Iris code from your image of the eye sends it

to a server and then your iris code is actually checked against this uh server of already registered Iris codes and if you're already present in this database then you get rejected and this Iris code is actually only used during the setup base but unfortunately this requires that work at least previously work can had to store this all this biometric information in a database and this has um huge privacy implications on one hand it's a database of biometric information so that alone is something that we it's not um um is not um well seen also by privacy Regulators but it also allows for potential misuse for example you could

derive potentially um uh information about the humans from these Iris codes let's say um what color the iris have been or you can use this database to sign up for different um Services um which also use Iris codes if you also control one single server with this if you're the one controlling this server you can also um I giving out IDs to some individuals so censorship is also a problem there so you can see there's a lot of privacy implications if they have this single database here and in this project we want to to um to um to change this private application by applying MPC to split this database amongst multiple

mutable um in this trusting Barum so they set up rep the following here so you can see this on the on the slide we suddenly have um after applying NPC we suddenly have multiple parties here and each of these parties have a so-called secret share of this of the database so the this shares on their own do not contain any information so no party knows anything about the Aris codes which are stored in the database but uh if they would collude they could again reconstruct the whole database from these shares and also when we um um want a new human to sign up for the service is the or actually also secret shares the iris to the new uh to these database

holders and so none of these database holders get any information about the new Iris code which wants to sign up to the service here so um no part on its own learns anything but since we have um secret shares of all the data we can use MPC protocols to actually check whether this new iris is contained in this distributed database or not so this is the whole setup that we are aiming for in this uh in this project here so this sounds very nice but unfortunately similar to C knowledge or homomorphic encryption applying NPC to in use case usually leads to an performance uh reduction and we need to kind of optimize the protocol to actually get a a f enough system in practice so but

this uh performance overhead that you get with MPC this highly depends uh again on the use case that you want to to apply so let's have a look at the protocol that we want to translate to an NPC application yeah so in Blain what is happening when you um when you want to compare to Aris codes um is basically the following protocol so in practice you not only have an iris code which here is on the slides the vector C but you also have a mask which is here the vector M and this mask has the intention to to hide some quy bits in your iris code for example when you take a scan of your iris there could be some eyelashes in the way and this mask then re removes this eyelash from the matching procedure

here so we have two vectors the AR code and the mask and when we want to match this AR code and the mask against the the whole database we basically go through the whole database and compare the new Aries to each IR in the database here and the comparison is actually done via so-called fractional hemming distance and the the protocol you can see on the slides so first we have to combine both masks so M1 and M2 to get the the B mask which basically says which bits we should actually consider during the the um the uh the matching here and then we um calculate the hemming distance which is basically just the the the EXO of the both Iris codes

um then we apply also the the the the the mass to this EXO of the iris codes and count how many bits actually set after this EXO operation then we divide this by how many bits are present in the comparison at all so this is done by counting how many bits are in the combined mask and then we um just do this comparison Heming distance divided by mask length must be smaller than some fresher GE so this is a very very simple protocol and this has also been applied to many other use cases but unfortunately when we want to translate this protocol to MPC this can get very inefficient very quickly and the reason for that are the following so first the

the data site that are involved in this work on use case are kind of huge for NPC so for example one Iris code has already 12,800 bits and the database size um the for which is uh currently present at work is uh 6 million Iris codes so when you multiply this together you get a huge database of Iris code bits and the problem with MPC is always when you uh do a computation that um you need to communicate for each multi application or each end gate and the larger amount of data is that you want to compute on the more communication we'll have and then you suddenly have so much communication that this becomes the

the the main bottleneck of your application here so you this Computing part is they need to exchange gigabytes or terabytes of data if we are not um efficient here so the second problem with this with this protocol here is that we are ideally want to compute over different domain Ms so first for the hemming distance so we can see it on the slide before here so we first want to perform an EXO operation which is obviously the Boolean domain and then for the discount once operation we ideally want to do this over a larger uh larger ring so in our case this will be 16 bit integers and afterwards when we want to to compare um the the the so that the when we want to do the

comparison HD divided by ml smaller d that we again kind of want to do with the bullan domain because that's the basically the only efficient way we can do comparisons in NPC so we need to go from Boolean to a larger ring to again to Boolean so this can also become very in inefficient very quickly and just to give you some uh comparison there is a um a paper in the academic literature it's called yanos and they basically try to achieve the same just for different uh um organizations so that they wanted to do Iris code matching for the Red Cross for um uh human Aid distributions and uh they achieve at througho for the NPC protocol about 2,000 IR code

comparison per minute so this is very very slow especially when we consider that the current database size of work is about 6 million Iris Cotes so we need to come up with something better here but before I talk about what we actually did to make this protocol efficient I want to first introduce um some basic MPC protocol that we have been using in this project so um let's start with um I with sequence sharing so what I said what we want to do with MPC is we basically want to to split some data into random shares you can see it here on the on the right side here so we want to split X to random shares X1 X2 and X3 such that none of these shares um give

you any information about the original value X and then we want to be able to compute on these shares and after we reconstruct them we want to give the the the realing result and the very simple but very powerful protocol is addtive secret sharing and how this works basically is so let's say we have n parties what we do is when we want to share a value X we we sample n minus one random values and construct the last share xn to be the the real value x minus the sum of these random elements here so that basically tells us that um each party gets one random element and when we combine them together via the sum operation we are able to reconstruct

the original secret here so this is a very simple but very powerful technique so let's see what the properties we actually get by doing this uh this additive secret sharing so basically since all of these elements are randomly sampled um and we need all of these uh elements to actually reconstruct the secret that means that even if uh as I have n minus one shares I can get no information about the original secet so I need all of the shares together to reconstruct X from the from the shares so this is a very nice property also that the scheme is linear this also gives us very nice property properties

and that is that every linear operation that I apply on the shares leads to a valid share of the result so that basically means if I want to add two shares together or at a share with a constant multiplyer share with a constant then I can do this locally on my share without interacting with the other Computing buts so there's a lot of things that I can do without actually uh talking to the other Computing buts here which is very nice but the only problem that we have with additive secet sharing is that when I have two shared values and I want to multiply them then I cannot do this locally because this is not a linear operation and there I actually have to do some uh Direction with the other parties and how we would

do that that there are several different methods but uh we will see one on the on the next slide here okay um then another MPC protocol is a so-called free body replicated sharing and that is one that we actually will use in this project here and the essense of this um protocol is that um as it says in the name we only have three Computing parties and uh we basically do additive sharing of a value so if we have here the value X we produce three additive shares but the twist of replicated sharing is that each party now has not only one share but two shares so party one would have the share X1 and X3 in this case so each party has

two shares so why would we do that so first um what we get since we using additive squet sharing we inherit the same property that we can compute linear functions on our shares without part interaction so this is something that we basically just inherit from additive secret sharing which is very nice another property what we get is that um since we now have two shares per parties and there's only a total of three shares we basically just need the contribution of two parties to reconstruct the secret and it doesn't matter which of these um uh which two out of these three parties there are um any set of two parties can reconstruct the secret so this is a

setting which we call Honest majority in the in the academic lature and is something we have to keep in mind but a very nice property of this replicated sharing is that we now have a um a native multiplication protocol and that is since I have two shares I can use this formula here that I have on the slides to actually compute an additive share of the multiplication here so um I can translate um a replicated sharing in a multiplication do an additive sharing without party interaction so the only interaction that I will have um for a multiplication here is when I want to uh translate this additive shared result to

replicated sharing again and that I can do by simply sending my share to the next part and I have again a replicated sharing but it is the whole advantage of this replication here is that I have a very simple multiplication protocol and that is is also one of the main things why we use replicated sharing in our protocol another very important optimization of replicate sharing is that is also important for this project here is that when I have a DOT product in my protocol then I can um compute this without um very simply by first Computing a local part of each multiplication and then staying in additive sharing so I don't do any

communication anymore and when I sum up the results and can just reshare the final result to the other party so I can get this replication again and what I get is that I can basically basically compute the dot product but the communication is independent of the vector sizes so I only have to communicate the final result of the dot product to to get the replication again so dot products can be implemented with a very reduced communication between the parties there's a huge Advantage also for replicated sharing in our setting between you will see later why this is the case so another very important protocol that I have to talk about is Shamir

secret sharing so this is basically a different approach to to um get secret sharing here and uh what you can get with it is a so called threshold sharing so I can basically Define uh how many shares I need to um to successfully reconstruct the original secret this also one of the oldest MPC protocols that we have but it's still very very powerful and how do we achieve that is basically by working with pols so when I want to share the value x what I do is I um randomly sample a polinomial so with randomly sample I mean I sample coefficients A1 and up to a randomly and then I put the value that I want to

share in the constant term of the polinomial and when so this is the the soal sharing polom and what the actual shares of in this MPC protocol are are just points on this polinomial so the party one will get the polinomial evaluated at the index one but they do will get the polinomial related index to and so on so basically they have points on these polinomial and we do this um because um what we can do with polinomial we can reconstruct the original polinomial from t+ one shares so I can first choose the degree of the polinomial and then I I know that if I have one more share then I can reconstruct the original polom and

therefore the original Secret by lrange interpolation so this is very nice and it doesn't matter which points I have on the polinomial it just needs to be t+ one um points here and also um since we're working with polinomial we have some very nice properties here as well so first um pols are um also so secret sharing is also a linear secret sharing scheme so that basically means that similar to um do additive sharing inine operations can be computed on the shares without the baries needing to communicate with each other and also that's very nice we have a very native multiplication protocol here as well when I have two points on U

on a PO of two different polinomial I can just multiply them together and as a result I have a point of a polinomial where also the constant term is Multiplied so basically multiplying to shares gives a valid share of the of the actual result but the car here is that when I do that the polinomial degree doubles so basically I need twice as many paries to reconstruct the original value here so in our case when we will use Shamir secret sharing in this project is um we will construct basically the same setup as for replicated sharing we will use three paries and we will choose the um that the um the polinomial degree to be one so that basically means we need two B is

to reconstruct the origin secret so we also get this honest majority setting and also what is very nice in in this um sh secret sharing for our use case is that when we have something like let's say a DOT product or a normal multiplication then we can um actually translate the result to free party additive sharing by multiplying the share with the correct ground coefficient so we basically reconstruct the share in MPC to get an additive share so you can think about it like this um and it basically also gives us the property that when I have um sham sharing with nals 3 and a polinomial degree of just one I can do a DOT

product the result will be a sharing if degree to I can translate this to an uh free party additive sharing and then with one communication round I can again translate this to a free party replicated sharing and again I only need to do this for the result and so basically that means I can Implement a DOT product where that the communication is again independent of the vector size which also very nice for our use case so so far that was the introduction of the NPC protocols that we use in our um in our project here so let's now talk a little bit about the our techniques to make actually this fraction hemming distance comparison efficient with MPC so the first and probably the

biggest optimization that that we did is uh rewriting the hemming distance calculation because the hemming distance this would be the biggest factor in communication and especially when we have Aris code sizes of 12,800 bits so reducing this communication is critical for the performance of the whole protocol so um you can see again here the hemming distance between A and B is basically counting how many bits are set after exort A and B together and what when also um see quite easily is that um we can rewrite this equation to First summing up all bits of a adding the sum of all bits of B and subtracting twice

the dot product of A and B so this is uh gives us the same uh result as count ones of a X or B so and you can also see the only part in this formula where we actually have communication is this do product because everything else is linear and what we have seen on the previous slides is that when I use an honest majority protocol so replicated sharing or sh me secret sharing then this dot product actually has only the communication of one multiplication here so by applying this trick we can drastically reduce the communication requirements of our whole protocol and uh this is also one of the main reasons why we can actually make it prac efficient in practi here so what we will

do in our our setting is so whenever the or wants to share a new Aries code to the Computing parties it shares each bit over a larger ring setd where we choose t such that the this computation here does not overflow and then we can um actually compute the the the hemming distance via this equation here on this slide with just the dot product and reduce the communication overhead to get the hemming distance so this is very very nice and this reduces the the whole communication by this factor of 12,800 that we have for the iris Co speeds so this is very very nice but um so what I have given here is basically just the normal Heming distance and in our real

protocol which we have seen in the beginning we will have a mask here as well and there we also have a very nice optimization where we can introduce this mask into this computation here to reduce um uh performance requirements and this is what we have on this slide here so the optimization that I'm talking about is that we kind of want to code that the iris code bit and The Mask bit together in a what we call a mask bit vector and what we do here basically is um when the mask is not set we want the the M bit Vector to be zero and when the mask is set we set the the bit M bit Vector to minus one if the Aris code is zero and we set it to plus one if the

Aris code is one so basically here with this Mass bit Vector when we have a zero this means the m is zero minus one means mask is one and Iris code is zero and value of one means both the mask and Iris Cod speit are set so why do we do that so basically what the advantage of this is that um we can actually rewrite this equation here uh that we need to compute in this whole protocol so this count ones of the mass hemming distance uh smaller than the thresher times the the the the length of the combined mask the this gets reduced used to just a DOT product on the left hand side and a slightly updated value on the right hand

side so we have a DOT product between these Mass bit vectors on the right hand side we have one minus twice the threshold times the um the length of the combined mass here so that basically means when we want to compute the protocol we don't have to compute this huge statement here with do sums and where we also have to introduce the mask here somehow again and the dot product they do just one product here so this is basically the simplest we can get in our protocol here so um CPU we just have to compute one dot product and then the comparison which is very very nice in reducing the performance overhead on the CPU so the next step is once we have this uh dot product we need to do a

comparison here and um um what is often done in the academic literature when we want to do a comparison of shared values it is um that we rewrite this through an MSP extraction so it's is actually when we choose the sharing to be large enough such that the subtraction does not really overflow then the comparison is equivalent to extracting the most significant bit of a minus B and we can calculate a minus B since we are in a linear secret sharing scheme this does not require Communications so that the only thing where we have communication here is for the MSB extraction and there is also some uh tricks in the academic literature who

get the MSP quite efficiently and these especially work well for free party replicated sharing so this is the main reason why we also use this protocol here in this um in this setting and um so what we basically want to achieve here is we somehow want to translate in um arithmetic sharing where basically we have a normal additive SE sharing where the shares summed up together give the original value we want to translate this to a setting where we have instead of the addition we have the xor of the shares which gives us the original value X and once we have this setting we can just extract one bit of it so the MSP of it and this is then a valid sharing of

the real uh MSP result so that is the main procedure that we want to achieve here and in Pre parted replicated sharing there exists a very nice protocol that achieves this and this works by socaled share splitting so what what you do here in this setting is that you first construct valid binary sharing so sharings with this X or reconstruction algorithm um so you construct the value binary sharings of all of these three uh shares here so when we want to uh construct the value sharing of X1 we construct it as X10 0 so you can easily see X1 X or z x z will give X1 so this is a valid binary

sharing of X1 here and um since we have replicated sharing this means that first party has X1 and zero second party has zero and X1 and the third party has zero and zero so this um valid sharing of X1 the BST can create on their own without part inter action so they they just take X1 if they already have X1 and set the the um share to zero if they don't have it and we do this for all of the shares here X1 X2 and X3 so we have in the end three valid binary sharings of the original sharings here and we need now uh we now need to combine these three binary sharings to get a valid share of

the of the real uh value X and since the Reconstruction procedure in normal additive sharing is just the addition here we can do this by Computing a binary addition Circuit of these uh fre binary sharings here so we have binary sharings so we can compute binary circuits and we need to combine those with additions to get the original result so we will actually compute an binary addition circuit to add together the binary shares X1 X2 and X3 and the result is actually a valid binary sharing of the original value X so by doing this we actually can translate the um the additive sharing of x to a binary sharing of X and then we can extract the

MSP and we are basically done so this works out very nicely when we work over the ring set two to the power K because binary addition circuits naturally perform this modular reduction of set2 power k um but unfortunately when we would work our Prime fields we need to uh somehow introduce the modular reduction mode B also in the circuit here but I won't talk too much about it since we will later see that um we can get away with not Computing over Prime Fields here in the circuit as well so these are basically the main techniques that we're using and rewriting to a dot product optimizing it to a simpler dot product and then doing um MSP extraction to get the final

result so now let's talk about how we could instantiate the full protocol here so first as a first step I want to talk about the protocol where we actually have this Iris code secret shared but the masks are actually known to the Computing parties so we do this here to to make this uh first protocol a little bit simpler and this will be a stepping stone to actually compute the whole protocol where we um also would hide the the mass here we will talk about this a little bit later here but first now um we have the setting the iris codes are shared and The Masks are public here so basically what we want to compute here is this equation on the on the slide so first the dot product and we going to

compare it to some um floating point value times uh the number of maskit set so what we can do on the right hand side we since this is all public we can just uh calculate how many bits are set in a combined mask and um multiply this with this real number and round it and then compute the protocol here so in the end it's just one B product and an MSP extraction that we had so when we now would use replicated sharing to compute this so This basically means that for each bit in the iris codes in the data base we have to uh store two shares over a larger ring so basically we will use the ring set 2 to the power of 16 and so

we will need 32 bits storage for each bit in the uh in the database so this is kind some overhead and when we want to perform one NPC multiplication with replicated sharing if you remember this from the SL before we actually would perform free multiplications on the CPU and have to add these results together but we have also this very nice Advantage then we can use the ring set to the B K as I said we use set to to the power of 16 for this very cheap MSP expect that we had on the previous slide so on the other hand when we would use shamia secet sharing um we only have to share store one share one field element for each bit in the database so basically

the overhead from uh from database is half compared to replicated sharing so this is a property that we kind of want to have but on the other hand um also multiplication with fromia secret sharing is also one multiplication on the CPU so this is also cheaper on the CPU compared to replicated sharing but uh we kind of have to pay for that with Shamir secret Shar we usually have to work over finite field and that basically means that this MSP extract that I had on the previous slide is more expensive since we also have to get the modular reduction in there so ideally ideally what we want to have is Shamir secret sharing for its reduced database storage size and also reduce R

requirements on the server um and also on the for the the cheaper um computation of the of the multiplications in MBC but on the other hand we would love to have replicated sharing for the ability to have these um set to above K rings for the cheaper MSP extraction so and I want to talk a little bit now about why we cannot use shamia secret sharing over this set to the power of K rings so as I said before usually we have Shir Shamir seet sharing over a field because when we do lrch interpolation we need to to do some inverses and we as we know we cannot really do inverses over some rings here but with Shamir secret sharing this is

kind of a special case here because we can actually choose the values which we need to invert during LR interpolation interpolation so when we when we choose these values um uh right then we can actually instantiate it over a ring um because when we choose it right we know that even if we are in a ring we only invert Elements which are actually invertible in this ring but unfortunately when I want to instantiate Shia secret sharing over the set to power of K rings I cannot find enough of these points which I can uh which I need to be to invert here so we call this exceptional points and the requirements for the for it to work with Shamir

secret sharing like interpolation is that for all this exceptional Points each be difference need to be invertible unfortunately when I work over the ring said two to the power K I only can find two exceptional points and for three party sh secret sharing I need actually four of those so it is uh not possible to to get secret sharing over this ring in the setting here but luckily we can use something um called G extension Rings um that is also done in the academic literature so sever times we can use g g extension rings to basically not just work over a ring element but a polinomial over the ring elements to get

more of these so-called exceptional points and when we use um this here um this G extension ring set Power KX modulos x - x - one then we actually have 2 to the power of 2al four exceptional points so we actually when we work over this G extension ring we can do free body Shamir secret sharing but um the the um the disadvantage of this is that now we have to compute over the G extension Rings here so basically every operation that we do uh normally on a field or a ring we now have to do over pooms which can become very expensive very quickly as well but

luckily we we have a very special setting here and that is that we basically just use um J sharing to comput a DOT product so what we can do is that in instead of just backing one of these Iris code bits into one of these Garing elements we can actually back two Iris code bits like uh the this polom here a0 plus A1 * X into a Garing element so it basically means that we can store two bits per ging element and there so amorti this again means that we can uh store just one bit poal here so this is not not not a problem here and also

very nicely when we we choose um this x s - x - one reduction polinomial here what we can also see is that when we doing gorar ring multiplication this actually gives us parts of the dot product that we actually want to compute so when we Ed two bits into the gorar ring element perform a gorar ring m application then a constant term of the result is actually um the dotproduct of these two uh embedded bits here so this is very nice and so that basically means when we want to um use these gar rings in our special setting where we actually want to compute the dot product we basically just have to compute um the

constant term of the scalar ring multiplication and we are basically done we don't even need to compute this upper part here so this is uh super ni to reduce the the the computation complexity by using G rings but this unfortunately only works when we have to compute the dot product here another thing um when we want to translate then this shamia sharing this Garing to an additive sharing we usually said in the beginning somewhere that we need to multiply it with like orang coefficient and usually in this setting we would need to do this also over the gar ring so a more expensive multiplication and there we would also require this upper term here a0 B1 plus A1 B 0 * X but um

if we again do a slide re writing of this um of the of the whole procedure and multiply the L coefficient to the beginning here to a0 plus A1 * X then we actually can get away with just Computing this constant term here and this is then a valid additive sharing over the set to caring um of this B dot product here so in this setting we can actually use shamia secet sharing over gar rings at no extra cost and um we can also work over these set the B K rings so by using Shamir galar Rings we again get um the same properties for Shamir that we just need to uh store one uh 16

bit element for for the shares we just need one multiplication for each shared bit and we have the additional um advantage that we can compute them be extract with a cheaper uh set to the B K ring so in this setting this is super efficient so we will use sharings uh and then we can do everything over set to the power K so the basically advantages of replicated sharing and Shamir sharing combined so okay this was the the first protocol and now we also want to to hide these masks here so um um yeah so so not only the iris codes are shared but also the masks are shared here so both will be hidden from all the Computing parties

so we get full privacy here the main problem that we achieve here in the end is that now this right hand side is not a constant enemy so first when we share the master as as bits the end gate is uh count one so the end gate is basically equivalent to a DOT product so we need an additional dot product um on the on the the comput computation site but the additional problem is that this 1 - 2 * D is actually a real value and it's not that efficient to uh to do a multiplication of a real value and the shared value and round the result in NC so what we have to do here kind of is um approximating this value 1 minus 2T with

a fraction A and B and then rewrite the equation to B times the dot product must be greater than a times a DOT product and what we we get here is that basically since we have chosen the ring set to the power of 16 such that no none of these dot products overflows we also need to make sure that the multiplication with B also does not overflow here so this gives us basically through tradeoffs that we can work on here first we compute the dot products of a larger ring so let's say set um two power 32 such that the multiplication afterwards also doesn't overflow or we keep the same uh ring for the dot product and lift then the result in MPC

to a larger ring before we do the multiplication with a or with B here so and we opt to do this this later optimization to keep the cost of the dot product as low as possible because this will be the main bottleneck on the CPU in the end so and just to give you a quick overview on how we would do then the lifting from a additive share of uh um Modelo 2 16 to a itive share of model 2 to 32 so basically the problem why we cannot really interpret the share share with this larer ring is that um the Reconstruction Works model is 2 to the power of 16 so that basically means when I add two value three values together so

two additions H the result can have two bits too much so basically it means X1 plus X2 plus X3 is the real result plus uh um C1 time to the power 16 plus C2 to the power 17 where C1 and C2 are just individual bits which can be set on so and our strategy basically is uh in in this lifting procedure is um extracting this C1 and C2 bit interpreting x to the power 16 as a share of x to the power two um of two to X model 2 about 32 and I subtract um the these these extracted bits here so this

is basically the main uh goal that we want to achieve and we can extract this C1 and C2 very similar to uh how we did the MSP extraction so basically just Computing this share splitting and then 18 bit binary addition circuit in NPC so this is very similar to this MSP extraction and once we have done that we have lifted a valid sharing of the model to 16 do uh sharing mod to 32 exactly what we want here there's actually one other trick that we can apply here so for this uh constants here before this a ided by B when we choose B to be dual to the power 16 then we actually can um we

actually do not have to do this complicated lifting procedure because multiplying a share with a constant gives us the real result Modo um the the original model St the constant here so this can be done for free in NPC so we basically only have to do this Lifting for um for one of these two do product values and the other one is actually free in NPC this is very nice so that basically means when I have the Aris codes and The Mask bit shared so I want to compute this formula here basically means I have to compute two dot products one lifting step it is here that this dot product on the right hand side because the one on the left hand side is done for free when it CH spe to

be D about 16 and then again and one MSD extraction and then basically the protocol is done so that so far was the whole protocols and uh again we use shamia secet sharing over gings and for the dot products and afterwards we translate the replicated sharing and then everything can be done with a small number of dot products lifting and MSP extraction so nice optimized protocol so now let's talk a little bit about uh performance of our implementations so first of course implemented in on a CPU and did some benchmarks on AWS Kon 3 with uh three parties which are uh connected VI are Local Host Network and

there you can see the dot products we get a throughput of approximately 2 million dot products per second in this setting and for the the second part for this MSP extraction where we do this uh thres comparison we get um a through put of about 10 Millions per second here so combining for the whole protocol the fr that we can achieve in this setting is about 900,000 Iris code comparisons per second which is uh already a huge improvement over this yanos protocol that we um this state-ofthe-art protocol from the academic literature but it's still not um really enough to to give a nice frood for the workcoin infrastructure so that's the reason why

we also investigated graphic card implementations for our protocol here and uh graphic cards are very nice for computing something like dot products and um first part of our protocol is actually a DOT product so we can get a huge performance increase here as well but uh usually when we have um this thres comparison protocol afterwards after this St product there we have a a lot of communication round between the parties so here the bottom neck is more Network compared to just a computing power and usually when you do MPC with graphic cards you always have this overhead of moving data between the GPU and the CPU which cost a lot of performance as well but luckily there

exists something like which is called Nvidia nccl and with that we can basically instruct the gpus to directly access the network and so we in the end we're able to to uh implement the whole protocol just on the gpus without ever moving data from the gpus to the CPUs so we we we um don't have to deal with this performance overhead and so that the uh set was basically we have a bunch of gpus doing NPC with each other and um as I said all this overhead of data transfer on your system and there we can get a huge speed up as well so and um we Benchmark this on a very powerful awsp P5 instances so basically each server had one each party had one of the P5

instances uh and therefore each party had access to 8 h100 gpus and the network connection was uh very fast uh with 3.2 terabits per second and there we can actually get this huge throughput of 2.4 billion Iris codes comparisons per second so this is definitely enough for the current workload for the work Cur infrastructure all right so this is basically everything about the protocol and also about the performance and now I want to spend one slide now on um explaining why we use NPC in this use case and not homomorphic encryption because this is something that people kept asking us when we about this protocol why don't you use homeomorphic encryption for this use case so just as

a disclaimer you can use homeomorphic encryption it's is is also possible to to implement it um and to get the correct result but the the unfortunate thing is before more encryption you cannot get this uh performance that we have here with MPC so this 2.4 billion Iris code comparison per second is something that is definitely not achievable horic encryption right now so um just as a comparison here when you have a look at for example s TFG Larry the the benchmarks they give on their website they have a 16bit integ addition of 100 milliseconds and we would need definitely uh more of those and they can easily see that the performance then

does not scale also one thing to consider when you have a homeomorphic encryption is something called Cipher text expansion so when you um uh so I did some small benchmarks when I want to encrypt one Iris code this actually has already the cipher deex size of 37 megabytes so when you have a database of 6 billion AIS codes you have to multiply this by 37 megabytes and you can see that the the storage and RAM requirements actually also are significantly higher compared to to to the MPC setting here and finally um with MPC what we have for the security here in the setting is that um we require that we have a free Computing part which do not collude with each

other because if they collude then they can reconstruct the original database and with homomorphic encryption is also something where I cannot get rid of this non collusion assumption in this use case here because the main point is that the server who does the computation has no idea about the database so this means when you have an encrypted database with homomorphic encryption encrypted database there must be a key holder which is different from the database holder and therefore if these two parties would UD they could also reconstruct the database so you cannot get rid with of this non- collusion assumption this use case as well so uh no security Advantage we have a slower computation and more uh database size expansion so that that's mainly the

reasons why homic encryption are not really uh useful in this use case compared to NPC so all right so we now come to the end of this presentation so you have seen um that um um we get a very nice performance in the end when we use gpus so the learnings here should be that when you have a NPC protocol that you want to deploy in practice you should actually also consider using gpus for uh improved frut here and another learning is that um uh even though MPC has been mostly of academic interest in the last decade or so when we actually cleverly optimize a protocol and use reasonably fast Hardware then NPCs actually also fast

enough in practice for real world use cases with millions of users or the data sets um of millions of users here so we we I'm very much looking forward to to the next years to see many more NPC protocols be applied in practice here so about this project here so the the um the status of our collaboration with verin right now is that currently a predecessor of this protocol is deployed in practice so basically where we just do the dot product on the shares um but uh we also have done this uh a prototype of this full protocol on the gpus as you have seen on the benchmarks and then now this is in the in the process of

actually getting deployed in practice as well so stay tuned for updates from us or from work and if you're interested in more information about this protocol you can have a look at the paper it is online unfortunately the optimization of the Galla Rings is not yet present there because this is fairly new but uh regarding everything else you can find in the paper so thanks for your attention I hope you have uh learned something about this project and if you have any questions feel free to ask me right now thank you very much for the great presentation and yeah everyone feel free to ask questions in the chat or unmute yourself and ask questions this way like one two minutes for

questions can I ask a question yes sure um thank you for the presentation it was really helpful also as a general background on on NPC uh I have one one technical question and one more general question so uh you were comparing it

with uh this previous uh implementation that is like much slower in terms of uh computation time I'm wondering if the reason for this uh slowness was because they weren't using this honest majority assumption and in general if you were to use dishonest majority would it be like how how worse would would it be um so so yeah um one reason as you said is um they uh had a body setup so that they similarities come from what they want to achieve in the end so that they had the same fraction Heming distance they also wanted to to use the

service as a de application service so that the goal was the same but what they used to instantiate this protocol was completely different so um we had this three party setting with seet sharing and they had actually a two-party setting where they used a a completely different kind of MPC protocol which is called G circuits and um they also then were not able to use this um the thought product optimization and so that the main bottleneck in their setting was really communication cost so that the the the amount of um information they had to share between these two parties to actually do the com compination was significantly higher than in our approach and that's the main reason why they they were not successful with NPC

in their in their paper so they also had an FFG implementation that was slightly faster than the NPC version but also um not comparable to what we achieved here and yeah um the to your second question so when you have this two party setting without this dishonest majority you you cannot really get this uh this advantage that um the dot product requires this reduced communication amount so there you always have to pay the the cost of communicating linear in the bit size of the the AR vectors so you have at least this fact of 12,800 in there so um this is um the the main reason why with a two party setting even if you use secret

sharing like the the as I said the others were using gar circuits but even if you use secret sharing the communication would be significantly higher than what we have so at least by a fact of 12,800 so um that you can give you a rough overview of how um fast it would be in the two party setting here without this honest majority assumption thanks and like the nontechnical was about one of the problem that you define as a like the origin of the paper that was like this type of sensitive data shouldn't exist in like a central database for like a regulat reason I'm wondering if there's any

regulation that kind of mention the fact that if this uh database is distribute then it's okay yeah so so there there is actually a good questions so um right now I think the status is that gdpr and similar don't like to have this uh don't like to see um database like this and this is still not yet um fully clear if applying NPC and fhe is um uh actually then directly leads to something that has absolutely no problem with gdpr this is something I think we need to to to see in the future how The Regulators will react to this uh techniques but uh

definitely my opinion it's the the correct thing to do applying FG MPC Z knowledge to gain privacy but uh I think that there are too little um practical applications so far to see how Regulators actually react to to um in general to this protocol I think uh for the work and setting they were talking to them and um at least some in Europe were uh at least the ones I know of they were okay with uh using MPC here but uh in general um I think it's not that uh clear if um any application of f MPC is directly um uh leads to something that

is okay with Regulators but uh uh it's definitely the right step and it's definitely something I I encourage that you do um but yeah that we have to see in the next years and I've seen in a chat Lucas has posted a paper I think this is about the uh how gdpr interacts with MPC and yeah so maybe have a look at that thank you any other question yes I had one question um

I wanted to ask about since like the eventual identity of the user will be the iris code right which is 128 bits correct I didn't fully get it um can I repeat please so the eventual identity of a user is is one Iris code right yes so um what happens is when you when you sign up you get uh the op takes an image of your Aris and deres the Aris code and the mask uh and um what you then uh you have then to compare this Iris code to the whole database and what

happens in practice is actually you have to do two eyes um for this whole um uh setting so basically uh the or scans both of your eyes and then it is also some rotations of the eyes that get Meed against this database but essentially um um yeah to do AR codes from the human so you cannot cheat by signing up if each of your eyes by want um each of your eyes want and then you have to match several versions of this Iris code so that is actually what is done in practice here so that's why we need a little bit more frut than uh uh just the database so this is something we glance over in this presentation but is mentioned in the paper as well hope this answers the question I did not really

fully get it due to a reasons but I hope this answers it yeah yeah no thanks a lot yeah I wanted to ask about uh uh since it's 1 128 bits if if there's a system which is based on a unique identifier for users for around 32 digits so let's say 107 bits so what what approach should uh should the protocol buildout should take for dealing with a 107 bits for uniquely identifying end users I I'm sorry I I really trouble understanding you the audio is not that great can you maybe um typ the message in the chat please

sorry yeah e and the question is in the chat can you

read it can you see it yes I can read it um yeah so the question is I want to ask if a system identifies end users with a unique idea of 32 digits um 107 bits what approach are available for this so uh I I'm not sure if I fully understand the question but uh um if in general if you want to authenticate the users there are to a system there are several possibilities for example if you use Z knowledge GRS for that then you also don't have to give away who you are just that you are um really um allowed to authenticate with a server but also with traditional systems where you give away your

identity is um with DLS you also authenticate to the system so basically then the authentication key would be uh your private key that but you as I said have to give away your identity but if your knowledge groups in general you can do this without giving away your um identity as well so I don't know if that uh answers your question yeah you can ask in the you can ask in the PSD Channel and yeah and Roman can answer yeah with more details have something so I will follow up in the PC chat thanks a lot thank you you for the

question so yeah if there are not more questions we can wrap it up here and thank you thank you so much Roman for the great presentation and it was really nice having you here and thank you everyone for attending and talk to you soon have a nice day thanks for having me um bye thank you bye-bye