Secure Multiparty Computation (MPC): Foundations & Challenges

[00:00:00][YUVAL ISHAI] Okay.

[00:00:00]Thank you, Sanjam, and thanks, organizer, for assembling such a great program.

[00:00:06]It's a real pleasure to be here.

[00:00:09]Okay, so I'm going to talk about secure multi-party computation.

[00:00:12]You know, most of you are familiar with the commonly used acronym, it's just too long, MPC.

[00:00:21]But somewhat oddly, MPC is used in the literature to denote everything, secure multi-party computation.

[00:00:27]And I don't know if you ever thought about this, but it seems that I'm always bothered by me, by it, and it always seems to me like a poor choice of acronym.

[00:00:35]But then I realized that there are two actually.

[00:00:38]This acronym has very important advantages.

[00:00:43]First, you know, if you ever realize that there is a bug in your security proof or no security proof at all-- --it puts you in a kind of a better legal situation.

[00:00:55]And the second point, which is actually a serious one you know, if you ever get to review a paper that contains a more appropriate acronym, like especially anonymous crypto submissions, right, that contain a more appropriate acronym, like SMC or SMPC, then you know it was written by pedantic authors who cannot be any of your friends-- --so the paper can be safely rejected.

[00:01:21]So maybe the first take-home message from this talk is that it's sometimes better to, to use a standard if a more inappropriate acronym than, uh-- Okay, anyway, I'm not going to change the acronym and I, I hope that somebody will ev-- uh uh, will, will take the initiative and change it, but I'm sticking with MPC.

[00:01:43]Okay, so I'm going to start with a gentle introduction to MPC, just to test the grounds.

[00:01:49]How many people here are not familiar with the basic notion?

[00:01:54]Okay, so-- --seems like almost everyone is familiar, and then you can use it as a way to introduce, to have a gentle introduction to MPC to other people.

[00:02:04]But anyway, I'll try to be q-- Uh, to be quick.

[00:02:07]I will try to give some idea of the breadth of definitions of the MPC some idea about protocols.

[00:02:19]I will talk about open problems and luckily for everyone, why we will never run out of them.

[00:02:29]And obviously, it's a very, you know big area and any such survey talk has to focus on a small selection of issues.

[00:02:41]I try to combine between giving some broad overview in some parts of the talk, and in other parts, focusing on things that are obviously biased by my own research.

[00:02:51]But please feel free to ask questions about everything, or to stop me or on any issue that you'd like to hear more about.

[00:03:00]Okay, so let me start with this claim.

[00:03:02]Please don't try to think about it too hard.

[00:03:04]It's circular.

[00:03:05]It might mess with your brain as in Amit's talk.

[00:03:07]So but really, you know, even those of us who are used to working on this problem often forget that you know, if we take this problem in its fullest generality, as has been defined in the literature, it can actually capture problems that don't, we don't think of them, like MPC, right?

[00:03:26]So error-correcting codes, you can cast it as an instance of MPC with a certain you know type of security.

[00:03:37]Distributed algorithms, right?

[00:03:38]It's like MPC without the secrecy requirement.

[00:03:41]Again, you can cast it as an instance of the general problem.

[00:03:44]Notions from complexity theory, like interactive proofs, PCPs, randomness extractors basic cryptographic primitives that we do not think of them as being MPC, can also be cast into this framework.

[00:03:58]So basically, anything that you can phrase as protecting good guys against bad guys this framework is general enough to capture it.

[00:04:06]Uh, so, so you know, if, if you kind of hate this area and you secretly wish that you know, it will vanish in a few years, then I have Yeah, I'm gonna have bad news for, for you.

[00:04:18]The government will bail it out, so.

[00:04:24][AUDIENCE MEMBER] You got it?

[00:04:24][YUVAL ISHAI] Yeah.

[00:04:25][AUDIENCE MEMBER] Can you give an example of something that's not MPC?

[00:04:29][YUVAL ISHAI] Oh, when we function?

[00:04:30]I don't know.

[00:04:30]I mean you, you can always generalize, but again, it is an attempt to generalize, especially people like Juan Corneti have been pushing this agenda that you can generalize in general.

[00:04:39]Of course, you can say the same about logic, right?

[00:04:41]It's not, uh-- So the fact that the language is general doesn't mean that you know, you need to think about it in this way, but it just means that we'll never, this is actually the answer to the last point in the previous slide.

[00:04:55]This is why we can never run out of problems.

[00:04:57]When we figure out all of these things you know completely, then we may run out of MPC questions.

[00:05:06]But because it's so broad and has so many highly non-trivial special cases that feed the entire communities we can never run out of open questions.

[00:05:16]That's one answer to this question.

[00:05:21]Okay, so in the rest of the talk, I will talk mainly focus on what most of us think about when we hear MPC, namely, the goal of securely evaluating a function.

[00:05:33]And let's again go quickly over this very simple two example, where let's say that we want to to figure out or actually six of us, because the picture only contains six parties want to figure out our average salary or equivalently, the sum of our salaries, or alternatively, you know, maybe more interesting here to figure out what is the average travel reimbursement we received from the Simons Institute.

[00:06:03]Okay, so, Yeah, So we want to compute, the sum of our, you know, secret, local inputs without revealing anything else, to each other, to the extent possible.

[00:06:20]So this is the simple, straightforward solution.

[00:06:23]Take someone we all love and trust, eh-- --Ki-- Kimme for those who don't know him, I hope this does not put me in trouble, but, uh-- Anyway, I'm not recorded, so, eh, and if I'm recorded, it will not v-- It will not be on the internet.

[00:06:36]And if it's, if it's on the internet, it's beyond the reach of North Korean hackers, so-- --I know I'm fine.

[00:06:43]Anyway, I love him seriously, so it's nothing.

[00:06:45](laughter) Jokes aside, he can really do it for us assuming that we all trust him.

[00:06:59]Okay, and the goal of MPC is to find a better way, if we don't have, here in the U.S., we don't have anyone who's as trustful.

[00:07:07]So, we need to find other ways.

[00:07:11]So let's assume, eh, thi-- this is updated, this is updated rec-- eh, moving to the Bay Area, but we-- L-- Let's assume that there is a-- By the w-- did, did anyone here receive a travel reimbursement of more than 10 billion dollars?

[00:07:23]You do?

[00:07:25]Okay, so we're fine.

[00:07:27]So let's assume that the answer is bounded by this capital M, and now from now on, all addition and subtraction operations are taken modulo M. Okay, So how do we do it, right?

[00:07:40]So I don't know, eh, I guess that even people who study or do research in MPC are not necessarily aware of the simp-- of these very simple examples, so here is this, eh, very simple, eh, old protocol, um, I believe it should be attributed to Chaum or it's kind of equivalent to, eh, what Chaum did.

[00:08:02]And, so the first guy, you know, picks a random number modulo M, which he uses to mask his input and send it to the second girl.

[00:08:21]So he sends a message, which is just his input plus R modulo M. She sends to the third guy this message plus her input and so on.

[00:08:31]Each party adds his or her input to whatever it received from the previous party.

[00:08:38]Now the last party receives the sum plus his original mask R, so he can just unmask by subtracting R from the result.

[00:08:48]Okay, so it's clear that we get the right result.

[00:08:51]What about, what can we say about the security of this protocol?

[00:08:54]All right, And I'm assuming that everybody's following the protocol, that there are no, eh, malicious parties here.

[00:09:00]So is this protocol secure against any single party?

[00:09:07]What do you think?

[00:09:11]So is there a single party that can learn anything except the sum of the inputs and whatever follows from his or her input?

[00:09:19]Yeah, so this protocol, in fact, right, so th-- this is how it ends, so this protocol, eh, actually is secure against any single party because every party, what it can see, except for the final message, if we look at some, eh, some party in the middle, then it just gets a completely random element of Zm.

[00:09:40]And, the last, the only message received by the first guy is the sum of all inputs, which is the output that we must reveal, plus the randomness that he picked, right?

[00:09:58]So clearly no information is revealed to anyone, any single party beyond the sum.

[00:10:03]But, if you look at, two colluding parties like the first and the third, they can easily, unmask, the second input, therefore compromising, completely compromising the privacy of this second party.

[00:10:19]Okay?

[00:10:19]And this is, you know, a simple example that's even useful.

[00:10:25]It's used, something similar is called DC-NET and is used, to implement anonymity.

[00:10:31]And, you can actually get around, it's easy to get around the previous insecurity by just using a more elaborate network, so, we just take a complete graph and direct the edges arbitrarily, so this is a tournament graph.

[00:10:50]Now every party, for each outgoing edge, it picks an independent random group element and sends it to the destination of this edge, okay?

[00:11:02]So this defines the entire communication in the first round, okay?

[00:11:06]We have n choose two, six choose two messages here.

[00:11:10]Now, what happens in the second round, each party does a local computation where he takes his own input, adds all the in-box, all the incoming messages, and subtracts all the outgoing messages, all of the out-box, okay?

[00:11:28]And this is what every party broadcasts to everyone, sends out to everyone, okay?

[00:11:33]So it's clear that if we take, so in the second message, in the second round, we have six messages.

[00:11:39]If we add them up, then every random mask will cancel out because it appears in exactly one in-box and one out-box, okay?

[00:11:47]And now you can analyze this and show that this protocol, assuming that everybody follows it, is indeed secure against any subset of parties, and more generally, you know, it's a nice exercise in linear algebra to show that, if you can use partial graphs and the combinatorial criterion is that whenever a set does not disconnect the rest of the graph, if you ignore the, the directions on the edges-, then the protocol is secure against this set of colluding parties.

[00:12:15]So you can use like expanded or sparse graphs to get good solutions to this problem.

[00:12:22]Okay, so more generally, now this immediately calls for the generalization, and I guess I should be very quick here because you know if somebody wants more details on anything, because this stuff really I believe that everyone understands, at least at the intuitive level.

[00:12:39]So we have K parties that want to compute some arbitrary function if of their inputs before it was a sum, a modular sum.

[00:12:47]Now it's a general function.

[00:12:50]We have a parameter T that measures how many parties can collude, and we want them to learn essentially nothing except the output.

[00:12:57]And we refer to this as a secure MPC protocol here.

[00:13:00]I got it wrong.

[00:13:01]It should be MPC protocol for F. Okay, so there are two types of questions one can ask.

[00:13:07]The first is, when can we at all do it?

[00:13:10]You know, at any cost.

[00:13:11]And the second is, how efficiently?

[00:13:13]If we can do it, then we want to understand how efficiently.

[00:13:18]So this is just a kind of a recap before defining anything formally.

[00:13:22]This is pretty much the same in almost every reasonable setting for secure computation.

[00:13:27]There are some exceptions, but this is pretty much the state-of-the-art, whether we're talking about passive or active attacks that I will define later.

[00:13:35]So in the '80s, we have, we had this these amazing feasibility results, and they showed us that if we want information-theoretic security like in the previous protocol, then we can do it in general if and only if we have an honest majority.

[00:13:54]So as long as we have less than K over two out of the K participants are corrupted, we think of them as being corrupted by an adversary.

[00:14:07]In the case of computational security, okay, which is of course the typical cryptographic relaxation of information-theoretic security we can get better results.

[00:14:22]We can get security in some sense at least under standard cryptographic assumptions for any T, so security against any strict subset of colluding parties.

[00:14:36]And as I said before, this is impossible in the standard information-theoretic model.

[00:14:43]I should mention that the standard information-theoretic model inc-- assumes the existence of secure point-to-point channels and possibly broadcast channel.

[00:14:51]So this is tight, right?

[00:14:54]We cannot get it with information-theoretic security, but there are several augmentations of the standard model that allow for information-theoretic security even when there is no honest majority.

[00:15:03]For instance, a popular extension is assuming the existence of oblivious transfer, another is the existence of some trusted setup phase that might be implemented using offline pre-processing given which the protocol can achieve information-theoretic security against an arbitrary number of parties.

[00:15:22]And just for those who don't know this oblivious transfer or it's referred to also as the OT hybrid model, assumes the availability of an ideal two-partic oracle between any pair of parties that can take a pair of strings from one party called the sender and a selection bit from a second party called the receiver and deliver only the selected string to the receiver without revealing anything else to the receiver or anything about the selection to the sender.

[00:15:51]Okay?

[00:15:51]This is what I mean by augmenting the standard model with oblivious transfer.

[00:15:57]We give this ideal oblivious transfer between any pair of parties.

[00:16:02]Okay, so again, this is still at the informal level.

[00:16:04]I'll get more formal later in the talk.

[00:16:08]As far as efficiency is concerned, the situation is more complex first because we have several different efficiency measures that sometimes are in tension with each other.

[00:16:19]We can refer to communication rounds, computation randomness, and known results are more sensitive to the exact flavor of security.

[00:16:30]Again, I will talk extensively about the flavors of security we have, but efficiency results tend to be more sensitive naturally to the type of security we require.

[00:16:40]It's a very active area of research.

[00:16:43]I should say that compared to other areas of crypto, it has a relatively small gap between the best, between those results we can prove under, even under standard, very standard assumptions versus the best solutions or the most efficient solutions we don't know how to break, right?

[00:17:05]This is heuristic efficiencies, is the efficiency of the best solutions we don't know how to break.

[00:17:09]In this area, we tend to have to kind of have the privilege of not having to deal with these situations where we have great solution, but we don't know how to prove it under any standard assumption.

[00:17:22]This happens less often than in most other areas of crypto.

[00:17:27]And perhaps in part for this reason, this area you know, it has a very, I think very strong synergy between the theory, I don't want to say practice because it's still not deployed, but there are really a lot of implementation efforts in actual companies that are selling these types of protocols.

[00:17:47]So this is now, and we'll hear about it in the next workshop, I believe there will be several talks that deal with actual implementations and concrete efficiency of MPC.

[00:17:56]So, you know, when I refer to efficiency in this talk again, this is a theory-oriented talk.

[00:18:01]I, I'm referring to asymptotics, but part of the motivation of even finding different ways or asking certain theory questions, right, that's a very broad thing, right?

[00:18:12]Why do we care?

[00:18:13]Why are we upset so much about, you know, two rounds versus three rounds or all these things?

[00:18:19]I think that part of the reason is that these challenges that are mostly theoretical challenges, they force us to think of new ways to solve problems and these new ways might yield an unexpected return and also help perhaps less directly, but help those who care about the practice.

[00:18:39]So again, I think that in this area, there is a very good match between theory and practice.

[00:18:45][AUDIENCE MEMBER] Yuval, is there any particular intuition why there should be a small gap between theoretic and [YUVAL ISHAI] Heuristic I think that, in part because a lot of, most of the results have a core which is information theoretic or almost information theoretic or maybe uses a one way function, and then on top of it, and you can make this the bottleneck.

[00:19:07]So in many cases, you can amortize the weight, the parts where we do have the gap between, proofs and heuristics.

[00:19:15]And in the domain, in the information theoretic domain, we have a tighter understanding or it, a better match between, not being able to attack something to find an actual break and being able to prove that it works.

[00:19:30]So I think this is maybe the high level reason.

[00:19:32]And again, it's not a universal truth, but I think it's true to a large extent.

[00:19:37]Yes.

[00:19:37][AUDIENCE MEMBER] This contradicts your, what you were saying at the beginning that the MPC is everything.

[00:19:45]It's everything.

[00:19:46]I'm serious.

[00:19:46]I mean, I [YUVAL ISHAI] Didn't say everything, I said just complexity theory and algorithms and, yeah.

[00:19:53]Like, not humanities as far as I know, but, uh-- [AUDIENCE MEMBER] I mean, the every most cryptography or pseudo-cryptography that doesn't have hypergraph.

[00:20:01]Yeah.

[00:20:03][YUVAL ISHAI] No, I agree.

[00:20:04]I, I-- What, what I'm referring here, I, I said I restricted myself to secure function evaluation and, eh, Yeah, you're, you're absolutely right.

[00:20:11]So there are certainly fragments of MPC to which this does not apply just because you can cast also those areas of-- very good point.

[00:20:18]What I'm saying mainly, eh, is about, eh, this, eh, whole, eh, business of implementing secure function evaluation, which is what, eh, mm-- and also, you know, it's about the type of, eh, constraints you're imposing, right?

[00:20:34]So in practice sometimes, say in theory, you want to minimize communication, but what practitioners will tell you communication is not the bottleneck, you need to minimize computation.

[00:20:44]But again, I may-- maybe I went a bit too far in this claim, but at least this is, this has been my experience in my research.

[00:20:51]There were very few things that, you know, I wanted them to be secure and I could not, you know-- --or they could not be proved to be secure.

[00:21:03]Relatively few things.

[00:21:04]It's just about mainly about my experience, but I think it also reflects on these implementation efforts.

[00:21:12]There are very few compromises people need to make, people who implement the MPC.

[00:21:17]You know, sometimes they resort to random workers, but this is to, just to get some kind of a minor improvements, not [AUDIENCE MEMBER] Very big ones, typically.

[00:21:27]Yuval?

[00:21:27]Yes.

[00:21:28]Can you give me an example of a heurist, like what is the best-- Is there a particular thing that you have in mind, like, eh-- [YUVAL ISHAI] No, I mean, if you look at the I.O., right?

[00:21:38]So you can make a heuristic leap of faith and assume that your I.O. is an ideal obfuscation, and now you can get, all the applica-- the beautiful applications that we heard about [AUDIENCE MEMBER] Previously.

[00:21:47]Anything in particular of secure function evaluation, like what do you consider, what are you considering as the best heuristic [YUVAL ISHAI] Algorithm?

[00:21:55]So I, I will mention, eh-- so, so again, ev-- every, every problem has its own heuristics, but I'm just, eh, sa-- saying this as a kind of a general claim that is consistent with what I know about most of the things I've done and things that people who implement protocols do.

[00:22:16]Okay, so, right.

[00:22:19]So, you know, I guess that I don't have to tell you about this RELIDEAL paradigm which has been a very powerful idea that probably originated from the seminal work on probabilistic encryption, and then zero knowledge, and then the first works on MPC, ending with the UC framework and this paradigm tells us that in order to define security, we don't try to enumerate a list of security properties, which is both tedious and incomplete.

[00:22:57]But instead, we just try to make the general statement that we have some ideal solution in mind, the one we are axiomatically happy with, namely it's a solution, the previous solution using Kim, right?

[00:23:12]That you send all inputs to the trusted party and he hands back all the outputs.

[00:23:17]This is the type of solution we're willing to live with, and now we want our actual distributed solution that does not involve a trusted party to be as secure.

[00:23:26]Or in other words, any attack that exists against the protocol has a matching attack that achieves something similar when attacking the ideal implementation.

[00:23:38]Okay?

[00:23:39]And by achieve, what I mean by achieve?

[00:23:41]Achieve contains two types of things.

[00:23:43]Also there are interactions between them, but essentially we're talking both about the secrecy of data, so learning about secrets of other parties, and also about correctness being able to influence.

[00:23:55]And this is relevant only when the attacker, the adversary is active.

[00:23:58]If it's passive, then we only care about secrecy.

[00:24:04]And this type of intuition can be captured formally via the notion of a simulator which again captures both secrecy or privacy, correctness, and also more subtle things like independence of inputs, right?

[00:24:16]We don't know, we don't want the inputs of the adversary to depend in some way on the inputs of the honest parties.

[00:24:30]Okay, so, when we want to formalize this, we have this adversary that attacks the real protocol.

[00:24:38]So the adversary just corrupts a set of parties and interacts with the honest parties.

[00:24:44]The honest parties also talk with each other, but the main point that they care about is the interaction between the adversary and the honest parties.

[00:24:51]By the way, do people know who this guy is?

[00:24:53]I guess that Israelis should, but this is a, a famous Israeli psycho-- a parapsychologist or someone who claims to have supernatural powers.

[00:25:07]And this is the skeptic, his arch-nemesis, who is basically claiming this is a simulator.

[00:25:15]What he's claiming is that there are all these hackers that brag that they can break everything they want to.

[00:25:23]So he says, "Okay, you know, whatever you achieve by breaking, by supposedly breaking the protocol, I can do in this ideal implementation."

[00:25:32]Right?

[00:25:33]So if you can figure out that the input of some honest party is bigger than seven, right?

[00:25:38]Maybe because the function allows us to compute the millionaire's problem, right?

[00:25:42]So you could do it also in the ideal model, right?

[00:25:44]So I can do it as well.

[00:25:46]But if you can bend the spoon, this is what-- this is his trademark, I can do it as well.

[00:25:51]You know, so the simulator basically is telling the adversary that he has no edge over what can be done by attacking the ideal implementation, right?

[00:26:01]And we also need to capture the influence of the adversary on the honest parties.

[00:26:05]It's not enough to look at, so if we only considered what the adversary-- so without loss of generality, we can just consider everything the adversary can see, right?

[00:26:14]So if we only require that this, what the adversary can see is the same or essentially the same as what the simulator can generate, right?

[00:26:25]The simulator doesn't see, it's very boring.

[00:26:27]The simulator's world is very boring, so he needs to make up for what he doesn't, the stuff he doesn't see.

[00:26:34]So if we only require that this is distributed, the same as this, then, this only captures the secrecy, right?

[00:26:42]What the adversary learns.

[00:26:43]If we want to also capture influence of the adversary, then we also need to look at the outputs of the honest parties in both of these games, and we need to consider these two distributions jointly.

[00:26:55]So we can look at correctness alone, so it's this equal to this-- eh, sorry, privacy alone, it's, this is distributed the same as this.

[00:27:01]Correctness alone is this is equal, is distributed the same as this.

[00:27:06]But the actual definition requires that the joint distribution of these two is the same as the joint distribution of these two, and this is strictly stronger than, you know, requiring separately both privacy and correctness.

[00:27:19]I mean, each of these notions alone is very problematic.

[00:27:22]It does not compose and so on.

[00:27:23]So, we really must consider the two things together.

[00:27:29]Okay And it's convenient to formalize this using this notion of an environment which serves as a kind of a referee to see whether, you know, they're really the same.

[00:27:39]And we say that the protocol is secure if no environment, the goal of the environment is to output a bit, and you know, the protocol is insecure if the environment can have a significant advantage in distinguishing between these two protocols, or these two interactions.

[00:27:56]And what the environment can do, it can pick inputs, you know, for the honest parties.

[00:28:06]It can interact with the adversary or the simulator.

[00:28:08]It does not know who it is interacting with, but its interaction with the honest parties is restricted to picking inputs and receiving outputs.

[00:28:14]And in the end, it outputs some bits, and we say that the protocol securely realizes F, if for every adversary there is a simulator such that no environment can distinguish between the left side and the right side.

[00:28:29]And we have an important distinction, eh, between the stand-alone case, again, I'm being here a bit, eh, simplistic, but, eh, one of the crucial differences between the stand-alone, eh, setting for MPC and the universally composable setting is that in the stand-alone case, the environment basically lets only active in the beginning and in the end.

[00:28:51]So in the beginning, it picks inputs and sends them to, you know, the honest parties and the adversary, and in the end, it takes outputs from the adversary or the simulator and the honest parties.

[00:29:02]In the UC setting, which we'll talk a bit more about later, the environment can interactively interrogate the adversary or the simulator in order to distinguish between them, and in particular, this enforces what is known as straight line simulation.

[00:29:19]Okay, so, eh, there's actually too many, you know, the-- now I'm going to get, eh, in more details about different variants of MPC, and there are actually more variants of MPC than we want.

[00:29:33]But the good news is that, most natural questions are not too sensitive to the distinction between these models.

[00:29:41]There are several important distinctions, but most of the distinctions are unimportant from the point of view of most natural questions.

[00:29:49]We have many different ways of, you know, transferring results from one model to another, and also the community has kind of converged to a small number of standard models, so it's not as if, you know, you can write a new paper for every combination of the parameters that I will specify next.

[00:30:08]Okay But, now I do want to give some, overview of the different variants of definitions of MPC.

[00:30:15]So when you want to define a concrete MPC model, you need to specify-- or a concrete MPC task rather than model, you need to specify a functionality which tells you what it is that you want to achieve, a network model that tells you, you know, how parties can talk to each other what the adversary can do, so this tells us how we're going to do it.

[00:30:38]Right, so the adversaries belongs to the adversaries, so you need to define what the adversary can do, who it can corrupt, how many parties it can corrupt, in what way it can corrupt parties, and we need to specify a security type which kind of quantifies in a way what level of protection we get, or what kind of protection we get.

[00:31:03]Okay, functionality, as I said, it captures the ideal goal and specifies a solution using a trusted party.

[00:31:11]Sometimes we put into the functionality also some inevitable vulnerabilities.

[00:31:15]Right?

[00:31:16]So it's not always exactly what we want.

[00:31:18]Sometimes we know we cannot get what we want, so we modify the functionality to get the next best thing which might be realizable.

[00:31:28]So typically, when people talk about secure function evaluation, they think about a non-reactive functionality, which is the mapping from a capable of inputs to a capable of outputs.

[00:31:39]There is also a more general case and very important and useful.

[00:31:44]For instance, if you want to capture commitment and similar primitives, you need to talk about reactive functionalities, which you can think of it as an actual algorithm that has state information and it can really interact with the parties in multiple rounds.

[00:31:57]For the case of non-reactive functionalities, which will be the focus of almost all of the talk there is a distinction between deterministic and randomized.

[00:32:06]There is a distinction between the case of a single output that is known to all or to one party, versus multiple outputs, which is the case denoted here.

[00:32:17]And the various standard ways of moving from, so if you have in the list there, if you have a protocol that works in the least general model, say, deterministic single output, you can easily extend it using standard techniques, perhaps with some loss of efficiency, but you can easily extend it to the most general model of reactive, randomized multiple outputs.

[00:32:40]So it's mainly for giving us a language to express the things we want in a better way.

[00:32:49]As I said we sometimes augment a functionality to capture some vulnerabilities we are willing to tolerate, either because we have to or because we don't know other, we need to write a paper.

[00:33:00]So for instance, a common relaxation is to allow the functionality to receive input from an adversary, so specifying some allowable influence or information that the adversary can learn beyond just the output of corrupted parties, which it can always learn.

[00:33:19]And let me stress that the question of, is it a good idea to compute this functionality securely is not an obvious one, because also in this ideal solution the adversary does learn information, right?

[00:33:33]If we compute the sum function and the adversary, you know, corrupts five out of the six people, then you can completely figure out how much travel support the poor guy is receiving.

[00:33:46]So so, so the question of which functionality is safe to compute is really out of scope for this talk and in general for the area of MPC, and this is precisely the scope of differential privacy which Cynthia will talk about tomorrow.

[00:34:01]So this is actually common misconception.

[00:34:03]People think that, yeah, if you apply MPC, then it makes security problems go away, and this is very far from being the case.

[00:34:11]Sometimes analyzing the security of solutions that involve a trusted party, that's really the main issue.

[00:34:17][AUDIENCE MEMBER] Yeah, you're right.

[00:34:19]A good example for that is encryption, that leaks the size or down in the size of the information, and-- Yes, [YUVAL ISHAI] Ver-- very good, yeah.

[00:34:29][AUDIENCE MEMBER] --there's big world attacks that use just-- [YUVAL ISHAI] Yeah.

[00:34:32]Very good, Yeah.

[00:34:33]This is really, you know perhaps the best example for why these things are useful.

[00:34:44]Okay, so network model, there is a distinction between synchronous and asynchronous.

[00:34:49]In the stand-alone model, most of the body of research works in the synchronous model.

[00:34:55]In the two-party case there is no issue so much.

[00:35:00]But in the multi-party case somehow the research of MPC has almost entirely converged in the stand-alone case to talk about synchronous communication.

[00:35:13]How realistic it is, I really don't know.

[00:35:15]I guess that reality is in between.

[00:35:17]The asynchronous model is too pessimistic.

[00:35:19]The synchronous model might be a bit optimistic, but I guess that you can use timing or other things to enforce or to approximate synchronous communication.

[00:35:29]There is a distinction between secure point-to-point channels versus open channels.

[00:35:33]In the information-theoretic setting, we always assume a secure point-to-point channels unless we allow more powerful stuff like oblivious transfer or correlated randomness.

[00:35:42]Authenticated versus unauthenticated communication, and we assume here that everything is authenticated.

[00:35:48]Full network versus partial network, and as I mentioned we have these helper functionalities like oblivious transfer, broadcast you know, a lot of work on crypto using in, or MPC using noisy channels, and something that's very, very important in the context of UC is something, some flavor of a CRS, common reference string or common random string that is needed for many applications.

[00:36:25]Okay, the adversary we need to specify something called an adversary structure which tells us which sets of parties the adversary can corrupt.

[00:36:34]We just look at the simple case of a threshold T of corrupted-- or number of corrupted parties, but in almost all cases, eh, these results can be generalized to more general types of adversary structures.

[00:36:48]There is a big distinction between the case of an honest majority versus no honest majority.

[00:36:53]Again, the information theoretic setting is really the main reason, but also in the computational setting, there are differences between what can be achieved in both cases.

[00:37:03]A big distinction is between the passive or also known as semi-honest adversary that follows the protocol.

[00:37:11]It's like a virus that doesn't want to be detected, so it doesn't modify the behavior of corrupted parties, but it does observe other information, versus active which can do anything.

[00:37:24]There's also some intermediate notions like honest looking and so on, but these are the main notions.

[00:37:29]And another important distinction is between assuming the adversary to be bounded, usually polynomial time, versus a completely unbounded adversary which can do any computation.

[00:37:41]Finally, there is a question of how corrupted parties are picked, so there is a static model where they need to be picked in advance before the protocol begins; the adaptive model which says that the adversary can dynamically corrupt the parties as long as it never corrupts more than T parties; and mobile model captures the situation where the adversary can move corrupted parties as long as at any point in time, at most T are corrupted.

[00:38:12]Okay, so security type, as I said, a big distinction between stand-alone and UC.

[00:38:18]Quality of simulators, so the distinction between stand-alone and UC is quite pervasive.

[00:38:24]I will not get to all of these details, but, essentially, the standard UC definitions today are quite long and the stand-alone definitions are quite concise.

[00:38:34]So the UC model, involves a lot of things which aim to capture very general situations.

[00:38:41]The quality of simulator can be perfect versus statistical versus computational.

[00:38:45]When I said that the environment cannot distinguish, I did not say, you know, how powerful is the environment and how much do these output bits can differ.

[00:38:54]So in the perfect case, the environment is unbounded and cannot distinguish at all.

[00:38:59]In the statistical case, it can have a negligible advantage in distinguishing and still it's, unbounded, and in the computational case, it's the usual notion of computational indistinguishability.

[00:39:12]Simulators: Simulator can also be bounded, unbounded or something is in between that is also useful, in some cases.

[00:39:21]Typically, for the purpose of this talk, simulators are always, roughly as efficient as adversaries.

[00:39:30]And, in terms of, output delivery, again, this is something that could be captured by, the functionality, by relaxing the functionality, but sometimes it's just convenient to specify the functionality in a simple way, so it's a mapping from K inputs to K outputs, and then when there is no honest majority, we cannot achieve this, notion of full security in general.

[00:39:55]Full security means that everybody receives the output, right?

[00:39:59]So in the case of an honest majority, even if we settle for computational security, there are these impossibility results that I'll mention later, and so there are all these relaxed notions.

[00:40:09]Fair security means that either everyone gets the output or nobody gets the output, so the adversary can basically, disrupt everything but then he doesn't learn anything.

[00:40:21]The kind of, standard notion, for, the stand-alone and also in a sense in the UC model is so-called security with abort, which means that the adversary can learn the output and then decide whether the correct output will be delivered to the honest parties or not, so it gives the adversary some unfair advantage.

[00:40:43]And there is some stronger notion which is security with identifiable abort which means that, in the event that the adversary decides to abort, it must sacrifice some corrupted party by revealing its identity to the honest parties.

[00:40:56]Actually, Vassilis will give a talk later today, eh, which will mention this notion.

[00:41:00]It's not as well known.

[00:41:05]Okay, so the setting of information-theoretic security, just to put it within this, previous, criteria, so we're talking about an unbounded adversary, important distinction between active and passive.

[00:41:18]We will assume an honest majority with point-to-point channels or a OT oracle or correlated randomness.

[00:41:26]In a sense, you can think of an OT oracle as a special type of correlated randomness.

[00:41:30]There are secure point-to-point channels and broadcast if we have, an active adversary, so there is, this boundary where we need to assume broadcast.

[00:41:41]We cannot get it information theoretically.

[00:41:43]If there are less than one-third of the parties are corrupted, then we can even realize broadcast using point-to-point channels.

[00:41:50]And the security is typically but not always, so people identify information-theoretic security or in general with unconditional security.

[00:41:58]This is not necessarily the case, so there are quite a few unconditional information-theoretic results which are conditional just because we cannot prove.

[00:42:07]I mean, it's not very common, but there are still quite a few such results.

[00:42:13]There might be, you know, if we manage to prove that there, you know, one-way functions exist, we might have unconditional computational results, but this is not very realistic at this point.

[00:42:24]And you know, one nice thing about talking about information-theoretic security is that it usually, again, not always but almost always, it also, these protocols tend to be universally composable and also adaptively secure.

[00:42:42]Okay?

[00:42:43]So th-- th-- there is, eh, so-- some work, eh, by, by, eh, Eyal Ta'alen-Yoda that-- that shows that in some special cases, you can actually prove that Information-Theoretic Security implies UC security, but it's not the case in general.

[00:42:56]But almost all natural protocols which are Information-Theoretic secure are also adaptively secure and UC secure.

[00:43:05]So that's a nice bonus for working in Information-Theoretic model, including the case where we have no honest majority.

[00:43:12]So if we have two-party protocols, use OT or correlated randomness, and they're natural, they will almost always be UC secure.

[00:43:20]Okay, composition is a major theme in MPC research.

[00:43:26]It's been really the topic of many, many, many works.

[00:43:30]I believe it was, eh, kind of pioneered by, by, eh, Ran Canetti, eh, th-- even though there were many earlier attempts.

[00:43:38]But today, only Ran survived basically, the last man standing.

[00:43:41]So, eh yeah, so there were actually e-- e-- a lot of, eh, earlier efforts, but today, eh, I think that the works of Ran on UC security are the most well known in the context of composition.

[00:43:55]So the goal of a composition or the composition theorem takes the following form.

[00:44:00]It says that if we have a protocol that can be proved, that we can prove that it is secure for f, but it needs to call some subroutine, some oracle g, right, which is an ideal functionality, right?

[00:44:14]So we have this physical implementation of ideal functionality, like an ideal subroutine which the protocol can call.

[00:44:20]And given this oracle, it can securely realize f.

[00:44:24]And now, we have some other implement-- an actual implementation of this functionality g by an actual protocol, okay?

[00:44:34]So this is pi of f given g.

[00:44:36]This is pi g.

[00:44:37]It securely realizes g.

[00:44:39]Then what is the natural thing to do?

[00:44:41]To take every oracle call in the first protocol and replace it by an execution of this, inner protocol for g, right?

[00:44:49]It's like taking a subroutine call and replacing it by the actual code of the subroutine.

[00:44:55]And we expect, right, this is true for subroutines, we expect, the result, to work, right, the protocol to be secure.

[00:45:03]Unfortunately, this is not always the case.

[00:45:07]But let me first explain, why this is such an important question.

[00:45:11]It has two types of motivation.

[00:45:13]First motivation is looking outwards.

[00:45:15]It ensures that if we prove that, you know, our protocol is secure under composition, it means that you can safely plug it in some higher level application and think of it as if, or analyze it as if, you have an ideal piece of hardware that computes this function, right?

[00:45:31]And this is much easier than getting into the internals of the protocol.

[00:45:37]And a different motivation which is actually not less important, even though, you know, maybe originally this was the main motivation for composition, I think that nowadays when people try to actually build a lot of protocols and they care about efficiency, it's becoming super important to design protocols in a modular way.

[00:45:54]And this is important for the same reason and more, that code is built in a modular way.

[00:46:00]So you can analyze different components separately.

[00:46:03]You can optimize each component separately.

[00:46:06]If you optimize one component, then all applications that use this component can benefit from this optimization, so it's really hard to overestimate the importance of this for protocol design.

[00:46:18]So in particular, something that's very useful is this is an example of this, is assuming an OT oracle.

[00:46:26]So you know, even though initially I motivated it as a way to get Information-Theoretic security, actually, nowadays, most of the implementations, they make extensive use of OT, so they think, they analyze their protocols in the OT hybrid model.

[00:46:41]And then they can plug in --Because of composition theorems, they can plug in some very efficient implementations of OT, right?

[00:46:48]So this is very useful and is actually being used in protocols that are being implemented.

[00:46:59]So the stand-alone definitions that, as I said, are much simpler, they can support some kind of composition, but this is sequential composition.

[00:47:06]It means that you cannot make these two subroutine calls concurrently.

[00:47:11]You need to make one, and then once it's done, once the execution completes, you can execute the other, which is good, but not in many cases, not good enough.

[00:47:22]And the UC model supports a general, concurrent composition.

[00:47:28]Unfortunately, we cannot realize UC security for many useful functionalities, or most useful functionalities.

[00:47:36]We cannot realize them UC securely without any kind of setup, and there has been a lot of work on understanding what types of relaxations are realizable.

[00:47:50]And as I said before, in the case where we have an honest majority, then we can realize UC security with no setup other than the existence of secure channels, which can also be realized UC securely using PKI or-- Okay, so let me just recap.

[00:48:10]Until now, I talked about feasibility.

[00:48:13]I defined diff-- I gave different definitional variants, and the feasibility question is can we realize, you know, a given functionality in a given model?

[00:48:23]So even though the high order bits have been settled, I guess, for quite a long time, there are many, many, many remaining questions, and I will just give some examples of popular lines of research.

[00:48:37]There are many other lines of research that talk about the feasibility in, in certain, eh, maybe less studied MPC models.

[00:48:45]Type of very popular recent line of research is this revisiting the fairness question.

[00:48:50]So there is this classical result of Clive that says that we cannot do coin tossing and as a result, say we cannot compute XOR of two bits fairly.

[00:49:00]And this created the misconception that you know almost nothing can be done fairly or that very few useful things can be computed fairly.

[00:49:12]And and the breakthrough work of Gordon et al.

[00:49:16]initiated the line of research that attempted to, to understand which functionalities can be realized fairly without an honest majority.

[00:49:27]So now we're at a s-- at a state, this is, this is um, just a recent TCC paper by by Gilad, Amos et al.

[00:49:37]And this paper gives a full characterization for the case of two-party deterministic functionalities that output a single bit to the same bit to two parties.

[00:49:49]So that's a special of special of special case, which took a lot of effort to figure out.

[00:49:54]Can [MANOJ] You say that again?

[00:49:55][YUVAL ISHAI] Yeah.

[00:49:56]So, it's two-party functionalities that are deterministic.

[00:50:00]They output a single bit and the same bit is output to the two parties.

[00:50:04]So this case and they're finite, right?

[00:50:06]They have you view the constant size input.

[00:50:09]So this case has been solved recently.

[00:50:13]Okay, still you know, tons of other cases.

[00:50:20]We are in a somewhat similar, a bit better situation in terms of understanding which functionalities can be computed with information theoretic security.

[00:50:30]Actually, this is a line of research that was initiated by by Eyal.

[00:50:36]And uh, so here, sorry Eyal, this was before Joe.

[00:50:42]Eyal and Beaver actually had the first works on characterizing the two-party case.

[00:50:47]And there has been really also a large body of work trying to complete this characterization and the latest is work people in the audience here Maji, Manoj and Amit who completed this characterization for the case of finite non-reactive functionalities.

[00:51:11]Right?

[00:51:12]So you increase finite, meaning that the domain size you view it as constant, you increase the domain size, And again, these are not just hypothetical questions.

[00:51:20]So for instance, let me ask the following question.

[00:51:24]Can you design a small hardware token given which you can get information theoretic obfuscation, right?

[00:51:31]So you can cast this as an instance of the general question or, you know, you can, you can the whole lines of work, say on crypto based on hardware tokens, that if we had these general characterization for functionalities that are big, then these things would follow as special cases.

[00:51:46]But our theory is not nearly developed enough to capture all these useful cases beyond what we know and even this is quite hairy.

[00:51:55]So this is really summarizes-- Tal has been involved here as well and I guess that other people in the audience.

[00:52:04]Composable security again, a whole li-- line of you know uh, Rafael here Amit Manoj have been involved in lots of works on trying to find creative new ways for getting around the impossibility results.

[00:52:23]Um, and Yeah, So I, I will not say abou-- a lot about it, but I'm sure we will hear about it in later talks both in this workshop and in the next one.

[00:52:38]One last thing I want to mention.

[00:52:39]So I think that one of the challenges, this is not really an open, well-defined open question, but I think that the main issue, at least I'm having with UC security, I mean, it's, it's a great notion and we want everything to be analyzed in this framework, but it's too complex.

[00:52:58]I mean, if you try to tell, you know, a mathematician tells you, "You know, you have a theorem, right, claiming this protocol UC secure.

[00:53:04]Please write down the complete statement of the theorem."

[00:53:07]You cannot do it.

[00:53:08]You can refer to pages and pages of definitions that refer to each other.

[00:53:13]So there has been a, so there is an upcoming uh, crypto paper by Canetti et al.

[00:53:20]That proposes some simpler version of the UC model which captures, It, it's more restricted in scope than the general UC model.

[00:53:29]It's in a good direction, but at least skimming it, I feel that it still leaves a lot to be desired.

[00:53:34]So I think that Uli Maurer has some ideas in how to do it right.

[00:53:38]I think that really this is an important endeavor to get a version of the UC framework that captures the essence.

[00:53:46]Maybe it's not general enough to capture all real life situations, but it's enough to capture the essence and eliminate all the noise, right?

[00:53:54]A lot of what is done in UC proofs is noise.

[00:53:58]It doesn't have to do with the essence.

[00:53:59]Yes?

[00:54:00][AUDIENCE MEMBER] Is the standalone model a lot easier or is it just no one tried to formalize it [YUVAL ISHAI] No, no.

[00:54:04]Standalone model, you can write a self-contained definition in a few lines.

[00:54:08]I mean, you can look at Goldweiss' book.

[00:54:10]I mean, it's standalone definitions are very easy.

[00:54:16][AUDIENCE MEMBER] You can, Even if you talk about just self-composability, it's very easy.

[00:54:20][YUVAL ISHAI] Yeah.

[00:54:20]But [AUDIENCE MEMBER] Only when you move to general compositing [YUVAL ISHAI] It's very easy.

[00:54:23]Yeah.

[00:54:25]So I'm saying that in the, in the, um-- Again, many of these things are, are just a matter of taste or choice whether to be general or be succinct, but those who favor succinctness right now don't have a really good way of even stating results in the UC model.

[00:54:41]And this, I think, should be done.

[00:54:45][AUDIENCE MEMBER] So you a-- uh, just a minu-- you mentioned obfuscation, I'm just curious, do we have any composition theorem for obfuscation?

[00:54:50]You can obfuscate little piece, you can obfuscate big piece, but except for this oracle calls?

[00:54:54][YUVAL ISHAI] So again, as Amit said, if you look at even VBB, it's problematic, but if you consider ideal obfuscation, just as an ideal functionality, then composition is trivial.

[00:55:03]No, and I think that my response, if you want to take the current IO candidates and use them, suppose they were practical, so you could just assume this is an ideal obfuscation, as opposed to VBB obfuscation, and then you don't have to deal with, I mean, again, it's not an ideal obfuscation, but you make the leap of faith, you analyze the protocols as if it's ideal obfuscation, and then you don't need to deal with composition issues for obfuscation.

[00:55:28][AUDIENCE MEMBER] Yeah.

[00:55:28]Would it be a good design to design, like, big obfuscated programs?

[00:55:31]If you obfuscate little pieces and some co-- glue them, or that seems kind of compli-- I mean, that doesn't seem like it should work.

[00:55:36]I [YUVAL ISHAI] Mean, you, you, you should refer the, the question to those who understand the obfuscation more than me, but, but I mean, ju-- just taking Amit's word, I think that there is no good theory of composable obfuscation.

[00:55:50]Right, [MANOJ] Amit?

[00:55:52]We do have some, Oh, [YUVAL ISHAI] So Mano-- Yeah, So Manoj you, you will talk about it in the-- [MANOJ] In the next workshop.

[00:55:58][YUVAL ISHAI] Okay, very good.

[00:56:00]So.

[00:56:01][MANOJ]?

[00:56:03][YUVAL ISHAI] Right, and Finally yeah, I guess that this will be a good time to take a break, right?

[00:56:12]How much, when is my hour over, in-- [AUDIENCE MEMBER] In a few more minutes.

[00:56:15][YUVAL ISHAI] In a few more minutes.

[00:56:16]Okay, good.

[00:56:16]So I'll continue a bit.

[00:56:18]So, finding new ways for deriving feasibility results.

[00:56:21]So, the second part of my talk will be mostly about showing different ways to get feasibility results.

[00:56:26]Why do we need to get yet more ways?

[00:56:29]And two reasons.

[00:56:30]One is sometimes what we have is not simple enough, right?

[00:56:33]If you look at the textbook, like definition, it's a textbook proof of the GMW protocol from, say, Goldweck's book, it's still n-- not n-- not short and not elegant, so it's not something you really believe is the right-- I mean, the intuition is always very clear and simple.

[00:56:54]We have good intuition in mind, but for some of the protocols but there is a gap between how simple we feel this should be and how simple it really is when you need to write down the protocols and the proofs.

[00:57:08]So, finding new ways and simple ways could potentially make things better, but also, this relates to a point I made before, when we look at efficiency, then finding, being forced to find new ways, they will always be better in some settings.

[00:57:23]So whenever you have a different solution to a problem, there will always be a setting where this different solution will win and give you better things.

[00:57:32]So I think that nowadays, the interest in the practical efficiency of MPC also further motivates finding new ways to solve old problems.

[00:57:41]Okay, so let's take a break.

[00:57:42](applause)