Incorporate multi-party computation and universally composable receipt-free voting. The authors are Joel Alvin, Rafaela Straski, Ansheng Zhu, and Vasily Dzikas, and Vasily will be giving the talk. Thank you, and thanks to everyone who stayed until this very last talk of crypto. I'm gonna try to keep it light. So, okay, the talk is gonna be split in two parts. The first part I'm gonna discuss universally composable definition of incoherible computation. And in the second part, I will discuss an instantiation, a multi-party protocol, which is using incoherible, and particularly this implies the first, use a secure receipt-free voting protocol. As you'll see, incoheribility and receipt-freeness, they go hand in hand, okay. So, very briefly, you already saw this slide in several versions, already in the script, I guess in this session. Security-full-to-party protocols is defined via the real, ideal paradigm. In the real world, we have the parties that execute their protocols, and there is an adversary that corrupts some party and uses them to cheat the other parties. And in the ideal world, the parties have access to a fully trusted party, functionality, that takes inputs from the parties. And so essentially, the parties just are dummy forwarders that take inputs from their environments, they give it the functionality, and the functionality just computes whatever they want to compute, and gives them the output. And the corrupted party is controlled by a simulator, whose goal is to make this ideal setting indistinguishable from the real setting for any such environment. So formally, we would require that for any adversary attacking the real protocol, there exists a simulator so that for every environment, those two things are indistinguishable. This was very brief, you've heard me. Okay, this is the standard notion that we all know and trust. And in this work, we're gonna augment it with a new beast, namely coercion. So we have corruption, we put coercion. What is coercion? First, how does it compare to corruption? When an adversary corrupts a party, what he does is he takes control of this party. So he just becomes this party and tries to cheat the other parties. In coercion, on the other hand, we don't have someone taking control of the coerced party, just an external entity goes and asks the coerced party to do something different than what it's supposed to do. And now the challenge of the coerced party is not to cheat its peers, but rather to deceive its coercer. So to give you an example, let's look at the prototypical scenario of incoercibility, which is voting, right? You have Don here, he goes to a voter and says, please vote for my nephew, A. Now the voter is really brave and he doesn't like A. So he goes in the booth and votes for B. And he's even more brave and he goes back and says, okay, I voted for A. But he can pull this off in case of a standard election because he does everything in the booth. There's no trail, but if this is an electronic voting protocol, then actually the transcript of the protocol is a proof of what he voted in most protocols. So if the boss doesn't say, okay, prove it to me, show me your transcript, then he's in trouble. So on a very, very high level, the goal of an incoercible protocol is to help this guy pull this trick off, right? And in the voting literature, this is called receipt-free-ness because it essentially means that this protocol that this guy's running has no actual receipt that the boss here can ask. Okay, so let's try to kind of make this intuition more formal. How can we define incoercibility? What does it mean that the protocol is incoercible? First attempt, a protocol is incoercible if the coercer cannot tell if the party is lying, right? This sounds really like a dream definition, but that's what it is, it's a dream. And the reason is that, okay, what if the party is a swing voter, right? What if the party deceiving just changes the outcome? And of course the coercer can catch him. That doesn't work, second attempt, okay. Let's assume he's not a swing voter, right? Obvious thing. Actually, this is a notion of incoercibility which is used in the concept of receipt re-voting. It has some meaning, but as cryptographers we know that it's just not about only this guy's input and output, right? The coercer might know more inputs of other guys and by that he can deduce whether the coerced party cheated or not. So the final attempt is we want that the coercer cannot tell that the coerced party is deceiving him by any other means than just using the output of the function that we are computing. And by this we get all the guarantees that we got in the previous attempts and much more. So this is actually the approach that has been taken in the literature for incoercibility for general functions, not just for voting, in a sequence of work by Canetti and Genaro in 96. That was the first one. Then later, Moran and Naor, Undre and Willequade and Canetti, Goldwasser and Poburiana very recently. So why are there so many attempts to define incoercibility? The reason is that the problem has many parameters that one needs to take into account. So there are questions of the type, okay, do coerced parties know who is corrupted so that they avoid them in their protocol? Do coerced parties know each other and can they coordinate to cheat their deceiver? So say that me and Rosario are both coerced. Can we go behind the back of the mafia boss and coordinate the way we're gonna cheat? I guess Rosario knows Italian, right? More about mafia than me. You'll need that, so. Another obvious question is standalone security versus usage security. Here, usage security is not just about composition. Of course, when you're usage secure, you get composition alongside any protocol or in any environment. But here the point is that in this case we can have a non-line coercer so the coercer can adapt his strategy depending on what happens in the protocol. And the final question is what type of coercion requests we allow? So do you want a protocol that just protects against the attack I described before? The attack where the party plays its protocol, he votes as he's supposed to and just needs to produce a receipt or do you want something which allows a more evasive coercion type like this so-called active coercion? I'm gonna say in the next couple of slides what I mean by passive and active. So first of all, what does it mean to coerce a machine, a Turing machine? Well, this is essentially telling to whoever is using the Turing machine to use another Turing machine. So a coercion corresponds to a transformation of the protocol of a party to another protocol which we'll call C. It's a mapping of protocols to coerce if you want protocol. So the case of semi-honest or passive coercion, this corresponds to the traditional receipt for in this notion from the voting literature, is a case where we have a coercer, in that case the coercer is the environment, that goes to the, so it does whatever the environment does, it gives the inputs to the party, the party runs its actual protocol, pi, but at any point the coercer might give it a special input which is show me your view or this would be the receipt that the boss would ask before and the party is supposed to produce his view. So the actual coercion request is replying by the view. So of course this is the weaker form, we can have a more evasive form where the actual coercer is online. So he just tells through the protocol to the party what he's supposed to do. So this should be your first message M1, the party does it, gets the first message from the protocol, then sends it to its coercer, second message and so on and so forth. Okay, so now a few words about what has been done so far in terms of definitions. So the first two definitions by Kaneti, Zennaro and Moran and Naor are not UC, they're in the standalone case. And the main difference is that CG is for passive coercion, like receipt-free-ness, and Moran and Naor is for active coercion. So the first work that put this in coercibility notion within UC was by Ondra and Willequade in Eurocrypt 2010. And they actually consider both active and passive coercion. They are, as I said in UC, the main issue is that they have a slightly counterintuitive side effect of the definition, which is that they implicitly assume that the coerced parties know who is corrupted. So in other words, the coercer cannot use the adversary as an informant to take up on coerced parties. And second, they implicitly allow coordination when several coerced parties are trying to deceive. The most recent work by Kaneti et al. considers passive corruption, but it's for the two-party case. It's not really clear how to extend it to the multi-party case. Of course, they are also in UC, and their protocol is two-party. Interesting, also the protocol suggested by the previous work is only a two-party protocol, and it's not clear how to extend it. So in this work, we consider both active and passive coercion in combination with active corruption, everything here. So the deceivers do not know who is adversarial. They cannot coordinate with each other, and we are in UC, multi-party, everything that we would like to have. Okay, so I promise I'm gonna try to keep it light, right? This is the kind of only heavy part of the talk, this slide, which unfortunately, as it's usually the case, is also the meat of it, so. Okay, so bear with me through this slide. What are we trying to capture with our definition? The intuition we're trying to capture is that the coercer should not be able to get any more information on whether the party that he's coercing is deceiving him, he's not running the coercer strategy. Then what he can deduce from the inputs and outputs. And we want that to be the case for any possible deceiving strategy that that party might be using. So what does it mean? It means that if we consider those two worlds, the top world, where the parties are actually running the protocol that the coercer requested, and the bottom world, where they're trying to deceive him, where they're trying to lie, then the distance between those two worlds is not much different than the distance between the effect that having these strategies has on the input and output behavior of the function. So in order to give the definition, I need to tell you what those four worlds are formally. The first one is easy, right? It's the actual word that we have when honest parties are running their protocol, coerced parties are running the strategies of the coercer requests, and coerced parties do whatever coerced parties do. Okay, so what is the effect of running this protocol? The easiest way to see what the effect is is to think just of the coercion as being semi-honest coercion. So this means that the party is running the protocol, and occasionally whenever the coercer asks, we'll produce a receipt that is running with the actual input of the coercer bonds. Well, just because this is actually the same protocol, what we get is that this world here is indistinguishable from the world where the actual functionality is evaluated. But now the difference is that these guys here might take an extra request to give a view. And this request cannot dealt with if the world, if those guys are dummy, then they will just forward it to the functionality. The functionality doesn't know what to do with this request. So what we do instead is whenever they get such a request, one of those extra messages, they forward this request to the simulator, and now the simulator is in charge of producing the receipt. So this is the top part. Now the bottom part is the part where the parties are lying. And the easiest of those two worlds is actually the effect of a lie. What is the effect of a lie in the implementation of a function? Okay, you can see the element part. So the effect of a lie is essentially changing my input and output. So it's a deception strategy. It's changing my interface to the functionality. This is a lie in the ideal setting. And a lie in the real setting is a translation of this to a protocol, right? So what our definition will require, and here comes the heaviest part, oh, okay, it went away, okay. So here comes the heaviest part, is that, so for whatever deception, whatever lie the parties wants to tell, there is a way to tell this lie, do this deception in the real protocol. In other words, there is a simulator such that for every such lie, there exists a realized that for every adversary, those worlds are indistinguishable and those worlds are indistinguishable, which will in particular mean that those distances are preserved. Okay, let's look at this definition for a while because that's not the most real thing. Okay, so there are several things. One is that you might notice that those deceiving strategies are vectors. This exactly captures the fact that deception is not coordinated. There is no central guy that defines what those guys are gonna do. Each of them is running a local transformation. So this means that deception is local. This example with Mirozari collaborating is excluded here. Second, the simulator comes before the deception. This means that the simulator is not aware of the lie that we're gonna say. If you were aware, then this top equation here would be meaningless. Because there is no deception in this top equation. And the third and equally important is the fact that the adversary comes after the deception, which means that the guys that try to deceive here have no idea who is corrupted. So we get all the properties that we would want. Very, very relevant. It's the same adversary in both those experiments. I don't require that there exists a similar of an adversary here and there exists another similar of an adversary here. It's the same through this entire four walls, which is what will allow us to preserve this distance. So hopefully I didn't lose many of you, but those that I did lose now can jump back on board because I'm gonna discuss the construction and the construction. You won't need to really understand the definition for understanding why this construction is incoherent. Okay. And to go back to a lighter version, let me make a first attempt. And so let me just, first of all, stick to semi-honest coercion, just to be set freeness. And let me make a first attempt to build an incoherent protocol from a standard setup that we're using in UC, a common reference stream. As I'm gonna show, we cannot do that. Why so? So what we have is our environment, who is also our coercer. And the party that is running the protocol, which should produce a receipt when requested. And we have also CRS, so the party takes the CRS. And I assume that at that point, the coercer issues a request for a receipt. This is a request for the entire view. The party needs to produce such a view. And what does this view include? It includes the value of the CRS. It has to include that because the coercer can check that from the corrupted parties. And all the random coins that he's gonna use, he hasn't used it, he can fake them, but he hasn't used them yet, so it doesn't make any difference to try and fake them. And knowing all this stuff and this guy's input, all the messages that he is supposed to send through the protocol are deterministically defined. So any way that he will try to deceive any deviation from this protocol means that he needs to send one of those deterministically defined messages differently. But if it happens that the receiver of this message is corrupted, then he is caught. And the probability of that happening is pretty high. It's at least one over any, even if one is corrupted. So the CRS is excluded. And this example exactly demonstrates the power of having informants that help the coercer. Okay, so it totally demonstrates that. It also shows what we need to assume in order to get in cursibility. We need to assume a setup that parties can lie about. They can, from the beginning, give something which then they can stick on. So, our solution uses something which has been used in actual implementation of voting, of electronic voting. And it's only generated hardware tokens. And they look like this. So the token has internally stored a key for every party. We have n parties that are n keys. And what it does is it computes an additive secret sharing of each of the keys. And authenticated additive secret sharing of each of the keys. So each share has authentication tag. And it gives to each party his share of each of those keys. And the authentication tag. This means that all those parties together hold all those keys. Any n minus one of those parties have no information. And there is no way they can lie about those keys because they are authenticated, okay? So, and the next mode that this token can be used is any party can query the token and the token will return with an input and the token will return an encryption with his key of that input. So this is the functionality that we need from our token. And now we can actually construct an incoherible UC secure protocol. And we're using the standard UC secure protocol. And the idea is if this is the function that we compute the parties first query the tokens. They get all their shares and authentication tags. And then they query the token. Every party queries the token on his own input and gets an encryption. And finally what they do is they pull on this information together into an NPC, traditional NPC. You can use CLOS there, your favorite UC protocol. And what the NPC does is it first reconstructs the keys. Then it uses the keys to decrypt the encryptions and outputs the function. So I won't go into many details but I will give you an intuition of why this construction is secure. Probably you already see the intuition. It's a very simple intuition. So first, because all the keys are authenticated there's no way that parties, even adversarial parties can lie about their keys. Hence the correct decryption keys which are also the encryption keys will be reconstructed. Hence this will be the only thing that the adversary can do is just give a fake YI but that's just choosing a different input essentially. And the output will be properly generated. And there is no privacy leak because those keys are never revealed in play. They are always put just in the NPC and everything happens under the hood of the NPC. So the reconstruction of the keys, all this stuff happened within the NPC. So no information on the keys leak. Now why is this incoherent to me? How can the adversary, how can a coerced party deceive its coercer? It just takes its favorite input and queries that to the token. And then as a receipt to its adversary he just generates a random message, right? What he gets from the token is an encryption. So the random message is indistinguishable and the only information that the adversary gets through the protocol is just the output and a view which is simulated because we're running close within this protocol. So this means that essentially he can just lie by simply querying another input, his favorite input and just generating a random receipt before he's queried to the token. You know, I mean, this is very high level, of course. There's a lot of things and tricks that need to be played in the actual proof. And if you're interested, please look at the paper. And in particular, a big difficulty is that we need to have the same adversary and simulator in both of those experiments. This is a hazard. But the good news is that this very simple protocol also tolerates active coerition. So even in the case where the adversary is over the shoulder of the party, still, this protocol works with a different analysis, though. Okay, so to conclude, what we saw here is a general universally composable notion of incoercibility, which is flexible. We can define different coercion types. And we also presented the first multiparty incoercible UC protocol, which in particular implies the first multiparty incoercible or receipt-free, as it's known, evoding protocol. And some open problems. Okay, so this is, of course, motivated by evoding. And another property which is very relevant in evoding is verifiability. Actually, there is no definition of composable verifiability, let alone a joint definition of verifiability and incoercibility. So this is something that we are actually working on. The second one, which is, in my opinion, also very interesting, is I argued before that the CRS is not sufficient for getting incoercibility. Our solution uses this, one might argue, very powerful hardware token. So the question is, where is the line? Could we characterize or actually could we find even weaker setups? Not just, not characterizes the end of the story. Can we find weaker setups in that one that are still sufficient for getting incoercibility? And there is a hope that we might be able to use IO there, because, again, the whole goal is that I can lie about what's in there. So, and with that, I would like to thank you and wish you a safe trip back. There is time for one question.


Okay, we're back live here at Strata Conference at Silicon Valley. We got eight minutes to feature a company that we like here. It's popped into theCUBE. Tim Morton from AccuNew. Okay, so thanks for coming in. I know we don't have a lot of time. Shake your hand there. We have another guest, but if the guest is late, we'll stay on, but want to get you some airtime. Tell us about what you guys are doing. Real time is a real big focus right now. We love real time, it's hard. A lot of people don't know what that means, so we'll talk about what your company is real quick and let's talk about the technical problem that you guys solve and the business value that it creates. Okay, great, we'll do. So I think real time has been a big focus of the conference here, and a lot of that is about making Hadoop faster. So we're not trying to make Hadoop faster. We always sit alongside. That's green fun, by the way. I think it's a number of vendors. So we focus on operational analytics and operational intelligence. So when seconds matter or minutes matter, where you're not trying to find a needle in a haystack, but where you're trying to expose the latest results from a particular set of metrics and live dashboards. So what we've done is build real time big data analytics as a framework on top of Apache Cassandra, and we'll be announcing a release for that next week. But that comes out of our experience of working with Cassandra customers where we were really seeing that they were struggling to deal with the data modeling and querying challenges and the inflexibility that that can lead to. So we've built an engine for helping people collect data from a range of different sources. We have Apache flume integration, message queue integration. You can set up the queries, which are basically like OLAP, real time OLAP queues. All that data. Cassandra's found a nice little niche, well not niche market, with real time, high transactional, mission critical value. Is that kind of what you're talking about? Yeah, indeed. Maybe last year I would have described it as a niche, but this year I think every Fortune 500 company we go to has active production Cassandra deployments, but many don't talk about them. And sometimes that's to do with Cassandra's great scale out and geo distribution capabilities, but often it's to do with real time analytics. What we're doing is we're making it much easier and faster and accelerating that process of delivering real time analytics on top of most SQL. Yeah, and we've also seen Cassandra also penetrate some of the storage paradigms with sands and using open source to actually move off proprietary drives into a much more cost effective, horizontally scalable environment. Okay, quick question for you is, what is the focus right now in terms of the open source business model for you guys? I mean, is it software? Is it all free? You guys make money on training and support in the usual ways, or you have a proprietary piece of code, or what's the business model for you guys? So the business model is as follows. So we maintain a distribution of Cassandra. Everything we do gets pushed back into open source Cassandra there. Analytics itself is a layer that sits on top of Cassandra. You can run it against vanilla Apache Cassandra. Analytics itself is closed source, but with open APIs. So let's talk about in-stream aggregation. So right now, the business models that everyone's going after, whether it's on the OLAP side or real time side is, the user experience is really critical. Intel talked about that specifically. Having the user input data is not the preferred method. Getting data out of the experiences algorithmically or automated way is a big focus. You guys look at that at all. Is Cassandra a good fit for that, or is there any specific use cases that you see in that area? So we work with customers who are doing social media analytics, who are collecting financial market data, who are collecting telemetry data in telcos and in manufacturing. And that machine-generated data, as well as human-generated data, the main sources of use that Acunu Analytics gets put to. What we found though is that traditional BI tools are not a good fit for helping people solve real-time monitoring problems. And neither are traditional monitoring tools. So we've ended up building a very configurable set of dashboards as a web-based tool that allows you to, that allows you to... I was looking for someone. Don't worry, I'm not on camera. So those dashboards allow you to get a lot of value out of the dataset very quickly and be able to understand its structure and understand how you can expose business insight from it. So let me take us through for the folks out there that are looking at the big data market who want to know in the Cassandra space that you guys are playing, what is the big enterprise value that you guys are seeing? And if you can rank that, is there a rank? And you can go, oh, one, two, three. Is there a way to stack rank that? In terms of the value propositions? Sure. So real-time insight, I think, is number one. So doing what you would traditionally have done in perhaps a transactional relational database or perhaps on a Hadoop system and actually moving that into a real-time framework where we're talking about data coming in and being available to make decisions on in seconds rather than in minutes or hours. Yeah, so let me ask you that question. So Cassandra has a lot of use cases of what I call in the new way. The old way is kind of data warehousing, business intelligence, monolithic systems. The new way is a little bit spread out, resource-based, horizontally scalable. And we saw some benchmarks from Green Plum saying that they're 100 times faster than Hadoop. A lot of questions on the benchmark, but that's kind of an old data warehousing model. So it's like, okay, Hadoop gets a nice little messaging there, and it's a lower cost data ware as a pre-existing market. How do you guys compare and contrast to those worlds? I mean, obviously you're in a different world. But that's moving over, so that data warehouse and business intelligence is now moving over into a new world. What's your point of view on that trend? Well, I think it's all very well-making, Hadoop, faster, but really that paradigm is about accelerating the needle in a haystack exploratory and analytics process. I'm going to ask you a question that I've not allowed you to see before, and I want you to find the answer to that and mine it from a very, very large set of data that's sitting there at rest. What we're working with is really allowing you to take these NoSQL technologies and embed insights into what things matter to you. If you're doing clickstream analysis, you know you care about users being retained between levels two and level three, and that fun is very important, and you need to be able to make decisions about how hard you make your social gaming in your time. It's critical infrastructure in the sense that it's matched to business process. Absolutely, so it allows you to codify that business insight into the analytics process. Yeah, and we're seeing that too, by the way. We're seeing that the instrumentation and the data collection is critical in this, if there was a book being written, and I'm sure guys are writing books now about process improvement around this new technology. So we're on the same page there, but I want to ask you with respect to codifying process, where are we in this? I mean, how early are we? How far along the track are we? I mean, you might argue we're early, early, or, you know. I think the early adopters have, I mean, I think the only.  Are we minus one? Are we two? Are we one and a half? So I think in the space, we're probably about three to four now. So the early adopters are having proven successes and are beginning to talk about those successes. I think the early mainstream are beginning to recognize what some of the early adopters have done and say, hey, I want a bit of this. I was talking to Billy Bosworth at Datastacks and we're talking about Cassandra and we did the Cassandra Summit Cube there and a great insight there. And Flash has been a real big enabler for Cassandra, given some of the latency issues around storage, storage architectures. But we talked about Cassandra, it gets kind of overshadowed by Hadoop from the hype side because Hadoop is, you know, Hadoop, right? So we kind of use the NASCAR analogy. It's like Cassandra's in the track and might slingshot around and take the front position soon in terms of recognition. Not there yet, but it's different. And I want to ask you this question because there's a point there is we're hearing that, we heard it stat earlier, one in five Hadoop projects make it to production of POCs. Cassandra seems a little bit more mature in the sense of in production. Do you see the same thing? And what's your comment on that? No, I agree. And if that was Billy's insight, I think that's very true. Cassandra, because traditionally it's been a relatively heavy weight process with perhaps slightly steeper barrier to entry and learning curve than other systems, actually once people commit to it, they find that you end up getting into production in a much larger number of cases than with perhaps an average Hadoop distribution. I would go back to the race analogy. I would say it's actually, you know, it's not a single race. We're looking to address different related, related but different problems here. Okay, Tim, last question. We got to get the hook, because our next guest is here. Thanks for coming on the queue. But final question is, what's your outlook for this marketplace? The collision of top down, bottom up, action between all the no sequel and sequel environments or unstructured and structured. What's your take on the forecast? I think the collision's inevitable. We've seen a bit of it today at the conference and with the Greenblum announcement, you know, enterprise data warehousing, unstructured data warehousing in the shape of Hadoop and no sequel databases are going to collide and merge together. But I don't know where that leaves customers in terms of their ability to understand what's happening in the marketplace. It's a tricky one. What is your take on the Greenblum announcement? I mean, just what's your point of view on it? Good, bad, medium? I think it's great. I think they have a lot of great complementary technologies and clearly a lot of talent inside the Greenblum organization to be able to deliver. You've got big money behind you with EMC. They have a lot of money behind them. I think they certainly have the ability to execute and deliver on that vision. I don't know to what extent the world needs yet another Hadoop distribution, but I think hopefully the potential competitive companies there will find a way to work together for the good of the user base. Tim Morton at CUNY, thanks for coming on theCUBE. We'll be right back with our next guest, Roger from O'Reilly. We're going to talk about applied big data in our next segment live here inside theCUBE at Strata. SiliconANGLE.com's exclusive coverage of O'Reilly's Strata conference in Silicon Valley. We'll be right back with our next guest.