ZK11: Let's Build Something Impossible Using Multi-Party FHE - Janmajaya Mall

Transcript

[Music] okay so I hope we had a nice break feeling energized um so in this Workshop well my initial Focus was that it it was going to be a talk and then and then I check the check box for the workshop and now it's a workshop um and um instead of sort of like like in a talk I would rather go at a surface level of how does multi FG works and and sort of just tell you about the applications but I thought that in the workshop it's a

good opportunity to go deep like dive deeper into the schemes and how does it work internally and that is what I'm going to do today so I'm just going to um instead of you know just talking about multibody FG I'm going to introduce the scheme like how does the scheme work as a developer how do you think about this um and then I'm going to build applications using it um the first application is spirit treeville it's it's like a simple you know how do how do you match make homomorphically like how do use Effy to make sure that that you find people is a mchm and the second application is uh homomorphically running ml inference on private inputs so you can encrypt

someone's input and run M model on top of it modly okay so uh um this is the link for the Jupiter notebook that will be using throughout the workshop and this jupyter notebook has everything that I'm going to be sharing today and then you can sort of use it on your own later um now I've divided this Workshop into two things so the first thing is the code thing that I'll be telling you about and the second thing is like second is an hack and be document if you're interested in more theoretical aspects of it like how does it work from a number Theory point of view like like like like the the hard dis assumption and stuff and stuff then you can refer to that hack and document in future but

I wouldn't be talking much more about the theoretical expects of you today but that hack document has everything about you know you need to know about the theoretical expects of all these things um okay so let's get started so can I can I just remove this for a while and and let's get started with the Jupiter notebook looks good okay uh this is working this is working cool okay so so turns out like for the applications that we building today you only need CK K which is one of the F schemes right and when I like to think about

C is like even even generally f as well when I like to think about F I like first like to think about plain text instead of Cipher text because every operation on the plain text directly translates to the to the sorry every operation on the cipher text directly translates to the plain text and for most of the workshop today we would be directly using the r structure that the plain text itself gives you and we'll try to write circuits that make use of the plain text as much as possible like as efficiently as possible like writing the circuit itself as efficiently possible using the plane T so um first we'll talk about the plain text of

C okay so in C the plain text is a polinomial in this ring so what is this ring it's it's this ring is particular is is uh so let's say the ring RN is R modulus x^ n + 1 what this essentially means is that but any polinomial it is a polinomial up to degree N - one with coefficients that are reals that's it that's what this ring means so take any polinomial any arbitary polinomial with real

coefficients but with degree less than n minus one right okay so this this is what I mean by a plain Ty in so any any polinomial that has coefficients as Zs and has degre as L than N is a polinomial in this ring right sorry reals like real value 1.2.3 how many like Precision you talking about like after after decimals uh it depends like depending on the computation that you want to do but it could be it depends on the parameters

that depend depend on your application typically we set it 40 to 50 depending on the application like we scale the value so that we get Precision of 4050 or whatever that is depending on your preference uh okay now like for example over here x x by 8 + 1 this is this could be a plain text right because it has a degree less than um8 and the all the coefficients are in reals right um okay now if I give you any arbitary polinomial right any arbitary polinomial from that exists you can reduce it to

the to this particular ring by simply observing this particular thing right like because x^ n in this modulus can be written as minus1 right because xn mod xn + 1 is -1 so you simply replace xn with minus1 and then you can reduce any polinomial to the ring so you can find the representation of any polinomial in this ring with this reduction um okay any questions you can just stop me meanwhile whenever there's a question okay so um okay now this particular polinomial this particular ring structure has some special property and we usually refer to this property to that property as Nega like property of

this this particular ring so what do I mean by that okay so let's see uh h x n is equal to -1 does it make sense representation of a polom that is xn when reduced by xn + 1 is equal to -1 sorry U yeah uh the reason for that is like you just try to do long division right x^ n x n + 1

1 x^ n + 1 negative you cancel it you get minus one as the remainder so X xn reduc by x + 1 is -1 right so any value that is X by n is equalent to min-1 so so when you multiply two polinomial in this R when you're multiplying let's say this is a polinomial a0 these are the coefficients right a0 A1 A2 A3 multiplying it with B 0 B1 B2 B3 the coefficients would wrap around because a multiplication of x^ 0 with x^

4 x^ 3 x^ 3 will be x^ 3 multiplication of x^ 1 with x^ 3 would be x^ 4 it po add up with the exponent now you write x^ 4 as x 3 + 1 and 3 is - one right so uh the the when you multiply two two particular polinomial some of the terms wrap around and they become negative and this gives the this gives rise to the negly property of these polinomial when you multiply them so the terms wrap around and become negative uh we have shown an example of what the multiplication would look like when you

multiply two pooms in this particular ring okay so uh is that sense like you any doubts cool so over we have written an multiplication like like the code for how do you multiply to particular pooms in this ring and the the concept Remains the Same um okay so we can multiply two pooms in this ring so so cus plain text is a polinomial in this right we can multiply two when we multiply two polinomial we get Nega multiplication when we add to pooms well we get normal coefficient addition that you get in any polinomial when we subtract to polinomial we get normal addition normal subtraction that you get with any

polinomial but the special property to like to remember in this case is that you get this negative nature in multiplication that the terms wrap around and become negative uh now if you take a polinomial in this ring and set that as the plain text let's just like like I'm just calling that as the pl text of SE so that particular type like that particular type of encoding is known as coefficient encoding that you simply take a polinomial in this ring which is R xn + 1 in this ring you take a polom in this ring and you simply call that and and and if you take that as the plain text this particular thing is known as coefficient incuding and the reason we call this coefficient encoding is

because there's a different type of encoding that we also use in C Cas so this thing is coefficient encoding but there's also something called simd encoding that exists in simd encoding the way it works is that H so in simply encoding you can encode a vector like a vector of reals as a polinomial so that a multiplication in the polinomial domain acts like element wise multiplication on the vector so for [Music]

example um you have two vectors A B right these are vector of reals you got reals here there's a way to encode these vectors into polinomial a and b such that multiplication polom multiplication of these pols would result into element wise multiplication of these two vectors okay this is simd encoding and and what I mean by simd simd is like um single instruction multiple data right so the normal computer architecture word that you're familiar with uh so this is known as

simd encoding and the reason why simd encoding works is if you're familiar with f50s um you're familiar with you know the convolution that exists in fpce it just leverages that property to do this um if I have to dive deeper into that like if you're curious I can di deeper into that but like that would be a diversion for the talk so I've written an explanation in this hack document of how it work like it works internally but as a developer you just need to know that when you use simp coding a multiplication of the polinomial results into element wise multiplication of the STS okay and addition and subtraction follows it's it's element wise addition and elementwise subtraction okay sounds good so now we

know two encodings we've got coefficient encoding that is a simple simple plain text like a ring polom in this ring and now we know simd encoding right which is like you can perform element wise multiplication and element addition subraction now sorry just a tiny question about the digits of be the zero that you mentioned right because when you say you work with 40 50 be zero now if you multiply two reals you get you so you add to the digits how do you deal with that yeah

you get to about 100 that's what you do we divide it at something we divide by 50 Afters when you multiply to parans you get Delta Square which is the scaling Factor you use right and then we divide I'll get to that later it's there in the workshop it resolves the question I understand question um okay now we have Sly encoding coefficient encoding now uh this is just the code that I written how Sy encoding works just in case like if you want to understand interally how this works um so the interesting thing is that you can

use these two functions to encode a vector as a simply polinomial Po in the ring so that like for example you get this particular Vector you encoded into a polinomial or this particular Vector in into pomal you can use this function and this function internally calls an fft operation that's it like this this is an ft operation internally um and I've tried so over here I'm so let me just execute everything so that it works okay so over here we sampling two random real vectors you first and then we encoding it using simd

encode as a and b pols and and then we we performing Nega multiplication of the par that is multiplication of the ring and then we checking whether the multiplication of the polinomial in the ring corresponds to El wise multiplication of the vectors and that's what you're doing over here and if you run this particular thing over here you would see that the the Precision is 51 bits so what do I mean by that so well in floating Point values you cannot assert equivalence because there's inherent error in the operation itself so we sort of check how close the the difference how close the value is so the higher the Precision this means number of bits after decimal that are that are like equal and the a is like 2^

- 51 okay so the higher this value is the better is it is for us okay so um hm when you think of vectors what else do you think like when when you think of vectors you can perform elementwise multiplication subtraction addition there's another thing that we think of vectors like can we rotate vectors can we rotate vector left to right anticlockwise or clockwise um and turns out we can do that in this paintex structure as well so for example in simd encoding if you have simd encoding like you encoding a vector as a polinomial turns out you can manipulate this polinomial in a way so that the vector itself is rotated for

example let's say you have a0 A1 A2 A3 and you encode this particular Vector as a polinomial a you can change this polinomial in such a way that the vector is rotated so for example if you want to rotate this particular Vector to the left by one you can rotate you change this way such that it becomes this okay these are rotations and the way it works internally is something called substit substitution operation like um it just

substitutes x with X to pass something depending on the ring structure and it is mentioned the hack document that I sort of mentioned before which you can learn more about the theorical effects but the more important thing to know from developer perspective is that you can rotate the plain Tex with any degree like anticlockwise left right whatever that is um okay so this sort of goes into okay yes so I've given an explanation over here how it works internally and this is the implementation of substitution that we rotating a ring polinomial by left 1 or two um and of here what I'm going to do is

that I'm samping a random Vector s encoding it and then I'm rotating it and checking whether it matches the rotation or not okay so I rotated it left by three and then I check whether the rotation matches the element wise rotation or not and that's what I'm printing over here and turns out it works and infinite in fact means that it's it's like it's exactly the same thing okay um cool any questions um on the P structure so what have we covered we have covered coefficient encoding we've covered cly encoding we also covered that in simply encing a

poom multiplication of The Cypher text sorry of the pl text corresponds to element wise multiplication and simply according you can do something more special that is you can rotate the plain text okay these are these are four to five like three to four things that you've covered now when I think of cic as Cipher texts so we want to take a plain text and then simply fit it in inside the cipher text so that no one knows what no one knows what the PL text is the way we do that is the way I like to think about is that you simply adding the pl text to the cipher text and before I sort of tell you anything about you know how do how do you encrypt a plane text A C plain

text is that you get a c Cipher text I have to introduce to you uh something on ring ring learning with errors which is the hardness Assumption of the basis of all the FG that like all the FG schemes that exist um okay so what is ring learning with is does anyone lisus that is um learning with is a bit so you turns out you can you can and ring learning with there is Builds on top of flatus um and the hardest assumption is that uh

okay so let's say we have q what is Q think of Q as a very big value right in practice it is you know let's say 2^ 800 like a very big value using this Q we create a ring ring of pooms again which I will denote as r q okay NN what is this ring it is z q mod x^ n +1 are you familiar with what this is zq ring of integers modulus

Q right so this is zq that means and then this ring consists of all the polinomial of which the coefficients are are in this ring but have degree less than n so previously it was all the pols that have coefficients as real numbers but now we have all the polinomial that have coefficient in this ring okay zq with degree less than n now this is R q1 now the hardness assumption is that if I sample a randomly from RQ right so we samping a randomly from rqr and we assembling s which is a

c from rq1 with the kvr that the coefficients of s are are from tary distribution so what is the turn dist turn distribution well it's from this particular set right turn means three values so from this particular set so the coefficients of s are sampled from turn distribution and then sample something called e in the ring rq1 and the coefficients of e are sampled from Gan distribution what the normal distribution with some Sigma okay now my claim is that if I give you a s +

E and A if I if I give you this without giving you S and E you can never find what s is okay this is the hardest assumption that we making s s is a polinomial in this ring with coefficients from this distribution okay it coefficients could be 1 - one or Z okay yeah random uh okay so if I give you b and a you can never find what s is this is known as search variant of rwe and this deisal VAR as well but like

we don't care about it right now Okay cool so this is the this is the hard that we making for building C now how do you put a s PL Tex inside and rlw cotex so let's just say that we have this particular rlw cotex right like we have this AR assumption like you have this secret I randomly sample this thing and I get B and I have a here how can I put a plain text inside this thing without without having to do a lot of stuff well the way it works is that let's say I have a message M that is from ring

RN what is rn rn is the ring RN is ring x² n +1 right so it's the polinomial of ring with coefficients and reals x x + 1 so we take message in RN and we scale it by Delta Delta could be any value for example if you take Delta s to^ 40 you will have 40 Precision 40 bits of precision in your operations so we scale the message by Delta and simply add to [Music]

this and this gives you a SE as C and you would observe that by scaling M we've clearly avoided the bits of M getting jumbled up with e because e is eror it's it's the useless thing we don't care about it so this is C is Cypher texed now if you if I give you b and a you cannot find what s you cannot find what m is because you not know what s is right so before the hardness assumption was that if I give you b and a you cannot find what s is again you cannot find find what s is and given that you cannot find S you you cannot find what Delta m is okay so this is the cipher

text now huh okay so we've got this Delta M any questions um scale you just multiply the coefficients of M by Delta and Delta is 2^ 40 50 that I mentioned before like your Precision values how how much Precision you want in your calculations okay what was theot of data the uh what's the Del okay yeah the role of Delta is that you know this error

E right this error is random and the hardness assumption wants this ER to be there so that you cannot find what s is we want to avoid the bits of M getting jumble up with the error so we scale it yeah we scale SC it so that it does not get jumbl jumbled up with bits of Fe so we scale by Delta this Delta is big like to^ 40 50 to^ 60 yeah be yeah so it is just to get jumbled up it is just to avoid getting jumbled up with e but okay fine what I can do is

that I can try to give you an in a better inition of like why we want to scale it okay let's just let's just try it one more time uh let's just get rid of this this mathematical thing uh let's just think of uh in terms [Music] ofs one um six somewh like probably six the the norm of the value like like the magnitude that you can expect expect to you have is around like 20 30 that's 30 30 initially it grows over time as you perform a compute but initially it's

very small okay okay think of this box this is Q okay this is the size of the Cy text which is Q uh which is which is the Q in the AR one right this is the size of the entire box now we sample error from a g distribution which would have a magnitude of like very small the point is that if I add error like if I add message like this over

here simply then my message would get jumbled up with the error because it is being added and this error Is Random so I want my message to be I want to avoid my message to get added to this set so I scale it by Delta so I scale it by Delta which is still big so that my my message is starting from this point so now this is my message okay cool um so now how do we do so once we have Cipher text of Cs like once we know we have a cipher text how do we how do we

work with that Cipher text like how do we perform operations on the cipher text so that the same operations are performed on the plain text okay so first is like before before we do that I would like you to sort of Imagine The decryption structure of The Cypher text so since Cipher Tex was uh B is = to a s + e + Delta M and A is u a was a simply of this the decryption structure of this is B + as s and why is that the case well when you multiply a

with s you cancel this out and you only get Delta M plus right so when I speak of decryption structure I'm speaking of this particular equation of uh b + a s okay in which case C 0 is B and c01 is yes there's a there's a limit there's a limit after which like intuitively when reason through this things if you add to Cipher text the error would get added as well so there's a limit to

which you can perform additions and when you when you perform multiplications the error would get multiplied uh so there's also a limit to which you can perform [Music] multiplications yeah it it does affect and we we do something called bootstrapping operation uh which in fact means that uh we get rid of this homomorphically we homomorphically run this decryption structure with encryptions of s to get a cipher text with reduced n that is one of the most expensive

operations in FG but I can get that afterwards but like but first let's let's just understand how is um how how to different operations of work so we got addition so once we know this addition well addition is a simple addition of the the cipher text components for example let's say there are two Cipher texts Cipher text zero Cipher text 1 addition is let's say this is b0 a0 and this is B1 A1 addition is simple addition of these two values

okay you simply add these values out you get the the the addition of The Cypher texts okay and the subtraction is simple subtraction of these values okay these are two pols you add them in subtract them and uh the reason it works is because if you look at the decryption structure it gives you addition of the uh messages right but the the errors get added as well and you have you have increased error which is why there's a bound to amount of additions that you can do but the increase is not much it is like just twice dat previous value and in terms of bits it's like just one bit got increased right now how do you multiply to

cyhex well okay so in order to explain multiplication I have to okay so for multiplication let's say let's take two CER text c0 and C1 C 0 is equivalent to let's say um B 0 and a0 and C1 is equal to B1 A1 and you know the decryption structure if

if you have the secret key you can get the message back which is Delta m0 plus plus error and Delta M1 plus eror okay right so you got di structure this is a cipher text how do you multiply to Cipher text well multiplication is uh okay so wait a minute so we know that [Music] this is the decryption structure of these values right because when you multiply s with this you'd be able to get U multi when you multiply s with a add with B it is equal to M plus e same applies for this one when you so to multiply to

cypher text you actually perform tensoring of these components so you multiply you you tensor these two Cypher text now are you guys familiar with tensoring uh tensoring is simple as this so you just you just multiply the cross components right so um it is tensing of these two values would be B 0 B1 plus sorry it would be B 0 B1 b0 A1

plus a0 B1 and then it should be a0 A1 okay so this is the tensoring of these two subs and what does that give gives us well it gives us the encryption of well okay so tensoring is this right so you you perform T between these two components you get this particular thing okay very tend of two decryption structures you get the same thing but with s and the so if you have sequent if you have access to the

sequent you can decrypt this particular SI of text by itself so okay is that making sense or am I am I going first good okay so let me try to explain away you need to keep track how many times uh unfortunately not like if if if it was this way then yes but I'll tell you a way to reduce this particular degree after uh so you multiply two cotex with tensoring and the decryption structure of a tensor CeX is this with S and S Square now initially we were working

with a degree one CER text when we think of s as the x of the polinomial so you only needed the access to the SE to be able to but now we need the a secet square to be able to and this is a problem for us because when we multiply the again it become ex S 4 X+ 6 x 16 x and then so on and so forth so the increase in the degree would be exponential which is bad for us so what we need is a way to go from degree 2 to a degree 1 side Tex right and the way we do that is we homomorphically multiply like we

use we multiply this particular term with the encryption of s² and this operation is known as relinearization operation FG it's it's a very simple key switching operation you can think of this s squ is a different key and we switch from s squ to S and we we are able to reduce a s² 2 s and the key thing to note in this particular thing is that it is an expensive operation which is why multiplications are more expensive than additions [Music] okay now what happens to the message when you multip our message

was Delta sorry A message was Delta m0 + e0 and Delta M1 + E1 when you multiply to this these two things what do we get we get Delta squ m0 M1 and then Delta m0 E1 plus Delta M1 e0 right so what in but in but instead of this we wanted multiplication of m0 hello okay so

um multiplication gives us multiplication of m0 N1 but with square of the Delta but this is not what we want we want Delta right so what we essentially do is that we divide the entire thing with Delta and we end up getting Delta m0 M1 with reduced error because you divide everything by Delta but the error is increased although because you multiplied M m0 and E1 and the and the are that is induced depends on the size of m0 because when you multiply a big value with a small value the the the the error depends on the The Big Value like the amount of the resulting value would

depend on the Big Value hence the error in this case depends on uh and the important thing to note over here is that ication the noise growth is higher like the error increases higher than um editions okay now um Okay cool so rotations while rotations I would I would quickly run through them because we running out of time and I need to introduce a bit more things for rotations uh it's a simple key switching operation as well so we rotate the cipher text by substitution operation so if your initial cotex is this right you say substitute x with x^

K that's it that's the that's the that's that's how you do rotations you just substitute x with x^ K so you perform this Subs sub substitution operation and that's it that's what that would give you message as this right because when when the initial decryption structure was C 0 + c1s which gave you m + E when we substituted it would give you mx^ k + e^ x + K and now we need to switch it back which is another key switch operation okay so it give you encryption under s when you key when when you rotate it it give you encryption under this and

now you key switch back so you multiply this with this homomorphically to get an encryption under us this is another key operation that you do do um and it is also expensive but not as expensive as multiplication okay um cool so now I've told you that uh we got C cyer Tes and The Cypher Tes allow you to perform multiplications addition subtraction and if you encode the CER text sorry the plain text as a vector in simd format then you get you can perform rotations as well because you can perform element wise

operations in simply format so what are we going to do today is uh first let's try to build a very small application using it by just leveraging the pl Tech structure of the cks so just leveraging the C PL Tex and then we'll try to homomorphically figure out how to build how to evaluate a CNN using it okay if you're familiar with CNN comination in your networks um okay so any doubts because now we are moving from this PL text thing to to application stuff oh so when you are multiplying anding is that something that you can

like multiply many times iniz data can you accumulate you can accumulate but in practice no that for some reason yeah because it is an exponential gr but you can do that for sure yeah cool uh so okay so let's just say that uh let's just say that we want to build a reading application right like we want to make sure that um you have two two users and you want to ma m match make these users based on their expenditure history like how how how do they spend so let's just say that how would we

build such an application so you usually the way we would build an application is that uh we would categorize their spend expenditure history into categories like for example how much they spend on clothes how much they spend on flights food and sports and then we'll try to figure out how similar this particular distributions are right like how similar this expenditure history is okay that's how you find similarity between two expenditure history and the way usually you would do that is by evaluating something called cosine distance so what is cosine distance you simply take the distribution calculate the inner product and divide by the norm and what is Norm

Norm is like um like any L2 Norm if you're familiar with Norms um just just just like if it if it is L to Norm it is like addition of the like addition of the squares of the values and a square root of that that's a that's an Lor so the way you calculate coine distance is that you take these distributions calculate the inner product divide by the normal now you would notice that this can be translated as to a simple inner product if you make this observation right if you if you write rewrite this as this then it is a simple in product so it turns out to calculate a cosine distance between two distributions the only thing that care

about is evaluating this inner product homomorphically okay uh so how would you do it um so there's a naive way that exists but I'll skip the naive way for today because I've given an explanation here and you can look it afterwards I would want to tell you a way in which you can Leverage The stru the plain text of C such that you can perform an inner product with a single multiplication and a bunch of rotations okay uh and the way that works is is this okay um so we have two

distributions let's say this is me this is this is my distribution of 100 120 140 150 and this is someone else's distribution right some unknown person um another distribution of 500 and so on and so forth you want to find the coign distance homomorphically of this the way it would work is that we would encrypt both of these as Cindy plane texts so as a vector as inside the S PL text right now when we encrypt this into polinomial let's say okay let's just think of this is small J right just better note and

then when we encoded using simd encoding we get a polinomial j right and now when the multip and and we get another Pol a when we multiply these two polinomial we know that it would be element wise multiplication on these particular vectors because it isod SMD right so first before before we do the inner product we first encode them as plain text SD PL Tex and then perform a multiplication which in fact multiplies these these these values element wise let's say multiplication of these two values which is this right these are two two distributions a 0 A1 A2 A3 B 0 B1 B2 B3 you encode them as SMD

and you multiply them you get a plain text that encrypts a multip elementwise multiplication of these values okay making sense okay now how do we calculate the inner product so we have the multiplication we just need to add all these values right inner product is the multiplication and the addition of these values the way we do that is by rotation so first we rotate the existing value to the left by one and add it to itself we get this and then we rotate this by two

add it to itself and we get this which is the addition of all the values so this is and if you have like a vector of size n you can only add you can add all the values with logarithmic number of rotations right and um that's it so that's what we've done here we encode the inputs as simd PL texts we multiply them here once and then we rotate them repeatedly logarithmic number of times log a number of times by doubling the number of rotations that you would do like number of slots that you would rotate by after every iteration and then we check whether the

cosin function works and this is what we wanted and this is what we have right so this is pretty simple like we were able to do this using C pin text okay any questions left 10 minutes right cool any questions okay so um now I would like to move on to CNN um how do you how do you sort of how do you work with CNN so are you f with CNN convolution NE networks uh so you know the normal way work is that you encrypt the private and sorry encrypt the inputs of the user you

do not encrypt sorry you just get get the get the the inputs of the user in plain text and then you evaluate the model how about evaluate the evaluate the evaluating the model on encrypted user inputs and uh so so what are we going today is uh we're going to evaluate a CNN model with encrypted user us user inputs instead of having user inputs as plain texes and I'm going to show you how to evaluate this single convolution layer

so okay so um what is what is a CNN ifar with that because CNN is go ahead oh okay okay the way I like to think about CNN is is it contains a bunch of convolutional layers a single ution layer is something like this you got input channels you got kernels you got output channels each kernel operates with a particular input Channel something called convolution operation which is a simple inner product between the area that it covers and produces an output for the output

channel right so this particular thing is a single Evolution layer and then after which you perform um activation function on the output elements and now you can stack multiple of this convolution layer on top of each other to evaluate a CNN right a CNN is just just a collection of these um these these convolution layers okay so if I can show you that how to evaluate this particular layer with encrypted input channels then you can like if I if I can give you a circuit for this then you can stack this circuit on top of each other to evalate the entire seran architecture yourself

like for multiple like can see an architecture of like something like rest 20 or rest at 50 or something like that okay um we just got 7 minutes left so I would like [Music] to okay okay I would like to I I I would like to skip the boring Parts honestly um and move on to the interesting part um okay so over here what I've done is that so turns out you can do this convolution operation that I was mentioning before this particular

convolution operation right so you have input channels kernels turns out they now when I say batch convolution what I mean is that we perform a conion operation for all the kernels for a specific output channel right so you've got input channels kernels for those input channels for a particular output Channel and a bat convolution is that you perform convolution for a specific output channel right and turn out using cks you can do this using a single Nega multiplication so you can encode input channels inside a cks PL text at certain indices such that um a multiplication Nega cyc multiplication would give you a

convolution operation right so turns out a single Nega Cy multiplication can give you um the output channels now over here i' I've showed how to do that but I think this is the boring part which is why I would like to move on to the next thing which is the most more interesting part which is um how do you perform how do you evaluate the radio activation function uh after you done this after you're done with this convolution and after you've got this convolution output how do you how do you evaluate the activation function now another interesting part before this is that uh for the contion operation okay so yes

um are you fam with r functions Rel activation function okay so once we have done this convolution the second part in convolution layer is to eval valate the activation function of the output elements right and the caveat in this case is that um Val is a nonlinear function like it's what is Val R is this maximum of 0 and x right this is value function this is a non linear function how do you evaluate

a long L function when you only have access to multiplication addition and subtraction right how do you do that well you you you just give up on evaluating that particular function accurately the way you do that you you use something called polom approximation you try to approximate the r function using a polom and the way we do that today is by first approximating the sign function and then using the sign function to build the r function okay so if I give you a sign function sin x that returns 1 if x is

positive and returns Z returns 1 when the x is negative and when X is zero it returns one okay so if I give you the sign function then you can build the function as uh x + x * by 2 because when X is positive this would one so it becomes 2X and it becomes X again when X is negative this would be negative one and this things cancels out right so you can build an L function using the sign function and now we have to figure out how to approximate the sign function now there are several ways to approximate the sign function and I'm just using a simple okay let me just

yeah so for today we'll be using this particular sign function approximation this this probably is more over given most of the time specific yeah because most of the CNS use practice you can replace the AC f with the polom approximation as well like a polinomial function but people are not willing to spend millions of dollars to retain their model yeah so if you can do that for sure you would have faster latency but this also highlights a internent tradeoff in C right because if you want higher accuracy then you want you would

want higher approximation and but in like intuitively high approximation would require higher degree polinomial and higher degree polinomial would require a lot of multiplications hence higher latency right but if you do not want higher accuracy you can trade off the degree with the with the with the accuracy and um that now if you if you want lesser accuracy than a lower degre par would do but turns are like people wouldn't be comfortable with lower ACC so this is tra that exists in CP the the main most painful part in evaluating CN homomorphically using f is this like rati functions how do you perform a non linear thing using a

linear only only only multiplication so um we would be using this particular function today and the main part to note this not the main thing to note in this function is that this particular function only works over the range of minus1 and 1 and has an accuracy of 2us 10 now you can change it to Theus Alpha it could have any accuracy like when I say 2us 10 accuracy it has like 10 bits of accuracy and you can sort of change the function to get any bit of accuracy as you want but if you want more accuracy the degree of the Pol would increase so higher like you have to perform more operations if you want less accuracy the degree will decrease and in most in in practice you sort of like

trading of these things higher degree or lower degree depending on on how much latency you want how much accuracy you want uh but the the the main point here is that you only have access to like minus one and one input domain like the input range is- 1 to 1 but in practice the r function like sorry the CNN does not guarantee you that the input would be minus 1 to 1 right so how do we do that how do we how do we increase the input range of this thing well the solution is pretty trivial we just scale it so instead of instead of using this function directly yeah um just two minutes uh instead of evaluating this

function directly we first take we first experimentally determine what the input range is like we experimentally determined with a lot of test like what the input range is and we set minus B to B as the input range right now we scale this particular input [Music] by is it okay we scale the input by B so that the input is in the range of -1 to 1 and then we scale it back okay so we take the input scale it by B and then we scale it back so we able

to get the input rang in-1 to one and then scale it back and now the problem with this thing is that now the area that was introduced by this which is of 2us 10 is also scaled it becomes b b into- 10 and that's what we trying to do over here so this is the sign function and this is the r function build on the sign function you can see that first I'm scaling it down by B here and then I'm evaluating the sign function and then the r function which is x + x * sin and then I'm and then I'm scaling it back here now you would notice that for 20 like the range of- 20 to 20 if B is 20

the Precision is 7 bits but if I increase the bound to let's say [Music] 50 the Precision is 12 it should decrease so there's something wrong here but the position just to decrease uh but yeah as as the B increases the de something that's it [Applause]