Janmajaya Mall

There has been a lot of recent progress and interest in iO (Indistinguishability Obfuscation). This session will cover topics from the basics to theory and attempts at practical implementations—plus ways of breaking these attempts.

Breakout 2

Indistinguishability Obfuscation (iO)

Privacy is an unsolved challenge for blockchains and decentralized systems. ZK cryptography gets us there partially, but not all the way. ZK enables “single-player private state,” and certain other kinds of privacy are impossible to realize with ZKPs alone. Panelists, the cryptography library devs, infrastructure builders, and application devs who have recently started to explore programmable encryption will discuss MP-FHE as one such tool for achieving more general privacy capabilities.

Stage 6

Multi-Party FHE for Multi-Player Privacy

The talk introduces "phantom-zone", a framework to write scalable consumer facing MPC apps using multi-party FHE. Starting with what's multi-party FHE, talk gives a demo of non-trivial MPC app. Followed by introduction to programming model of MPC apps using multi-party FHE inside phantom-zone. Then the talk dives deep into primitives to realise multi-party FHE and ends with advanced FHE gadgets that further enhance multi-party FHE.

Scalable multi-party FHE with Phantom-zone

 Tanya Cushman Reviewer:"Presenter": Hello, welcome back. So, today I will be talking about Phantom Zone. But before I dive deep into Phantom Zone and talk about the rest of the things, I would walk you through the motivation behind Phantom Zone. So, if you guys are familiar with globally mutually trusted third party, I would want to introduce you to this idea of globally mutually trusted third party. What is this globally mutually trusted third party? Well, it provides you three guarantees. The first thing that it says is that whatever information you send to this third party, it will always keep that private. It would not leak it to anyone. The second guarantee that it provides is that all the information that it has collected over time from different people, you know, we have been sending this globally mutually trusted third party all our information, let's say for a year, all the information that it has collected for all these years, it will always keep it private and would not allow anyone to poke inside its memory. And the third guarantee that it provides, which makes this particular party very magical, is that it can compute any arbitrary function we want it to compute, as long as we provide enough authorization to be able to compute that function. And it will only output the necessary outputs. Usually, I sort of refer to this mutually trusted third party as a mutually shared computer. And if you guys are familiar with something called the God Protocol, this is the God Protocol. This is a picture from an example back in 1987. This is a picture from an example back in 1987. So first observation to make is that if you really want these three guarantees to be, if you really want this party to be globally mutually trusted, we want this party to be able to prove these three guarantees to any individual without requiring any additional interaction, which is why we require cryptography. to prove these three guarantees to any individual without requiring any additional interaction which is why we require cryptography we cannot just make it on a certain legal arguments or something like that we require cryptography for building this the building this globally mutually trusted shared computer and we started to build phantom zone to eventually build the god protocol but to stick within the realms of practicality, we could only build an abridged version of it. So for the rest of the talk, I will be talking about, A, what is Phantom Zone? Why it is an abridged version of this God Protocol? And the second important thing that I'll be talking about is, how can we push the frontiers to eventually build the God Protocol? Okay, so Phantom Zone, the abridged version. The key idea in Phantom Zone is something called multi-party fully homomorphic encryption. And for me to describe you multi-party fully homomorphic encryption, I have to eventually describe you what is single-party encryption. In single-party encryption, you have a single client, this guy over here. They hold a secret. They keep the secret private to them. They can encrypt their information, which is A here, with their secret and produce an FHC ciphertext. And then they can send this FHC ciphertext to any server. And the can evaluate and any arbitrary function on their private input which is a and produce an output ciphertext and that the and the client can receive the output ciphertext and decrypt it. So this is single-party FIG coming to multi-party FIG. Well the key idea in multi-party FIG is that you split this secret which is held private by a single client in single-party FIG. Well the key idea in multi-party FIG is that you split this secret which is held private by a single client in single party FIG among many clients. So you have S0, S1, S2 as secret shots split among these three people over here. The first step in multi-party FIG is something called collective public key generation. So all these three parties come together and they generate the collective public key. And then all these three parties, using the collective public key, encrypt their private inputs and produce FHC ciphertext. And then they send their FHC ciphertext to the server. Server executes a marble refunction on the FHC ciphertext and produce an FHC output. The key thing to notice here is that all these parties would have to produce a decryption share to eventually decrypt the output ciphertext here. So they produce the decryption share using the secret shards and then they send it to each other and then only they're able to decrypt the output ciphertext. Because in this case, the secret was split among all these parties. So why is Phantom Zone an abridged version? Well, because Phantom Zone, assuming that in the future we're able to add publicly-verifiable FHE to a Phantom Zone can only guarantee the three guarantees that I talk about in the God Protocol to only the holders of the secret shots. It cannot guarantee these three guarantees to everyone around the globe. Which is why Phantom Zone is just an abridged version of it. Okay. So you might wonder, how do we build towards the God protocol? How do we even do it? Well, what I would like to say at the moment is I would have loved to say that after a lot of research and a lot of five years of research, we have figured out the solution to build the God protocol. But no, there are no enlightening thoughts here. And there's one obvious answer to eventually building the God protocol, which is program of sophistication. What's program of sophistication? Well, to simply describe the program of sophistication, let's just assume that you have function f, right? What you can do with program obfuscation is you take this function f and perform some transformations on this function f and produce an obfuscated circuit. You can give this obfuscated circuit to someone else and program obfuscation guarantees that the only thing that you can learn from that obfuscated circuit is the input to output map and nothing else. Now you might be wondering why is this useful? Because if the function is trivial, then you can easily learn it from the input to output map. Program obfuscation becomes very interesting when you sort of like obfuscate a program that is a cryptographic function. For example, let's just say that I take a function that decrypts any ciphertext that is encrypted to my public key. So I take a function and this function has my secret key and it decrypts any ciphertext that was encrypted to me using my public key. And I perform certain transformations using program obfuscation to this function and produce an obfuscated circuit. I give this obfuscated circuit to someone else. What they can do is that they can decrypt any ciphertext that was encrypted to me using this obfuscated circuit. But they can never, ever learn what the secret is inside that circuit. They can never learn my secret key. And these are the class of functions where program obfuscation becomes useful. And I'll tie it to building the God protocol later in the slides. to building the got protocol later in the slides. So now, assume that we can only build program obfuscation for some limited class of functions, not for general class of functions, but limited class of functions. I'll tell you one way of building the got protocol using program obfuscation. building the got protocol using program of application. Step one, modify the FHT scheme that we're using before to become publicly verifiable. What do I mean by that? Well a publicly verifiable FHT schemes does those things. It evaluates the FHT function which you know a a normal FHE scheme does. In addition to evaluating the function, it also produces a proof of correct evaluation so that anyone can verify this proof with the output ciphertext and be assured that the server that sort of executed this FHE function executed it correctly, and which I usually refer to as proof pi of correct evaluation. Step two, replace the collective key generation operation that we did in the multi-party FHE with a trusted setup. In the trusted setup, you have arbitrary number of people here. They perform some MPC protocol to produce FHE keys. The two types of FHE keys which are very important. Public key and the bootstrapping key. Bootstrapping key is usually used for some sort of FHE operations that you can completely black box. The key thing here is that no one knows the ideal secret key because we're doing a trusted setup in MPC to generate these two keys. The third step is modify the trusted setup to also output an obfuscated conditional decryption oracle. Okay, that's a mouthful. I sort of like go into it one level deeper. What is an obfuscated conditional decryptor? This particular conditional decryptor is an obfuscated program of the following functionality. What it does is that takes an output ciphertext and a proof of correct evaluation of FIG circuit. It verifies whether the proof is valid and decrypts the output ciphertext if and only if the proof is valid. And this sort of like tells you why did we assume in the first place that program obfuscation may be feasible only for like limited class of functions because to build the GOT protocol like to build the got protocol using the FHERoute, we only need program obfuscation to be practical for this obfuscated conditional decryptor. So we modify the tracer setup to also output this obfuscated conditional decryptor, and that's it. And another thing to note is that this conditional decryptor also has the secret key, the ideal secret key that no one knows embedded inside it. Okay. So the end-to-end flow is, you do MPC to generate three things. Public key, bootstrapping key, and the offscored conditional decryptor, which I now realize is somewhat of a mouthful. I should have chosen some other term. Anyways, the second flow is, now anyone can encrypt their private inputs using the public key that is the output of the MPC protocol. So you have multiple ciphertexts here. And then they can send it to the FHC server. FHC server evaluates the FHC function, outputs the encrypted output. In addition, it produces a proof because the FIG server is evaluating a publicly verifiable FIG scheme. And then we plug in the proof as well as the output to the off-scaled conditional decryptor and the conditional decryptor would only decrypt the encrypted output if and only if the proof is valid. So this is one way of building the God protocol using publicly verifiable FHE and program obfuscation for obfuscated conditional decryptor. So there's one way, which I've just shown you, but we need new ideas to push the frontiers and to finally build the program obfuscation or and to finally build program obfuscation or indistinguishably obfuscation, if you're familiar with that. Here, I've showed you just one way. But if you're able to come up with new ideas, then probably we can make program obfuscation more practical for general circuits, not just for limited class of functions that we used before. And probably, we can directly build the God protocol from program obfuscation. So while I was exploring this field of program obfuscation and I.O., one key observation that I made was that it's really hard to get efficient program of specification from standard assumptions and we would inevitably require exotic assumptions. And I'll tell you what are standard assumptions and what are exotic assumptions. Well a standard assumption is an assumption that has been there for a while, for example D log, discrete log problem. There also exists additional incentive for people to break these standard assumptions. And exotic assumptions are somewhat newer assumptions. Like, they have been only there for like five years, or not even five, it was like two to three years. What we can do as a community to, you know, realizing that we might inevitably need newer assumptions to build practical program amplification is we can start examining these newer assumptions, start breaking them, start testing them. Or we can build applications using this assumption so that we can incentivize people to break them and tell us whether they're broken or not. And then eventually, in a few years, we would have candidate assumptions that are newer assumptions, but they have become then standard using which we can build practical program sophistication. And taking a first step towards this, we are launching a bounty program to break one of the candidate assumptions, which is called program obfuscation by local mixing. The way I think about this particular assumption is that they're taking more computational complexity approach than taking the traditional approach of using algebraic structures to build program obfuscation. The goal of the bounty is that we provided an obfuscated circuit with roughly 240,000 gates, which was obfuscated from an original circuit with roughly 1,000 gates. And you had to find the original circuit. You can learn more about the bounty at OfficeTopia.io. If you know what OfficeTopia is, OfficeTopia means that we're living in a world where authentication is practical, and the bounty amount is 10K. And this bounty is launched in collaboration with Ethereum Foundation and Zerix Spark. Okay. So before I break, and I think that I have a bunch of time, okay, before I break, and I think that I have a bunch of time. Okay, before I break, I would want to make one conjecture. And the conjecture goes as follows. I think the God protocol is the convergence of cryptography. Probably building the God protocol would require certain sort of like FHE. That is just one route, but like publicly viable FHE and other things like MPC for just setup and so on and so forth. But once you build the got protocol, I think it encompasses everything. It gives us everything that we have been wanting for for a while. It gives us witness encryption. It gives us zero knowledge proofs via signatures. It gives us MPC, multi-party computation. It gives us FE, functional encryption, all of these things that we've been demanding for a while. And this is also one of the major reasons that we should start investigating much more seriously how to get practical program application and finally build the God protocol. And that's it. Thank you. All right, thank you for All right. Thank you for the talk. We do have some questions rolling in. Yeah, let's go through some of the questions. Let's start with the first one. Can we implement threshold ECDSA with Phantom Zone? At the moment, yes, because you can express everything. Like, theoretically, yes, but it would be very impractical to implement ECDSA with PhantomZone at the moment because ECDSA is like you're doing elliptical operations, which is a lot of operations. As far as I understand, threshold ECDSA is possible. It takes two days to generate one single signature. All right, so next question. Can you tell us a little bit more about the definition of obfuscation as a virtual black box? That's the first question over here. Isn't the definition of obfuscation as a virtual black box impossible? virtual black box impossible? I am not posing obfuscation as a virtual black box. I did not mean to say obfuscation is a virtual black box. By the way, the impossible result of a virtual black box is only for certain very restricted class of programs. It's not for general class of programs. Eventually you can aim for virtual black box with certain caveats. But again saying that my definition of sophistication is not virtual black box. All right and what can be done today with Phantom Zone? At the moment as I said Phantom Zone is an abridged version of the Scott protocol. It does not even have publicly verified FHE scheme, so it does not give you all the three guarantees. The only guarantee that it gives you is that it will execute the function that you ask it to execute while private information can be coming from multiple people. It'll keep the information private, but you'll have to trust it for it. So you'll have to trust this particular server to always keep the information private, but you'll have to trust it for it. So you'll have to trust this particular server to always keep the information private and not send it to anyone else. Perfect. And we do have one last question. Oh, cool. More questions rolling in. Can obfuscating programs undermine open source transparency and make it harder to verify the absence of malicious code? I see. Make it harder to verify absence of malicious code? I see. Make it harder to verify absence of malicious code. Well, that is assuming that the entire program is obfuscated. When I say obfuscation, we require obfuscation for certain parts of the program, which can interact with a public program and a private program which is obfuscated. I understand that obfuscation can be used for many malicious purposes as well, like for example, you know, like, there are several reasons why people might be interested in obfuscation, but we can, as a community, make sure that there's interaction between the public interfaces and the private interfaces which are obfuscated. All right. And why do you call the publicly verifiable FHE circuit obfuscated? Doesn't the require solidity verifier or something which is public? No, I think once I give you obfuscated circuit, there are certain guarantees that you can learn from the obfuscated circuit itself, that it does not reveal anything, as long as you've done the obfuscation correctly. Alright, and do you have evidence that the conditional decryption functionality is possible using I.O.? Yes. There are theoretical results and we're trying to make it practical as well. All right. Can you give one example each on how I.O. can replace ZK, MPC, FHE? Okay. So for ZK, what you can do is like you can embed a secret key inside this off-secreted circuit, the God protocol, and a zero-knowledge proof is just a signature from this God protocol. Whatever secret exists inside this particular server or this God protocol, or this FHC circuit, off-secreted circuit, a signature by that thing becomes a zero-knowledge proof. So you do not require zero- zero knowledge on the client side anymore. For MPC, again, it's a globally mutually trusted third party. All of us encrypt our private inputs with the public key corresponding to the secret key that lives inside this off-site circuit. And we send our private inputs to this. It decrypts that, performs some function, and produces the output. So that's one way of replacing MPC, and the same applies for FG. Cool. We can stay here for maybe another 10 seconds if there are any new questions rolling in. All right, cool.

https://streameth-develop.ams3.digitaloceanspaces.com/transcriptions/6735aeab9dbb7a90e1bde09b.vtt