BitGC protocol - Nakul

Transcript

everyone to our next learn and share. Today we have Nicole from UCLA, PhD student from UCLA and also a PSC grantee who has been working on implementations of authenticated CarPlay. Um, and today he's going to talk to us about BGC. This is uh something he talked to us about internally and it was so exciting that we asked him to share it with with everyone and he graciously agreed. So Nicole, thank you for your time and the mic is yours.

Yeah, as Ali said, hi everyone. I'm Nuckl, a PhD student at UCLA. I'm researching secure multi-party computation or MPC. And today I'm going to talk about BitG, which is a recent work by authors Hanland, Shiao Wang, Kang Yang, and Yuyu. I'll first introduce garbage circuits as a general tool to do MPC and we'll look at its first construction by Andrew Yao which is more than 30 years ago. Then I'll introduce BitG first its semi-honest version and explain how this protocol drastically reduces the per gate communication cost for GCS which is often the bottleneck in practice.

Finally, and this is time permitting, I'll talk briefly about why semi honest security might not be good enough in practice and how gobbling protocols, specifically GC can be upgraded to achieve so-called military security. Let's start with what is MPC? MPC is a protocol or a suite of protocols that allow mutually distrusting parties to compute any function on shared data in a privacy preserving manner, which is without costing each other or anyone else with their private data. In an ideal world, if you had this entity that everybody trusts, you could very easily do this task. Every party just sends that trusted entity, their private data. Um, he or she will compute the function and broadcast only the output, forgetting everything else that I knew. MPC is

using cryptography to replace this trusted party. In a little more detail, an MPC protocol just looks like people sending each other a bunch of random messages which somehow reveal nothing but the output of the computation. The goal is that these randomlooking messages somehow suffice to allow the parties to compute the function. They get the output of the function in a way that preserves computational integrity. So they get the correct output and input privacy. You don't leak uh your sensitive information to other parties. But what exactly does random mean? You know, if it's if it's random, how does it help you compute anything?

If it's not random, aren't we leaking something? How do we formalize this? It turns out that the security of NPC is formalized in a super fascinating way. As I said, an MPC protocol looks like something that we have on the left. Parties send each other messages. But for a moment, imagine living in that ideal world that I spoke about earlier where we have this trusted entity. Everybody trusts him, could send him their inputs. He'll compute the function for you and broadcast the output. Note that in this ideal world, each party would literally only see their input and the output. Nothing else. No random messages either.

Now we say that an MPC protocol on the left is secure if these random looking messages in the real world give you as much information as you'd obtain in the ideal world which means nothing rightly an MPC protocol is secure if there exists a simulator living in this ideal world that can just look at the view of a party in the ideal world and use that to simulate the view of the party in the real world and with this for all intents and purposes as a user or a developer um you can just view MPC as this trusted entity that allows secure computation on shared data. It's clear that MBC would be tremendously useful where you want to in any situation where you want to like collaborate on data in a privacy

preserving way. Some examples are um uh statistical analysis. So say organizations hold sensitive data, they want to pull it together for some kind of analysis or biomedical computation. Um patient data can be very useful for research but it's often legally protected. NPC can uh be used to still gain insights from the data without ever revealing the raw data. And NPC has also been used in um satellite collision detection where governments want don't want to reveal the exact position of their satellites but they still want to know if their plan trajectory might lead to a crash. And finally um MPC can be very useful in AI. Consider uh just one example is where you have a server that's holding the weights of some large language model. You have a user with a

sensitive query. the user wants to query the model such that the server doesn't learn its private query and the server doesn't want to reveal its weights to the user and sure you could do you could you could use MPC but with so many potential use cases why has MPC not been adopted at a much broader scale and the primary reason for this is its practicality current MPC protocols um incur significant slowdown in runtime we call those random messages that I mentioned earlier they actually turn out to be really long random messages and generating ing them can be computationally intensive. On the bright side though, NBC protocols have been rapidly improving over time and the protocol we're going to see today introduces ideas that I think might be

very useful for making PRA MPC practical in the future. Today, we'll focus specifically on MPC for two parties dubbed 2PC and only look at so-called garbble circuit protocols. or GC is a tool that was introduced by Andrew Yao as I said 30 years ago and since then it's taken on a life of its own and it's today it's the most popular way to do constant round MPC by constant round I mean that the number of rounds of back and forth communication between the parties is independent of the complexity of the function that you are evaluating under MPC remember I said MPC is a general tool you can use it for any function and um because it's constant round this is um especially useful in high latency settings and it's usually

the most efficient way to do MPC there. At a very high level, this is how a GC protocol works. We have two parties, the cobbler on the left and the evaluator on the right. And they start by agreeing on this boolean circuit representation of the function. For example, just consider a circuit that consists of and and ex gates. This forms a complete basis for computing any function. Um there these gates are ting complete. Now a GC protocol proceeds as follows. The gobbler on the left looks at the circuit and to each internal wire of the circuit he associates two keys um representing false and true. So the green represents false here the red represents true. Next he uses these keys to generate um these encrypted truth tables more on that

later for each gate of the circuit in a way that um pairs of input keys. So if you look at the AND gate with input wire as a A and B and output wire D um pairs of input keys should um encrypt the corresponding output key according to the logic of that gate. So uh the zero and the zero key should encrypt the zero output key 0 and one should output the zero output key one and one should output the one output key because I'm looking at the AND gate specifically. Um for the time being I'm not going to specify more details about how this encryption works. We will look at that in more detail when we um specifically consider Yao protocol. Then these encrypted truth tables are sent over from the go the evaluator and this comprises most of the GC communication

cost. This is the thing that we're going to try and optimize for in our protocols. Next, we want a way for the evaluator to obtain input keys that allow her to decrypt these encrypted truth tables and proceed inductively through the circuit. So we start by wanting her to obtain input keys corresponding to a chosen input of her choice. So the next step is that the goblin and the evaluator they engage in this oblivious transfer protocol. OT is a primitive that's used widely throughout MPC. We won't get into the details of how it's implemented here.

But the functionality it achieves is that it lets go the garbage send over key pairs. Um so for input wires ABC he'll send over these green and red key pairs. Um and he can send over uh he could send over the matching keys the the keys that match the evaluator's inputs while one hiding the complimentary key from the evaluator and two also hiding the evaluator's input from the gobbler. For example here if the evaluator picks input 110 she'll receive red green keys corresponding to wires A B and C but she doesn't look at the green green red keys corresponding to those wires.

Now the evaluator holds keys corresponding to these inputs. She has the encrypted truth tables and she can um inductively proceed through the wires as as I mentioned earlier and she can now output um the key gate by gate by decryting with her input keys. So for example with two red keys she will decrypt a red key for Yod and then with the red and green key for the next gate she will because that's an XR gate. So one XR0 is equal to one she'll again decrypt the red key. Finally, she'll obtain some key either zero or one. She won't know that yet. But then pooling that information with the goblers's information. She can now decode the output of the circuit. In short, um this is what happens. The parties use OT to transfer

input keys. Uh then the goblers sends over this GC material, the main course of the protocol to the evaluator who proceeds gate by gate and obtains output keys. Very importantly, note that for each intermediate fire, the evaluator obtains exactly one of two possible keys and does not learn whether this corresponds to zero or one. That's important. He doesn't learn whether this intermediate fire value is a zero or one. Here we can see a red key or a green key, but she doesn't know that. We want to keep that hidden from the evaluator so we don't leak any extra information. She only decodes the output keys information along with the gobblers along with uh the information that the gobbler has.

Now let's look at a specific GC protocol that's YA protocol the first one that was introduced. Um I've already gone over the framework of how GCS can be used to achieve general 2PC. So it just remains to fill out certain details like how are these keys picked? How are G encrypted and how they're decrypted. This is what the gobler does. He starts by picking two random bit strings. We'll use um a length of 128 bits in practice as a true and false key for each wire. And then he creates this um table of cipher texts that encrypt output keys using input keys as I said. So specifically for an AND gate here look at the first table that I have um keys A I and BJ should encrypt output key D I and J which is what you'll see if you

look at the four rows. So that once is sent over to the evaluator the evaluator can decrypt the appropriate output key with her input keys. Um here just to explain the notation. H is a hash function. It's it's modeled as a random oracle. And without getting into any any details, all this means is that with um input keys AI imi and bj, you can compute h of aibj. But if you don't hold either of these keys, that just looks like a random value to you that you can't guess. So given two keys, the evaluator can decrypt exactly one row of the encrypted truth table. That's how how we've arranged it right now. Um but remember that the keys that the evaluator holds uh they correspond to the underlying wire values for that wire

and um we don't want the evaluator to learn whether this is a true or a false key. So the protocol as such if you just send these tables over it's still insecure because the evaluator she'll end up learning which row she can decrypt and that might leak information about which inputs she has. So one fix is just have the gobbler randomly permute these um permute these rows, send that over to the evaluator and then she'll try decrypting each row until she gets a valid decryption. This way that uh decrypted position won't leak anything about the logical values. Um before proceeding to the next GC protocol, I'm going to talk about two optimizations to y protocol um which are free exord and point and permute. These

are pretty relevant for BitG and that's why I'm going to take five minutes to look over these optimizations and they're very clever bits as well. We'll start with free XR. Now, as it turns out, very surprisingly, there's a way for the gobbler to set the bio keys in a slightly smarter way so that you actually never need to send over any material for XR gate. XR gates are free. Now, the protocol cost only depends on and gates. That's cool, right? Earlier I said that the gobbler, he picks random zero and one keys. Um, but now I'm going to modify the protocol and say that he only picks random zero keys and he picks this one global offset. We'll call that delta. And then he sets all the one keys to be the zero key exor that same delta.

Also, he doesn't pick all the zero keys at once. Instead, he now proceeds through the circuit in a gate by gate order. And then for X or gates, he won't pick that uh he won't pick the output key of that at random. Instead, he'll set the zero key of the output to be the X or of the zero keys of the input. Note that I've dropped my zero and one subscript notation here. If I just use the letter, that's the zero key. If I say X or delta, that's the one key. The reason this thing helps is now the evaluator can actually compute the correct output key just by exorting the two keys that he has without needing to encrypt any table. Um one quick example say that um the evaluator has a and b plus delta. She doesn't know that this

is the zero key and the one key but say that we know this is the zero key and the one key. She just exores the two gets a x or b x or delta which is c xr delta because of how we set it which corresponds to a value of one which makes sense because 0 xr one should be equal to one. Um this basically just boils down to XR being a linear operation and it works well with C data. So we only need to worry about the nonlinearity which is captured in the AND gates. Um in fact we have like uh optimized circuits for computing AES that try to have as many XR gates and as possible and minimize the number of AND gates because that's most efficient for GC protocols.

And for the next optimization, remember earlier I said that the earlier I said that the evaluator still can't decrypt every single row of the table. But but this isn't ideal. Somehow um it would be it would be great if there was a way for the evaluator to know exactly which row she could decrypt in a way that doesn't leak any information. There is a way to do that. Um what we have here is that the garb along with picking these input keys now he picks random bits. These we call these permutation bits. He picks random bits for all the wires. So he picks pi a and pi b for wires a and b and he uses these to randomly per table. So um without getting bogged down by the notation here um if the gobler

picks pi a is equal to one you just swap the first two and the last two rows of the table. If he picks pi b is equal to one you swap the odd and the even rows of the table. Along with this we now arrange for the evaluator to somehow learn these masked values which I've written on the right. These masked values are the underlying V value which we keep hidden from the evaluator. Exor with the permutation bit which again we keep hidden from the evaluator but the gobbler knows. So individually these two values should be kept secret from the evaluator. But it turns out that it's okay to leak the XR of the values. And it's incredibly useful to do this because now the mast value that the evaluator holds points exactly to the

row in the encrypted table that she has the labels to decrypt. Um it's it's best to see an example here. So let's quickly walk through one example. Uh say that the gobler sampled pi is equal to 1, pi b is equal to 0. So we flipped the first two and last two rows, but we've kept the odd and even rows unsweped. and assume that the evaluator also holds masked values. So suppose she um ended up with labels a 0 b 0 here um with the permutation bits that we've set this would correspond to m values one and zero. This corresponds to the third um index of the encrypted table. And if you look at the third row here, this is exactly um the row that she can decrypt with a z and b 0. Um and I'll

acknowledge this is something that can take time to digest. You need to probably work out an example by yourself to be convinced that this works for all the rows. Um but for the purpose of this talk just understand that the gobleration uh these are used to randomize the truth table in a way that the evaluator can directly point at which uh row to look at. And importantly the evaluator never learns the permutations bit picked or the underlying v values for the labels that it holds just the x or of the two. Now a lot of effort has been spent over the years to optimize this even further improves the communication efficiency of these protocols and that's usually measuring the number of and number of bits per and gate because XR gates are

free. Um in Yao's protocol with the optimizations we discussed we had the go send over this entire um truth table of four rows. So we sent four cipher texts. This is all each of this is an encryption. So we sent four cipher texts of material perate. Over the years this has been was like really clever tricks. hasn't been reduced to three cipher texts, then two, and then even 1.5. Um, but for security reasons, each of these cipher texts is still set to 128 bits. So, this is still about 200 bits of communication pergate. The GC, the work that we're going to look at today, it reduces this per gate communication to just one bit per gate, which is like a 200x improvement per gate, right? That's

crazy. Um it's important to mention that um BitG does make some strong assumptions. Specifically, it uses the so-called learning with errors assumption. Whereas the other works only use a random oracle. They use a half function with a couple of extra assumptions and that's modeled as a random oracle. But still there's LWE assumption. It's very well studied. It's the same one that's used for homorphic encryption if you've heard of that. And if you haven't, it's something that we'll look at soon. So a really exciting result. How does it achieve this improve uh this like super impressive improvement? It does that by working a slightly different gobling framework. Um so let's look at a very high level difference between previous works and bitc without going into details right now and

exploring that slowly. Previous works for each gate you uh had the gobbler encrypt the correct output key with like all the possible um input key pairs uh arrange that into this truth table. send that encrypted material to the evaluator. This consists of most of the cost and then the evaluator uses her input keys to decrypt those output keys. This work use a different approach. Now the gobler um he uses his input keys to encrypt output bits. More on that later. This uh what output bits?

How are these enough? Um we'll look at that in more detail. But he now encrypts output bits rather than like encrypting that output key. And um before all of this happens what what happens is this um the parties engage engage in this pre-processing phase where they distribute correlated randomness. This uses constant communication independent of the circuit uh being computed then using one correction bit to the evaluator who can locally produce these encrypted bits. So these bits were computed by the gobler. gave her the encrypted versions of those bits were never sent over to the evaluator. The evaluator had her own pre-processed

material and she corrected that with this one bit of communication to the encrypted bits that she needs and then she'll use her input keys and the encrypted output bits to somehow produce the output key. Right? Um the idea is that the evaluator has like reprocess material and then from there just one bit is enough to reconstruct the entire uh garb material and then proceed with the evaluation. in a little more detail. Um, we'll start with the GC starts with a computationally more expensive pre-processing phase uh independent of the circuit being computed and independent of any input. So, this can be done beforehand before they even wonder uh they agree on which function they want to compute. Um, this uses low

communication. And what happens is the gobbler he picks a random seed. He encrypts the bits of the seed with a secret key that only he knows and he sends over the encryption of the seed to the evaluator. The evaluator uh he uses homorphic encryption. More on that in the next slide to homorphically expand this encrypted seed into a lot of random encrypted bits. These bits are known in the clear to the gobbler and these are known in encrypted form to the eval evaluator. But they're random bits. So these random bits clearly can't uh consist of the GC because it can't be like completely independent of the circuit. Yet these random bits plus just one bit of information per gate from the

gobbler is enough to generate this GC of encrypted bits which can then be used by the evaluator to use input keys and decrypt the output key. For the next few minutes we're just going to look at um we're going to try and understand some more details about these step the steps these steps. Um, for now, appreciate that we've moved to a different goblin framework. We're not encrypting keys, we're encrypting bits, and we're just using one bit to correct an unfixed GC that the evaluator has. So, homorphic encryption. Um, oh, yeah. Uh, Andrew.

Um, yeah. Hey, I just wanted to uh clarify for a second. Um, so I I thought for a minute and now I think maybe this is not true, but maybe you can clarify. The it sounded a bit like the way this scheme works is we fundamentally sort of recover what we would have had in the garbling in the type of gobling scheme we were talking about before or at least some variant of that um and then we can proceed and sort of use that but you know achieve the same thing with less communication. Is that roughly true or roughly false like is it the same do we recover the same kind of thing or is it fundamentally a different thing that we're recovering through this technique?

Yeah. Um butically speaking it's a it's a good framework to have that um we are recovering something very similar to the previous scheme and then we're using this trick of like having correlated randomness to just use one bit to correct it. Um the gobble circuit that we are recovering it's different than the one that we've seen before. Uh it's similar to the uh in the table I said there was one thing that used three cipher texts instead of four. It's actually very similar to that. Um but we're using these encrypted bits instead. Um it's an okay framework to have in mind, but I don't think that's exactly what's happening. And I think um as I continue with like the more explanation about how this works, I think you might get some more clarity.

Okay, cool. Can I ask one quick question? Yeah. The the wire labels that we recover in this system, are they like 128 bits corresponding to the 120 bits of compute security? Yeah, they are. Yeah. Okay. Okay, cool. I think so. Yeah. Um Okay. Yeah, I think there. Cool. All right. Thank you.

Okay. Yeah. Back to homorphic encryption. So homorphic encryption is uh it's an encryption scheme that supports computation on encrypted data. Um and this work just uses somewhat homomorphic encryption which supports computing simple functions on encrypted data. By simple functions I specifically mean functions whose um circuit representation is low depth. And this is much cheaper cheaper than fully homorphic encryption which can support arbitrary function functions. that requires an expensive um bootstrapping step to control noise growth. Um also this is why we don't just substitute MPC with homorphic encryption. They both do achieve a similar functionality of being able to compute on private data without actually seeing that private data. But

um FH is still not as practical as MPC. Yet I'm saying that this BitG protocol it uses um BGC is used for MPC and I'm saying it uses homorphic encryption as a sub routine. Um, crucially, BitG will only use homorphic encryption in a way that the noise growth is independent of the circuit being computed. Therefore, we don't need any bootstrapping and this is still um completely efficient in terms of computational cost as well. With that, we're ready to dive a bit deeper into how bit GC works. Um, I will skip a lot of details here. Um, I'm going to answer two main questions. What are these encrypted bits? Um answering Andrew's ear all your question, we said this is GC consists of encrypted bits.

What exactly do they look like and how are they used to decrypt the output key and how is one bit of communication enough? Um both parties here they started with encrypted random bits that I could I said that that can be produced with constant communication and then just one bit of communication per gate is enough for the evaluator to reconstruct the GC. How do we do this? Because these are the two main ideas. I'm going to like reiterate it uh once more by while taking a look at this high level overview of the protocol. This is the previous slide. So I said this is a gobbler. He uses his input keys and pre-processed bits to generate a GC of encrypted bits. What are these encrypted bits and how are they used by the evaluator to decrypt the correct

output key. Second, I said that these encrypted bits never need to be sent over. You just have uh the evaluator. the evaluator she has her own um correlated randomness and she can just fix this with one bit of communication to these encrypted bits and then proceed with evaluation. How is this done? We'll answer both questions one by one. We start by looking at what are these encrypted bits that are needed to make this protocol work. And I'm going to start by introducing a key technical component of bitc which is an extension of homomorphic encryption to support something called distributed decryption.

Um technically this is achieved by a simple extension of H. Um uh it's a simple extension of one scheme that implements G H which is called the GSW scheme. And we're actually only going to use distributed decryption in the context of the specific um EV algorithm. So let's just look at it as a high blocks right now and see what it achieves. So um yeah unboxing what's going on here. We have an algorithm that takes in two keys and three encryptions of bits. It takes three sash attacks and what it what it achieves it it is it allows parties that hold encrypted bits and shares of a secret key. Okay. So the the the bits here they encrypted under a

secret key delta. And the parties don't need to know delta here. They can have these shares of because u the first thing is a share of i times delta. The second thing is a share of J * delta. So they can hold shares of this and they can use that to obtain pairs of a linear combination of the bits. Okay. So neither party here needs to have the secret key and that's why we don't expect them to be able to decrypt the exact bits. But still with the shares of the keys that with of the key that they have, they can use that to decrypt shares of a linear combination of bits. Um this does seem a little bit contrived but it turns out to be exactly what you need um for the evaluator to obtain output keys from input keys and um it's simple to achieve this functionality. So

let me show you how this algorithm is used. Recall what I said earlier, the evaluator uh she has to use these encrypted bits um along with her input keys to get the desired output key and compare this to how in Yao GC she used the encrypted truth table and her input keys to get the desired output key. I'm going to skip a lot of details here and um I think questions regarding more details here we can probably postpone them to the end. Um it's very interesting to work out these details but for now let's just look at what we get from here. So the gobler he picks keys he picks these bits sorry based on those permutation bits that I spoke about earlier. So each of these bits is a deterministic function of those

permutation bits for the three wires of the kit by a pi bi c. Um he sets them as such. Um this is it turns out this is what um allows the algorithm to go through and work out how we want it to and he sends for a second pretend that he sends these encrypted bits across to the evaluator. Then if he also sets one of the output keys according to this EV algorithm then if the evaluator runs the EV algorithm on the keys she holds it turns out that this algorithm like magically works out to give her exactly the output key that she should get here.

she can just out compute EV on her input keys and these encryptions and the math works out to give you um the output key that the evaluator needs here. This should convince you modular a lot of calculations that need to be checked that the encrypted bits and the magic EV algorithm achieve the gobling task. Okay, but in this picture I still have a gobbler sending over um these encrypted bits and that that's too much that's too costly. We wanted it to be just one bit of communication per gear.

How can we do away with this? How can the gobler communicate across these encrypted bits to e using only one bit? This is where the pre-processed encrypted random bits and homorphic encryption come in handy. So along with the input labels now uh remember we have arranged so that the evaluator she has encryptions of random bits and these random bits are known in the clear to the garb. So we set these exactly to be the permutation bits pi a by b and we also generate one um additional random uh bit we'll call that rc an encryption of a random bit for the evaluator and the random bit for the gobbler um and recall that to run her algorithm she needs these oh yeah Ali Nicole I

encourage you to use the marker to point to where you're talking about of course yeah so we have the evaluator hold these encryptions of random bits by A and P by B and we also arranged for her to have an extra encryption of a random bit RC. Recall that the encryptions of B1, B2, B3 are what the evaluator needed to be able to proceed with the evaluation algorithm. We want her to obtain these encryptions without the garbler communicating across these encryptions. But these three B1, B2, B3, going back to the previous slide, these were just functions of the permutation bits pi A, PI B and PI C. And these functions are pretty simple to compute. It's just one

gate. So like an AND gate and an XR. This is where homorphic encryption comes in handy. So um we inductively arrange that the evaluator has permutation bits for um input keys that she already holds. So say that she has encryptions of pi a and pi b at this point. And if she had an encryption of PIC C as well, she can just use the same logic that the gobler gobbler used here, but along with homorphic encryption to obtain B1, B2 and B3. He doesn't yet have PIC though. Um, but this can be communicated with like exactly one bit of communication. We had this other random bit RC. We have an encrypted version of RC that the evaluator holds.

The gobler knows PIC and the gobler also knows RC. He has that initial PRG seed in the clear. So he knows all the randomness that the evaluator has encrypted forms of. He can just send over this correction bit PCXR RC over to the evaluator. And now the evaluator will look at her encrypted RC exort that with this correction bit homorphically and obtain an encryption of PIC. Now she has encrypted versions of pi a pi b and c pi c and she can use those to homorphically compute uh encryptions of b1 b2 b3 and then proceed as before use the evaluation algorithm and get the output key. So other than the pre-processing

step for this to work we need only one bit of communication per kit and doing a quick cost accounting here. The communication here as I said it's dominated by that encrypted seat that was initially sent and these correction bits. So we have um lambda like the security parameter. So 128 cipher text that need to be sent for the encrypted seal. Each the size of each cipher text is quasi linear in the security parameter is quasi linear with supposedly large constants. Um but it is still independent of the circuit size.

So it's uh slightly more than quadratic in the security parameter asmtotically speaking and you need one correction bit to be sent over per gate of the circuit. So the total uh communication in bits is like size of the circuit plus slightly bigger than quadratic in the size of the security parameter. And the computation here turns out to be dominated by this homorphic evaluation of the PRG in the first step and this EV algorithm. you can set parameters so that um you can use this so-called low complexity PRG and that gives you um an amortized cost of 01 homorphic operations per gate um adding both the PRG valuation and the EV algorithm. So these are the costs of bit GC and the next question is is the

security good enough and why not? Um okay so all I've shown right now is that these protocols are secure and they hide the data that you would want to hide so long as parties behave right now going back to Yao's GC um the algorithm that I described the gobbler uses to gobble these gates the gobbler could actually incorrectly gobble the gates so that the evaluator expects to obtain the output label corresponding to an endgate for this first gate with a b and d as the wires but instead the gobbler used the the logic of an orgate to go this and now the evaluator has ended up with this f wrong output key and remember we don't want the evaluator to to learn which output key she has. So this is something

that's not detectable by her and this could lead to the wrong final output and this could like even leak some sensitive data data that you don't want to you might think that one um fix here is just attach a zero knowledge proof of correct garbling here but actually even this is susceptible to the so-called selective failure attack. Um so looking on the right here um the gobbler can do this really nasty attack which is selectively gobble rubbish for some rows. So for the third row he just puts like random bits and gobble all the other rows correctly.

Now the evaluator might be able to detect this and abort. So like if the zero knowledge proof at this step fails you might abort if and only if she had masked values corresponding to 1 zero. If she bots, the gobbler now knows that she had masked values corresponding to 1 zero. And he also has the permutation bits pi a and pi b. And this now leaks the value the real vio values x and y using um the fact that the evaluator aborted at this row which gives these m values and the fact that the gobler knows what pi a and pi b are. Luckily, it's true that the evaluator cannot cheat here. Um assuming that initial OT is done in a maliciously secure way

which can be done pretty cheaply. Um the evaluator has been given the GC material and at worst she can follow a different evaluation strategy and then ends up with rubbish outputs that like don't map to any output keys. But by the security of encryption she can't learn output keys for any inputs that she doesn't have. So upgrading this protocol to be maliciously secure and I'll explain what that means in a second. um that task mostly consists of handling malicious gobbler. Similarly for bit GC um one way to uh one one thing that the gobler can do is just send the wrong bit to the evaluator when the goblin is supposed to send px or rc you can just flip that bit send that to the evaluator and you can again a simple calculation here which

shows that the evaluator would then run the e algorithm and end up with the wrong output gate that she's supposed to so you could flip an end gate to a nan gate here and again this might not seem like a big thing but you could end up like computing a different function that leaks more information than your desired function um wanted to leak. Note that everything that I've said um I have argued why it's not good enough to have that security but this doesn't technically violate the definition that I provided earlier where we assume both parties behave um honestly. So instead what we have to do here is we need to upgrade our definition of security itself to to allow for malicious behavior from the other party. So it's formalized as follows. Um in the real world we allow

the corrupt party which is the adversary to send arbitrary messages. Now um we don't require that the that Alice follows the rules of the protocol she can send arbitrary messages and we handle these messages in the protocol specification. So we might say that if Bob receives a rubbish message here, just oppose the protocol, right? And now security again says that um a simulator living in the ideal world should be able to simulate the view of a party in the real world. And notice the difference between the semi-honest definition and the malicious definition. Here we assume that both Alice and Bob hold the protocol. And then we say that their views be simul. So they shouldn't learn anything. In this case, we're saying

that even if Alice deviates from the protocol, we still um require her view to be simulable. So, she can't deviate from the protocol and learn something extra like we did in that selective failure attack in that she was able to learn something extra and we want to protect against attacks like that as well. The main takeaway here in malicious input protocol is maliciously secure. Then if an honest party follows the follows the specs so it follows the rules of the protocol runs the correct code they are guaranteed input privacy irrespective of the other other parties actions and this is a much stronger and perhaps more practical uh definition of security. So how do we achieve the stronger notion of security? Um I'm going to very briefly look at this in

the next 10 minutes. Um in gobble circuit specifically there's a framework called authenticated gobbling. What this does is it distributes that gobbling process between the evaluator and the gobbler so that no one can mess with the GC to like leak sensitive information. What I said the gobbler could do earlier he can't do that anymore. And then it also performs an authentication check afterward afterwards. So um you the bodies check that they actually did compute uh correct gates. So you can't flip an andgate to an orgate for example. Um this ends up like specifically addressing the two issues that I raised earlier. But you can then prove that these two steps actually um guarantee malicious security as well in the way that I defined it earlier

here. So let's look a bit let's look at these two steps in a bit more detail. Uh recall I said that earlier a gobbler in the semionis protocol could incorrectly gobble an gate um as an orgate for example and to protect against this we do a correctness check at the end of evaluation and now recall that point and permute technique that I introduced earlier. This is also where it comes in handy to know that optimization. In that technique, we had the evaluator holding masked values for each wire which is the internal value X or the permutation width that the gobbler holds. Right. Oh, um actually I flipped the order of who holds what here. The the mast value

should be held by the evaluator and the permutation bits should be held by the gobler. Sorry about that. Either way they end up with these simple this these simple exor shares of the underlying vio values for which we want to check that they satisfy the relationship without leaking those under underlying vio values right this is done in two steps you first authenticate these shared bits um I don't think we have time to get into how exactly the authentication works but um basically this means that there's now a mechanism to prove that you haven't tampered with bits at the end of the protocol you can prove that hey uh the bit that you agreed on using that's the correct that is the bit that I used in the protocol and then to test all of these gate relations you can just take one uh random linear combination of

these authentication tags and that's enough to verify correctness in a little bit more detail say that you want to check these uh two constraints specifically so you want to check that the value of uh V is equal to VA and VB and V is equal to VC X or V D based on the gates of the circuit so what you do is you first replace these bits in protocol. So throughout the protocol now instead of having a bit you have an authenticated bit. That's what I've denoted in the double angle brackets here and you use those um and then both parties sample these random values Kai 1 Kai 2 and they check this single relationship. If this relationship holds then over the randomness of Kai 1 Kai 2 with high probability the individual

gate relationships also hold. So your final correctness check just reduces to checking that one thing is an authenticated zero bit which is cheap to do. So that's the authentication after evaluation step and the other step is um distribute this uh distribute the generation of this GC. Recall that um in the the previous authentication check that I mentioned it happens after evaluation. So it still doesn't protect against the selective failure which can be an abort during the evaluation of the protocol.

Um this framework basically it it views gobbling as this function of randomly picked wire keys and permutation bits. And earlier these this randomness was known gobling is to hide these permutation bits from the gobbler. Instead you secretly share these permutation bits as well between the gobler and the evaluator and then they jointly generate the gobble circuit in a distributed manner. So there's a lot of details here that are interesting to work out, but skipping over them for right now. Um what this achieves is that now the gobbler even if he selectively gobbles certain rows without um he he gobbles certain rows incorrectly if the evaluator fails at any point if she is uh if she abotss on the third row

without knowing that permutation bit the gobbler can't uh deduce what underlying value this corresponded to. So quickly going back uh we had that selective failure attack which um which gives the gobbler information if he has his permutation bits which can unmask those masked values and he can use that to reveal the underlying wire value. So with with the secret shared bits this is not a concern anymore and that's the main uh purpose of au of distributing this gobling process. authenticated by GC also at a very high level it adopts this two-step framework to object to malicious security and specifically what we do here is that the gobler does not hold

the secret key for encryption anymore it's now secret shared between the two parties so that initial encryption that we had encrypt that seed um that's also done under MPC but again this is just um you only encrypt security parameter many bits this is independent of the actual circuit being computed um and then this leads to both parties is holding encryptions of some random seed. None of them see the random seed in the clear. Um, and they both use homorphic encryption now to expand that encrypted seal into these encrypted bits. The gobbler now does not know the permutation bits, right? Because those were um generated from the PRG. Instead, he also only holds permutions of the

permutation bits. But this is still um this still suffices for him to generate this GC and the correction bit. And the details of this you can find in the authenticated bit GC paper. So from here more or less it proceeds the same way. He'll use the encrypted bits. He'll uh compute the correction bit. Send over just the correction bit and the gobler and the evaluator will use that to fix the GC and then she'll use her input keys to decrypt. Again, there's also a correctness check at the end to make sure that the goblin didn't like flip any of those um bits that you were supposed to send. Um this follows the the same blueprint that I described earlier, except now instead of holding um exor shares of the m of the

underlying wire value, the bodies now hold encryptions of the underlying wire value. Again, by point and permute, the evaluator holds the mast value of intermediate wires in the clear, but she also holds encryptions of the permutation bits. So homorphically she can use that to obtain an encryption of the underlying vio value. She the parties want to check these relationships and they both hold encryptions of these valu vio values. Um I just said that the evaluator holds it. The gobler can also hold them with just one bit of communication by using similar masking on masking trips uh tricks. By the way, um this is why the authenticator protocol instead of using one bit of communication per gate, it

now uses two bits of communication. Still a lot better than 200. And now they want to check that uh they want to check these gate constraints. So that again checks to that reduces to checking that a single equation holds and that this um Kai 1 * this relation plus Kai2* this relationship is an encryption of zero. So the entire authentication check is just reduced to checking that a single cipher text cipherex decrypts to zero. Since they hold shares of uh the secret key, this also needs to be done under MPC but it's just a single check. So it's still cheap compared to the uh total cost of the GC and this turns out to be maliciously

secure and this is what BGC and authenticated bit GC give us. Um these are the works that I referenced in my talk and um I think we have some time for questions now. Thank you so much Nicole. Um yeah let's open it up for anyone who has any questions can please type them in the chat or raise your hand and speak up. So, uh, Nicole, do you have any idea about the the, um, the compute cost as far as homorphic encryption goes, like CPU

RAM? Um, I actually don't, um, it should be easy to get that number. I just don't happen to have that. We could look at that after this. Um but I will say that um the reason that I emphasize that this is also just constant homorphic operations per gate is that it's actually been known for a while that there are ways to um do the succinct goblin where your communication might it doesn't even have to be number of bits of the circuit. It can be like logarithmic in the circuit size but those are like really um computationally expensive. Those are like they they don't even intend to be practical. The point is that this protocol, it does intend to be practical. Um, but yeah,

it's a good idea to get a some kind of estimate of the exact computational cost. I'm not sure. And in terms of authentication, I'm just wondering generally is authentication are authentication protocols like sort of independent of the gargoying protocol? So you can use one authentication as a drop in replacement in something else? Are they kind of like is it kind of a Lego or is it something specific to a specific garbling protocol? That's a great question. So there are ways there is a blackbox compiler for goblin to make something from semi-honest to maliciously secure um that introduces a pretty large overhead. It introduces a multiplicative

overhead of a statistical security parameter which is like 40. So there's a way to make something uh make a gobling protocol that's semi-honest make it malicious with a 40x overhead in communication authenticated gobling this framework that I introduced. The idea is that in principle this can be done with like almost no overhead and unfortunately there's no blackbox way to do it for protocols right now. like every step that you're doing you're now replacing that generation process uh and you're you're distributing it between two parties and you're trying to see if you can still somehow do it in an efficient way. So uh to answer your question right now no it is there isn't like a drop into replacement but there is like a framework that um morally

speaking it has extended a bunch of different works and um when there's a new semi-onest protocol you would hope that adopting that authenticated goblings framework might get you a maliciously secure version for not too much extra cost. Thanks. Um, any questions from anyone? Andrew? Yeah, go ahead. Um, yeah, I was wondering about the um, uh, you mentioned that the the upfront communication cost the GSW ciphex. I think it is uh, it's quadratic in the size of the security parameter. Is that the which security parameter is

that the statistical or computational? Computational. Sure. everywhere that I use lambda I mean computational and I would uh we would set lambda to be 128 here. Gotcha. Gotcha. Okay. Yeah. I will say that this um bigo notation for the size of a GSW cipher test is definitely hiding a lot of constants here. Um so the exact concrete cost for this seed it's not yet known. This protocol has not yet been implemented. Gotcha.

Um, and I think I might have asked this before, but um, uh, do you know this is a a two-party uh, protocol in particular, right? Um, there's no general do we know about generalizable to end parties? Not known yet. Cool. Yeah, it's not known yet. There's no clear reason that um, it I mean in the paper there was no clear reason or clear difficulty expressed in extending it to multiple bodies. Um, right now we don't hold it. uh garbble circuits in general though um it is known how it's known how to extend them to multi-arty computational in a bunch of different ways uh both semi-honest and authenticated for this specific work it's not yet known

gota got you um I think I had another question but I forgot what it was yeah no worries whenever it comes back to you with that generalization Nicole do you expect the uh the pre-processing the size of these pre-processing uh artifacts to go up if you have multiple parties. Yeah. Um yeah. So one framework for doing it is where you in your gobble circuit itself you kind of extend that to hold um something that you authenticate from each party. So your gobble circuit size actually scales linearly in the number

of parties that you have and um in that setting I would expect the pre-processed cost to increase for like general protocols but maybe for this protocol since it's like completely independent of the circuit size um it's just a an encrypted seed and from that you can just like extract as many random bits as you want. Maybe it's independent, but I don't want to um I don't want to conjecture uh about something that I haven't looked into much. That's a good that's a good question though.

Um I remember what my question was. Yeah. So the I think I heard you mention uh I think I heard elsewhere as well maybe but I just want to clarify the the GSW cipher text the upfront communication stuff um that's reusable between like different circuits different sessions and everything so is there just like one fixed sequence and like that is the DSW cy text for that security parameter I guess. Yeah. So that's just an encrypted seed and then um that communication can be reused but um it would incur more communication um sorry that that

communication can be reused but it would incur more computational costs every time you want to run another session and generate more encrypted random bits but once you have this um cipher this seed exchanged from there you can um generate arbitrarily many um encrypted random bits. So yeah, that communication could be reused at this point in the sessions, but it's but it's specific to the two parties. Specific to the two parties, right? Yeah. Because I was wondering like can we, you know, for practical purposes, can we just like embed this cipher text in the in like in the software? Um, but that's so that wouldn't make sense, right? Because it's like the two parties have to come up

with this, do they? Yeah. Uh I mean definitely for the authenticated version they do. Um for the semi-honest version, I'm now thinking if uh that seed is known to one party and it's just like generated ahead of time and paid in uh Yeah, I want to say that um it's specific to the two parties, but this is

another thing that I'm going to make a note of to think about later. Okay, cool. Yeah, definitely the communication can be reused across multiple sessions though. Nice. Yeah. And importantly that can be done before you know the circuit you want to compute or um have your inputs for the function or just like have an upper bound on the size of the circuit and produce enough random encrypted bits. Wait, the size of the circuit is an input to the determines the size. Uh it doesn't determine size of

the cipher text. Um um all I'm saying is that you can do the uh the the computational cost of generating that many cipher uh generating those many encrypted random bits that can be done um the the computation of doing that that can be done before even knowing what circuit you want to compute. But the the communication of just the side for text yeah it doesn't even need an upper bound on the circuit size. Oh, so sorry. What was the the size of the circuit makes an impact on like the upper bound on the size of the circuit is the the upfront cost computation cost before the upront computation cost. Yeah. Gotcha. Gotcha.

Gotcha. Yeah. Yeah. No, that makes sense. Yeah. Yeah. Yeah. Because you're given a PRG, you can decide how many times you want to use it to generate more random bits, right? Yeah. That's analogous to, you know, in sort of regular gobling. Yeah. Or in authenticated gobling at least that you have the these triples that you prepare ahead of time. Yeah. Exactly. Exactly that. Gotcha. Cool. Yeah. All right. We are right on time. Nicole, this was fantastic. Thank you so much for your time.

Um, and uh, yeah, uh, for anyone who may have follow-up questions later on, uh, you can ask it on Discord. We're all there. So, thanks again, Nicole. And, uh, thanks everyone for being here. And, yeah, catch you guys later. Yeah. Thanks everyone. Hey Ali.

Hey, Nicole. Thank you so much. Let me just stop the recording. Yeah.