
Video

Table of contents

Video
 Description
 Transcript
 Discussion
About the talk
About speakers
PhD student at University of Maryland College Park, Computer Science. Advised by Jonathan Katz. Interested in cryptography and distributed protocols.
View the profileIt looks like we're alive on YouTube. Hello everyone. Welcome to discussion on secure multiparty computation. This is the second of three sessions. I'll be one of the session chairs along with Auntie Tony as well. But we'll just get started with the first talk as usual. 5 minutes for the talk in 5 minutes for questions afterwards. So the first talk is always have a backup plan, fully secure synchronous and PC with asynchronous fall back. And chenda is going to give the talk. So whenever you're ready, take it away. So, can you see my screen?
Yes. Okay, and this is Jennifer from University of night. So they're sitting instead of security party computation or parties, want to drink, you compute the function of her private inputs. Without revealing, anything about the inputs just as if they had a plastic bag. So, a video probably NPC protocol can be classified according to the, underlined communication and modern, and perhaps the most popular one is a synchronous motor. This assumes that artists have access to synchronize clocks and everyone knows an Upward Bound from the network communication team.
While having these assumptions is very convenient, is might not be completely realistic. If the network delay is a dick. A much more realistic mortal is a synchronous motor. So here is to not make any assumptions on the synchrony of the plugs. They only use the fact that message is sent out eventually. So then one can ask, okay, then then, why do we care about synchronous? Having such security card? So synchronous, protocols, tolerate a high threshold for the dance. Show up to in half an artist compute, exactly the output that one would expect.
I'm on the other hand, a synchronous particles only. Get up to insert Corruptions and unavoidably the inputs of Park to tea. Parties are ignored. This means that part is to not really get F on the inputs, which would be the normal output. But that person is allowed to choose up to the inputs and substitute them by 84 value. See if you is that we can ask for. There is one single MPC particle, Tata chips, and a simple three Gins. And we would like, to have like high threshold for net worth, of course,
with input completeness. But even when the network is asynchronous, we would like to still be able to tolerate a reasonable amount of Corrections of the porcelain Wings. Do most people put sweet note. This is the question that we answer in this work. We say that. Yes, such an MPC exist. If and only if he has to TS mother turn on, the number of is not inputs, is at least two years into a synchronous trees. Security songs related work. There are some nice recent works by Bloom cats and lost that study, such questions for the case of agreement. Give me
tips for something for Speed machine application. And there are also some 18 journalist in PC. I believe this was the first one. I hear that a complete mess and I want the network is So, let's get an overview of our construction. So what we do is we rely on the court, which is basically, we enhance a synchronous MPC protocol. Not only keeps a current is that we would like to have when the network is synchronous, but also leaves a reasonable panties. From the network is asynchronous. Meaning that everybody gets an asynchronous output, which is allowed to ignore a bunch of inputs
or everyone of pains bottom. And on the way, we have to keep this is following the, the city an approach, which is based on. And once we have such a primitive is easy to guess how to get the NPC. We want with the first R&B singer nurse enhanced in peace. If, and if the output this photo and we're under a synchronous and asynchronous NPC practical because if it's from the first components, but even if the network is a synchronous either, everyone opens a y a output or happy or everyone opens put them in, which case is completely safe to
execute a synchronous. So far more information, I refer you to the full video presentation on or the food version of the paper. Thank you. So if you have any questions, please place them either here or how much overhead does the violation of the signals protocol? Do you have this extra property cost in terms of computation or communication? So we have to beat some more communication. So in fact, I might have some lights here. DC. The type C compared to CVN not that much. So so basically what we do is instead of broadcasting,
we we do hi sweet, we land on extra ACS protocol on this will include basically a song communication complexity in Carson and What's a perfume. Snow? No more questions questions. So you're the Primitive that you are using all the ways that the encryption. At least the Primitive that we rely on each other. Deeply on what we can creep. Fish falls. Okay. Thanks a lot more questions. Please. Feel free to ask Brenda offline. Now, we can move to the next talk.
The next dog is about stacked Garlin. Garbage truck with proportional to longest execution pass. From David, Keith and blond color is Nicole and David since giving the talk. So David you can start. So, I'm David Heath and I'll be presenting stuck babbling. Again. This is Joint work with my advisor blood collected off. That's so this work is about garbled circuits. So I'd like to briefly review the technique to Kabul. Turkish is a protocol between two players. If so called circuit generator in
evaluator and the circuit generators job is to build an encryption of a function represented to the circuit. And in this case will have her do so starting from a pseudorandom seat. So she built this encryption denoting M M is for what we refer to, as the material in the material. Contains a collection of encrypted truth, tables encoding, the semantics of the individual gates in the bullion circuit C. Now, after having constructed M. The generator sends em across the network to evaluator. And the key point is that this simple sending a picture Ariel from the generator to evaluator is
the single most expensive part of garbled circuits. And it is this cost that we decreasing this work. So you value it, or not husband material M. And he also obtained socalled input labels. So I won't describe how it gets these but these are our encryptions of The Logical, inputs to the Circuit, the input labels in the material are sufficient information for the evaluator to step through this circuit gate, by gate and eventually arrive at label sitting code, the circuit output communicate in order to jointly. Decrypt, the circuit output. Do this is garbled circuits. And in this
work, we extend garbled. Circuits to efficiently handle conditional branching that arises in the underlying program. So for example of this failsafe program that I have been here. In order to represent conditional programs. We need more than one circuit. In particular. We need one circuit for branch. So we'll consider these two circuits C1 and C2 and I'd like for you to imagine the case where, the circuit see, one is taken during the evaluation of his conditional Branch. The key point is that the circuit generator in evaluator should not know which of the, which of these two
branches are taken during the evaluation. Our approach approach is going to reduce the amount of information needed to represent the encryption of a conditional Branch without having to disclose to any of the players which branch has taken. Star approaches, it follows first instead of home having only one seed, we have one seed for branch. So the circuit generator constructs encryptions of each of the branches, in the conditional to get in this case drains M1 and M2. Now, the key point is that instead of sending M1 and M2 separately, as would normally be done. We instead send
their bitwise x, o r m, 1 + + 2 which is, of course, shorter than sending the two strings separately. So this bitwise X or is the source of our Improvement. The evaluator now has access to this exor and 1 + m to you and he also gained access to the seed that encrypts the non taken. Branch. Do. I won't explain how this is conveyed. Now, if we assume that the evaluator somehow dated know which branch was taken, then it would be relatively straightforward to see what he has to do. Because he can use this seed s 22RE. And Chris did not take a branch in calculate M2.
Given these two pieces of material, he can use bitwise xor to extract the material for the taking branch, and then evaluate his normal. Of course, the key problem is that the evaluator is not supposed to know which branch has taken in our approach. We resolve this by having the evaluators symmetrically attempt to evaluate both branches, but it's completely symmetrical. The evaluator uses the same seed to also encrypt the first circuit. This is not the old material and one but instead you'll see, a new String Band Won star different than the encryption built by the
generator. Therefore, when the evaluator attempts to extract the material M to buy bitwise exploring, he is unsuccessful. And what do you evaluate? He does not arrive at volatile, put labels, but instead arrives at random looking garbage, that is neither an encryption of 0 North 1. Now, if we could somehow eliminate this garbage, not interactively. And we would have evaluated this conditional, very efficient. To do this garbage collection, eliminate the garbage and propagate the valid labels. We add a few components first reality multiplexer Multiplex. His job is to handle
inputs on to the taken Branch. It propagates Valley inputs, such that C1 Valley, which is normal, but I'm a non taken Branch it. Places fixed garbage input keys that are independent of the, of the input. That's when they evaluate a run sister kit under encryption. He still arrives at garbage labels, but these labels are fixed. Our final observation is the generator, can place yourself in the shoes of the evaluator recompute these garbage out the labels. That is she can pre compute these pink keys. Knowing the pink keys and knowing about it. I'll put labels is sufficient
information to build a new encrypted truth table, which will obliviously collect garbage. So put together. Garland allows it to fitwize explore the material, from different conditional, branches, additional circuit gadgets that allows to collect the garbage put together stock car blowing offers a theoretical Improvement to garbled, circuit, ability to handle conditional branches. So, thank you and I'll take any questions. Alright. Thanks David. That's a some exciting work. If anyone has any questions, feel free to ask in either Azula for hear on Zoom will get those
relay to the speaker in the meantime. You're the very last thing you said is, this is a theoretical Improvement. Is it also a practical Improvement? Yes, so I'll refer you to our paper on ePrint, but we implemented this and I should emphasize that there is actually a computation overhead to doing this trick. In particular, with his generator, has to preach compute this garbage. So we increase the amount of computation needed compared to standard garbled circuits, but we show that depending on your hardware and foremost slower, now, it's very much. Well worth it to make this trade off
and the communication and prove it is worth it basically, so, yes, it's practically more efficient for most cases. Okay, excellent. Marcel is asking zulip is the number of interaction rounds, independent of the number of branches in the circuit. That's right. It's the property of garbled circuits. So there are no added on to communication. And I, I suppose you can Nest this little Gadget that you saw that you're showing on the screen. You can Nest it inside. So when are paper, we showed two construction zones. We still had a nest it, and then we also show how to sort of back to rise this.
So you can imagine that the multiplex for feeding and puts to not two circuits, but two 10, which turned out to be a computational a more efficient by a small amount. Okay, great. That is a possible. Great. We still have time with their more questions. Otherwise, I can keep asking questions all day. One of my questions was, it seems to work really? Well when there is a conditional branch in the circuit, but, you know, is there any hope of applying tricks like this for circuits, that you don't really naturally right
in terms of switching statements, like for example, the 80s circuit, you know, is there a way to apply your kind of ideas to make an unnatural example of a circuit? I'm not sure the key property that you need is is that there does need to be some sort of exclusive Behavior because as you can see on this light here we're completely we're getting off the ability to correctly evaluate the circuit C2. So if there is not some part of your circuit, which in
the end is not going to be evaluated. I don't see how you can apply this technique that said, you know, if it's not written in a highlevel language, perhaps they're always too kind of extract like bison. Compiler techniques to do switch parts of the circuit are exclusive with one another. But if in terms of like a, yes, it seems like a stretch because I think you need the output of all of The Advocates in order to compute the eventual output. Okay, except looks like more questions are appearing. Here will try to get to them quickly if we can online, Frank Davis is asking your
trading off, providing M1, and M2, as well as the seed because he's an ex, or if the x or value in the seed, is xor value and esteem shorter than simply giving and one of them to separately. Yes, so the seat is very short. You should think of this seat is, you know, 128, b or something. Where is the M1 and M2 are proportional to the number of what entry is proportional, in a multiplicative gates in each in the circuit times, the security perimeter. So the material is much much longer than the seeds and in fact, we show that you in our paper. We
don't even use additional fees. We just use, there's a wire, which is encoding, which branch has taken. And we just use that wire to perform the encryption. We use that as the seed. So the seed sort of comes completely for free. It's just material to cost anything. Okay, and maybe one last question cuz we're running out of time. I think this one has a short answer for cheek is asking what is the Assumption on the underlying Garlin scheme? The underlined portion of the ground case, right? So we used the underlying garbage. Can we formalize have to be socalled stackable and what
this means basically is that the encryption in the labels are indistinguishable from a random string. I'm so that's that's sort of the formal constraint that you can. There's a few other things but you can read that in our paper. But that's the main one. Is that the stuff that comes out of the circuit? Has to look random, basically. Okay, thank you for surviving. The barrage. Of questions. Is one more question. I see in the zoom chat. Maybe you can handle that if line, but I think it's time to move along. The next talk is
on better concrete security for half garbling in the multiinstance. Setting, I think shinkai is going to give the talk. So whenever you're ready, please go ahead and share your screen. I think you looks good. Hello, I'm think I'm presenting our papers at her concrete security is a multi instance. English story in this paper. We need to study the concrete coating for herpes, Carpeting and first attack on the current have casings in addition. To know, that's it. Doesn't mean that have this brokerage insecure that we do find a weakness when they have
functions during the hostage is not instantiated properly. And also, there is some previous papers, where they, there's a lack of concrete security. Normally, they only provide and also we gave her a new obstruction of hash function which can give you a better country security. And Thursday new review of the all Skylander games that y'all squabbles. Okay. See that's Marty completion for the Colts. It allows two parties turn to jointly compute function without revealing. Anything beyond salt, good. And it's usually represents of a function as a Boolean circuit with end and
Axle gate. And the hawk is Prosecco Interstate. Ozark Goblin King compatible with most other organizations for the half for the double turkey and efficiently computer and Kate with minimal communication. And also used to fix key is basically means that it's a function table using the GPS. And listen, when they touch functions, motorized vehicle type security reduction, but when we use my wrist and shades this, using the 60s, and there's a gap to exploit. I asked if the details of the attack and the give the results of our
nation, Are you our nasty taco seasoning. Roni X is okay. Oversee your the case of be lots of the label on the Steve's. The number on the gate in the circuit, explore multiinstance settings and bursaries may receive multiple staircase, Wichita, Independent League are old, and is he can be the total number of and agates the oldest turkey and the results showed that even if you use a label for the guy was, so it doesn't mean you have to be a security example, you use HD label with the circus title to the 40,
then it can be completely broken and including some words may presently in this in this conference and pulling our results. We asked me that we can break the circuits were using HD label under the sea. Is the 3267 Machine model. If we will only cost us $3,500 in spending money machines, we can simultaneously. So, how do we do this this? How do I fix this problem? Now, we already have done a half kids from school. And the first step is to design a new obstruction, which month was the use of hash function in the house gets broken again in that in the sense of this obstruction, which
is not a new heart function, which can which that's why I told us to 30 requirements for this abstraction as a provider battle concrete security. I hear all our results of the designs abstraction layer. We, we design the multiinstance, pickable circular correlational past touch function. It takes in Woodstock, Inn to label your dad. If you can receive few instances and this week. I can be reused for most New Times. And do you know, the kind of fermentation
and this is more than ideal Cipher. The key of these, I just have her, is this Twix pie and then two for the bouncer maximum reuse a single tweet, tweet star disciple Moran and point at knows that the previous 50 aspirin. It always starts from one, we started from Morant point. And design problem with the arrival of a new battery, new concrete Security box. And the instrumentation. So we make use of the hardware support and the some Kratom powder instructions to a salary operations, including various 128
scheduling. And the table shows the performance of the most of the Situation's net worth of the Network's next to the performance, is the same as the previous implementation network resources, enough 5% lower than before and the week after we publish the paper and no doubt almost the same. So in summary, we enhance the security and the Make little compromised only efficiency. 3 p.m. To empty to get Library. There's also links to the full version of the paper. Thank you.
Thanks a lot, Jen card. Okay, so there's a question from Mike but before actually can you give an intuition of the attack? Also, sorry, can you give an intuition of the attack and why you had to change? That has a function turns of updating cementation, words, they only provides the security and it's the Secret Agency created Bond. He's not enough instruction to use in, in the practice circus. I see two large, then this circuit can be completely broken. I think the motivation is that we have David which
can provide a new function which is more secure an impossible to use that. Excuse is as Okay. Yeah, it was just asking why you had to like me to that that has function that weekend. I can ask him afterwards. In the meantime. I can. You just ask you a question online. Sure. You hadn't attacked at the cost of his to the k. / C&C is the total size of the circuit. Does it have to be a single circuit or does it also work across many circuits? Because in half Gates, different circuits would have a
difference in a correlation, a different BX or Delta value. Does it still work in that case multiple staircase and the important things? No heat like the pretty major of the hash still only attacked while at a car to prequalify. Thanks. Okay, thanks. I don't drink no more questions than actually we're right on time to move on to the next talk. Thanks a lot. when next, we have, And who was going to talk to us about improved primitive, Skyrim PC, or fixed ice, Matic Banner Secrets,
Peter shop. So, you had a whole whenever you're ready, you can start. Okay. Thanks for the introduction. So there's going to be a quick overview and bought a book from just for a c u r s. So as we know if you see if you have to accomplish that means insect multiplications and the monster machine learning. We have motivation to have affection for the back and forth between the two demands by proposing Frameworks that. But they're usually either in the winter on the
story setting or in the semidarkness option setting security. Taking inspiration from them. We proposed a framework, which works and go to settings. But I'll perform steps in Washington, DC. Leaving from instrumentation. Inside your compassion for the cause. And although we support all Kirkland restaurants by the most pain in the security. Nvidia b, b proposal control protocol which might be of independent interest, it works by exploiting Tampa since properties of binary sockets. In front of me, being timid or construction and cement to an application benchmarks for each other better
than the paper, but I'd like to point out is that if he considered comparisons to 25 * best communication, and we have a 47 times higher than previous stateoftheart, which is a debit. I need a bit. Is an extender. It is. It consists of M. R. And B with a shared and their corresponding value are primary field or ring? 208, abbottsford generated internally with a large number of tablets and combined them to make a little bit to install a generator. And the advantage of being so is that we can do is cheat for TBS, multiplications over after work instead of
more expensive. As a result of this, if you can study as stupid. Norwegian Radio, b. Each body cell of a b is also known as the underlying values and we are at the music at the end. The country's protocol requires a few weeks as compared to the original one because that one was built for multiplication. Triple H have a linear relationship has have a nonlinear relationship. This means we need some information and the stairs. So then are you approach? Would be 200 S or triples
and using a process and its setup and use them for correctness? In the paper, we finalize this version of running shoes and prove that this doesn't give the adversity in Edition Advantage. So, this is the modified game which uses unreliable. Is Paris p. I a set of earbuds and require no triples? We shuffled amusing to public Communications. The Open Sea in a b and c Prime sets of final two triples and verify for greatness. If any of them filled then we aboard otherwise we take our many ones and place them into
buckets. And we got to go to baggage check protocol within his pocket with every other year a bit in the bucket using the tiny or triples pass them out, the door. As a verified private Arabic. So I'm leaving this game, has the following week. We found that we only have two open three ab and three sets of time if you have a bucket sets of three and we can regenerate it up. It's in the order of a million. This is a local studio version. Pensions game for multiplication tables, where we have to open security. As I mentioned, we
have informants to Compassion International using it a b. Are constructions work over signed and unsigned data types? give benchmarks some into an applications, like and the court is available as a part of the empty space. I'm just not conclude by saying these benchmarks. Then we're about three to five times better than tablets. If it comes to the number of comparisons in about five times better, if you can see where the communication cost for comparison. I was a quick overview of rabbits.
Okay. Thanks for Hulu. Anyone has questions, go ahead and ask them here. In the meantime. I had a question about your last slide where you showed some. Empirical improvements Improvement Factor, 2260 X. Are you just talking about the raw generation of? These is a tad bit sore, or do you have like a an application in mind where the ability to switch from? Arithmetic? The Boolean is like a killer feature considering all setting Oliver into an application. So I Believe by Protestant Christian and the other ones we benchmarked it snowed. Isis. Lester Holt. The whole
protocol has improved even offline and online phases. Okay. I also was wondering. How the conversion from from Boolean to and from arithmetic. Does that affect the round complexity? In online face. Dumb as opposed to using debit. You mean just in general? But the sure in comparison to the prior work as well. I don't have the numbers at the top of my head. Maybe one of the other colors can answer it online. Okay, and then I got the message out using couple seconds to get across and round. Okay. Thanks. I see a question
in the chat from how Jen does does this work improve truncation and comparison in a semi on a setting as well? Reminder 3 on a Saturday. I think we're about the Benchmark for concrete applications and match the performance of something like a b. Y g. I don't really remember the figures. First thing on a security door. This is Mom still here. If I can say briefly, it's not it doesn't really improve on ABCya free because said, you should like very specific tricks, but
it does improve far as I know, one other settings, like a show me a secret sharing because they're like, know that man didn't know that many special tricks. You can use this to me in secret sharing. Okay, great. And I think, I think, I think only also has a question that she can ask. So which conversion protocol you're improving Upon A B Y or which one? Are you competing against for these numbers? A comparison protocol paper by Katrina and Sebastian, the tank
Those are the ones. Okay, if you can face in the chats, I don't know. Okay, I don't I don't see any other questions cute up and where exactly at the end of time. So that's the end of the session. Thanks to all the speakers. I've seen in the other sessions. Everyone unmute same class so we can, we can do that. That's kind of fun. Thanks to all the speakers. Thanks everyone for asking questions. If you haven't gotten enough and PC, then stick around in 10 minutes. The next
Buy this talk
Ticket
Similar talks
Buy this video
Conference Cast
With ConferenceCast.tv, you get access to our library of the world's best conference talks.