Hi, and thank you for inviting me to speak at the NTT Research Summit. And congratulations for NTT for setting up the new research hub in the Bay Area. Okay, so I’m going to talk about fully bi-deniable encryption and multi-party computation. And this is a joint work with Sunoo Park from Harvard and Oxana Poburinnaya. She’s actually right now in Rochester University.

So consider these two kids, which maybe some of you still remember. It’s Violet Parr and Jack Jack, the Incredibles kids. And they want to talk to each other privately without their mother knowing what they are talking about. So here they are using this lead pipe, which is like an ideally secure channel. And Violet can say to Jack Jack that she doesn’t want to do her homework and she actually wants to watch a movie. And she knows that Jack Jack will understand what she says, will hear what she says. But their mother is not going to learn anything because it’s in this lead pipe. She doesn’t know what they’re talking about. And we know how to implement this actually without lead pipes in software with the idea of encryption which, you know, we know for the last 40 years or so, but actually for many more.

So this is great encryption, it gives us a private communication against eavesdropping adversaries, so passive adversaries. But we know that mothers can be more than passive, so what if the mother actually goes and asks Violet actually, “What did you talk [about], what did you say to Jack Jack?” So, if Violet really used this lead pipe, she can say whatever she wants. She can say, “I actually said that I was studying.” And then the mother goes to Jack Jack and asks him “What did Violet tell you?” And he says, “Oh, she said that she was studying.” And the mother still cannot tell anything about what happened. She doesn’t know if really that’s what was said or not. In fact, even if Violet said that she was studying and Jack Jack said something else, that “She said she’d rather watch a movie,” even then the mother doesn’t know who was right.

I mean, not from the lead pipe. Maybe she can look them in the eye and know this way, but not from the communication, she doesn’t know. And, in fact, it can go on like this and, the lead pipe doesn’t help at all to understand what really happened. And this is really another very important form of this really secure channel, that it doesn’t allow external parties or coercers to be certain what’s really happened, even when they ask to see all the internals of all the parties. In fact, even further, Violet and Jack Jack have no way to actually convince the mother that this is what happened, even if they want to, right? They have no way of actually proving to the mother that they said this and not the other thing with this lead pipe.

So the question is can we obtain similar effects with software encryption. So, again, we have an encryption scheme that has the same sort of properties. So we know that, a priori, normal encryption doesn’t have these properties, that encryption leaves traces, so there is the ciphertext that the mother or the coercer sees, and then when the mother goes to the parties to validate the chat, she can ask them, “Give me, show me your randomness, show me all your internals. I want to see how you generated the ciphertext and how you decrypted it.” With normal encryption, there’s only one way that Violet and Jack Jack can open this ciphertext, and therefore there is no real privacy any more.

So, this is the case. So really to address this issue, there is this concept of deniable encryption that was considered, many years ago. And the idea here is that you want an encryption scheme that provides protection of privacy, an ability to keep private your real value and maybe fake or lie about what you say in a convincing way, even against such a coercer. So the idea is that, you think of three types here.

So there is sender-deniable. So we just go and ask the sender of the message, “How did you encrypt the message? Show me your encryption analysis,” assuming the decryption-key is public.

And if you go to the receiver and ask him, “Show me your decryption key, I want to see how you decrypt it.”

And you can also think about the natural case where the coercer actually goes to both parties, and asks them for the details and compares one against the other, right?

So this is the bi-deniability concept. And you can, of course, naturally generalize it not just to encryption, to, say, two-party computations. Assume here Violet and Jack Jack, they maybe do not even trust each other fully, but they want to compute together. Or do they actually know a kid that they both know and vapes in school, right? So Violet has her own list of kids that she knows vapes and Jack Jack does too, and they want to do this two-party secure computation to figure out if there’s a kid they both know.

So if they have this ideal trusted party or, say, for somewhere where they can actually do the secure computations securely, then they can, of course, learn the answer without learning anything else. And also if the mother comes in after the fact, and asks them, you know, “Oh, I see that you were trying to figure out who vapes in school, so tell me what you did. Tell me your inputs, tell me your outputs, give me all of your randomness, and I want to know who are the kids that you know that vape in school.” So if they were using such a physically insecure gadget then they can say, you know… So Violet can say, “I don’t know anybody that vapes and Jack doesn’t either. And I got nothing. Input nothing, got nothing.” And Jack Jack can say the same.

And of course the mother has no way of knowing if this is true or not. And even if Jack Jack decides to tell the truth and actually tells his real input and real output and real randomness. No randomness here. And Violet tells still zero, nothing, nothing. That the mother has no way of knowing which one is lying. Clearly one of them is lying, but she doesn’t know which one. I mean, she can again look them deep in the eye, but not from the communication, she cannot figure out. So we want to get something like that for two-party computation. So, again, in the case that one is lying, one is telling the truth, we still don’t know.

So the question, is there a protocol that everyone has this behavior and furthermore how to even define this? One further thing to think about, this doesn’t, shouldn’t end with two parties. You can think about three or more parties. And the same thing happens. You know, just maybe the trust structure or the consistency structure becomes more complicated. You know, you can make groups of people which are consistent with each other and not with others.

Okay, so, what are our results here? So our first result is regarding encryption. So we come up with the first bi-deniable communication protocol. It’s not encryption, because there’s three messages. So it is three messages, and we need our reference string, which is like programs in the sky. But it’s a short reference string, one short set of programs that everybody in the world uses for all the encryptions for the entire duration of time. And our assumptions are subexponential iO and one-way functions. But just to say that what was done previously, it was just sender-deniable or receiver-deniable. And then another thing that we do is to actually, we define and also obtain this extra property which we call off-the-record deniability, which talks really about the case where, as I said before, that one party is saying one thing and the other party is saying another thing, and they’re inconsistent. So they cannot, there is no way for them to frame each other.

And the other result is regarding multi-party function evaluation. And here we come up with the first all-deniable secure function evaluation protocol. So by all-deniable, I mean that the protocol where the adversary or the coercer expects to see all of the transcripts of the computation, including all the randomness and all the internal states of all the parties. Right, so previous results of this area always assume that, you know, either the coercer only can coerce only some of the parties, or if you can coerce all the parties and there is some physical gadget which has crucial information about the inputs and outputs and, nobody can see inside.

So, now, here, we actually let the attacker see everything, or at least they think they see everything. And we can still provide deniability. And our protocols also withstand inconsistencies. In the case of this off-the-record style, one party says one thing, the other party says another thing. But this is only in the case of two parties and only for functions where the input size is polynomial, input-size domain. So this is actually an interesting open question, how to extend it beyond that.

So, just to say that this is kind of, it’s a surprising thing that you can even do such a thing. Because what it allows you to do is actually essentially completely rewrite history. So you’re doing a computation, and then somebody comes in asking, “Show me everything that’s happened, all of the randomness, all the entire transcripts of the computation from beginning to the end.” And you can now tell them something else, not something that really happened. I mean, they see it, the public messages, they see it, this is uncontestable. But you can show different internals that are very different than what really happened, and still nobody can catch it. So it’s really, in some sense, you know, who knows what’s really happened? So, this is the results. Let’s just say a few words about fully deniable encryption, just to give a bit more details.

So, how did you find this fully deniable encryption? So, first I want to say that, you know, if the parties have a pre-shared key, then deniability is really easy, because, well, in order to encrypt a message you just want some private-public key, and this one-time pad is completely deniable, right? Because you can just take the ciphertext and claim that it was any message, encryption of any message of your choice, by just XOR-ing, by just coming up with the key, which is the XOR for the ciphertext as a message of your choice. So this is completely deniable by both parties. And even if it’s off-the-record because if the two parties say different things, there’s no way to know who was right.

But it means that, the hard part is actually how to come up with this shared key in a deniable way, so that you can actually later argue that this key was m. So then you can have a deniable key exchange. And this is what we do. So we come up with this idea of a divided application and show what this means. So it’s a protocol for two parties to exchange a key with messages, which gives you the ability to lie if somebody asks you which word was the key, you can claim it was anything later. So, a bit more formally, so we have two parties, this is the key exchange protocol for one party, and this is the key exchange for the other party. And each party also is equipped with this faking algorithm. This is the S-Fake and R-Fake.

I keep sender and receiver even though it’s not key exchange. It’s a faking algorithm that allows you to come up with fake randomness that demonstrate the key was anything. And we want correctness and semantic security, as usual. And we want this S-Fake takes the transcript and the randomness and the old key and the new key that you want. And then he comes up with this fake randomness, such that… And this is, you know, consistent with this new key K prime, and the same for the receiver. It comes up with a new randomness consistent with the K prime. And the requirement is that the attacker cannot tell the difference between the experiments when the key was exchanged, and you see the transcript with respect to the real key, or the case where the key was exchanged and then the faking algorithm will invoke what the adversary sees is the actual transcript but they don’t put it into a different key. So these are indistinguishable.

And then what if the parties don’t agree on K? Then there is another requirement there that says that even if the parties, one of them fakes the other one doesn’t, and then they cannot tell which one really faked and which one was to tell the truth. And the point is that these two properties together really give you what you would like from an ideally secure channel, even with respect to coercers.

So just to point out that, these properties hold only if the parties follow the protocol during the execution and actually choose randomness as they should. Otherwise, this doesn’t work. In fact, otherwise there is nothing that could work, because if the parties cheat from the beginning and just use a deterministic protocol instead of the randomized, or just randomness which is pre-determined, then, of course, there’s nothing you can do. However, you know, there are, of course, interesting situations where it is choosable to trust that the parties are actually using the randomness as instructed during the execution of the protocol. For instance, if we think about voting, this is something can be forced by the voting rules, but, you know, other situations. But this is kind of, like, essential. So maybe another minute to say a few words about, you know, just this construction and how it kind of works, in general.

So we have like a three-round protocol. So we have four programs, two from each party, to deal with the three messages. Then we have a faking algorithm for each party. So the way it works, , first, Violet here has this randomness, and actually chooses the key that they’re going to agree ahead of time, and inputs to the first program, which is kind of, think of it as an off-the-scale program, a black box program. And there’s the message, the first message is basically a hash of PRF of the S and the K [msg1 = PRF(s,k)]. And then the responder gets its message, has its own randomness and outputs another message, which is the hash of the first message and the randomness.

And then the third message now is going to be an encryption of the key and the hashes, and the two previous messages. This is a common encryption of this one long string. And then the fourth program just takes the randomness of the receiver and the two messages and puts it in and then outputs the key which is decrypted, essentially decrypts the ciphertext from here in doing all the checks. And then the faking programs, what they do, they just take the transcript and the actual key and the new key, and the striking program here puts a new randomness for the sender. And this one, there is a new randomness for the receiver. And the way this new randomness, S-frame and R-frame, work is, again, it’s kind of like natural, at least on the face of it. It uses the secret hidden triggers idea of Sahai and Waters for the sending on the deniability that, trigger each one of those programs to output their actual right message even when they get this S prime, and eventually this key K prime is out.

But the problem is that these hidden triggers, give you local consistency for each problem by itself. This was their goal. But there is no global consistency about those six programs together. And get the six programs together to be consistent with the fact that the key was actually K prime and not K, is [unintelligible] and this is something that will become the main challenge of this work. That’s also why we need these three messages, because if you have only two, then there’s no way to get a global consistency. So, anyway, so this is the gist.

And just to say about, you know, the future. So definitely we want stronger deniability for MPC. As I said, we just gave partial results. And then there’s some very interesting questions. One is, in general, you know, we know that iO is very nice, but in many cases we actually can do things without iO, indistinguishability obfuscation. But maybe deniability is one of the very few cases where actually we don’t have any other way to do things other than iO. Is it really essential? Can we prove it? And, if not, can we do without it?

Can we get around the CRS? Can you actually do with public-randomness CRS? And, more generally, we actually sweated a lot, spilled blood in order to make this thing work with iO, and because iO is really hard to work with. It would be great to find some general set of tools to work more easily with iO. Anyway, thank you very much. And that’s it.