Arbitrary computation on encrypted data

Roadmap
1

Last week during the public Global R&D, @victorshoup gave a presentation on a collaboration with Zama regarding fully homomorphic encryption (FHE) research. During the presentation, he said that somewhere in the grand and glorious future after the research collaboration that we hope to enable arbitrary computation on encrypted data.

You can watch the presentation starting here: Global R&D - April 2023 - YouTube

This is extremely exciting. I would like to ask @victorshoup and others involved to share more details on these plans if they can.

I have a few questions:

  1. Will FHE ever be able to provide truly arbitrary computation, including branching (if statements) and all other operations necessary for a turing-complete and expressive computational environment like we have with high-level languages such as Rust, Python, JavaScript, etc?
  2. If yes to question 1, will this require new languages or libraries, or will it be possible for example to feed Wasm or other bytecode/binary into some kind of FHE VM and enable arbitrary computation on encrypted data in that way, similar to a zkVM?
  3. The presentation mentioned other methods being explored, Iā€™m only really aware of MPC as another means to enable arbitrary computation on encrypted data, are there others?

Like I said, the vision here is extremely exciting and would solve a host of privacy issues with hopefully an extremely simple and familiar developer experience. Iā€™d like to know truly how promising this path is and what it will look like for developers, and how CDK authors (like us with Azle and Kybra) should expect to integrate FHE and the other methods in the future.

Thank you!

9 Likes
2

Good questions. Compiling general programs into the type of circuits that are suitable for FHE and/or MPC is an area of active research. There is a lit going on in this space, and it is also one of the areas where Zama has a lot of expertise. The short answer to your question (1) is ā€œhopefullyā€, but I wouldnā€™t want to make too many promises right now. For (2), Iā€™m pretty sure that any type of FHE on the IC will require some kind of runtime support both for replicas as well as clients, but this is an area that we have yet to explore very deeply. That said, hopefully the interface for dapp developers will be pretty straightforward. For (3), yes MPC is the only other technique, so it is mainly a tradeoff between computation and communication costs.

Thanks again for your interest and your questionsā€¦this is still very early days in this exploration, but stay tunedā€¦

10 Likes
3

Thanks very much for the extra details, and good luck with all of this. Iā€™ll be watching it with a lot of excitement, hopefully others as well.

3 Likes
4

Is there any insight you could give into branching/if statements? Historically whenever Iā€™ve tried to do FHE/HE branching has always been what killed it for any of the use cases I had in mind.

1 Like
5

Hello! Rand from Zama here

You cannot do branching in FHE, since this would imply having a cleartext control bit. What you can do however are 2 things:

  • you can call a decryption oracle to extract the plaintext value of your encrypted control bit

  • or you can regularize your code by evaluating the condition homomorphically, then using the encrypted control bit as the condition for an encrypted mux (a ternary if x then y else z). In that case however all branches will be evaluated, and the control bit simply nullifies the false one.

Regarding language support, we have an FHE library written in Rust (tfhe.rs), which has C and WASM bindings. We also have a compiler that converts python code into FHE.

7 Likes
6

Hmmā€¦it seems very difficult, impossible perhaps practically speaking, to have general-purpose FHE computation then doesnā€™t it?

Is FHE always going to be relegated to specific use-cases, or is general-purpose computation possible? If we have to execute all branches it seems very difficult to scale thenā€¦insights?

1 Like
7

How does this work if I have if statements in my code? Can I (or will I be able to eventually) take any arbitrary Python code and compile it into FHE?

8

Semantically, itā€™s the same thing actually. The mux operator in fhe is effectively equivalent to the ternary ? operator is other languages. Anything you can do in plaintext, you can do in FHE!

2 Likes
9

Performance wise however youā€™re right, thereā€™s a penalty since you would execute both branches. But in practice thatā€™s actually not a bottleneck for most use cases. And with FHE accelerators becoming available in 2025, it will be barely noticeable in terms of user experience

2 Likes
10

Intriguing thank you, whereā€™s the best place to dig into all of this more (Iā€™ve been following FHE/HE for years at a surface level and have played with your libraries), seems FHE capabilities are really about to start changing drastically.

1 Like
11

You can check FHE dot org, its full of resources and has a very active discord server

2 Likes
12

I heard Pascal speak about making a general purpose FHE-compiler or sortsā€¦ write code <> output FHE executable. Is this the direction ZAMA is taking or do you think there are still more performant lattice based FHE schemes to be made?

Are NTT (Number Theoretic Transform) the largest part of the cryptographic overhead with FHE? If a ICP node provider has special hardware for this, FHE could be made more practical now for the IC. I saw one such demo at FHE Tokyo with the Game of Life :slight_smile: There could be specific nodes setup with the state-of-the-art hardware available today.

I am biased towards application specific FHE due to the blowup doing full-computations which often occurs. For example, private inputs with a public state change, ZKP used to check the well-formdness of the inputs; many of the use-case in the R&D video can potentially already be done right now on the IC with FHE and ZKP. Last question, how do we trust the FHE being run on the IC? ZKP, consensus, other?

3 Likes
13

I believe ZAMA is itself working on developing algorithms for homomorphic computation on ciphertexts together with various types of hardware accelerants, ranging from GPUs to custom ASICs. The hope is that in some future version of the IC, we could have subnets running such special hardwareā€¦but that is all still in the future and nothing is yet worked out in any detail.

Re, trusting FHE on the IC: the way I see it, external users would submit encrypted plaintexts augmented with ZKPs that prove that these are correct encryptions. These ZKPs would be nonmalleable, so one user cannot copy encrypted inputs of other usres. Once ingested into the IC, the computations that might be performed on these encrypted plaintexts would be determined by the canister logic, so users would only submit encrypted data to canisters they trust to operate in a certain way. At least, that is the way I see things right nowā€¦it is still very early days

6 Likes
14

Hello!

We have an open source compiler that is geared towards ML applications, and that takes Python code as input (concrete.rs). If you want fast FHE integer arithmetics, you can directly use our FHE library (tfhe.rs).

Regarding schemes, there is always the possibility to invent something new, but the scheme we use (TFHE) is already incredibly powerful, as it isnā€™t limited to homomorphic additions and multiplications, and can also do homomorphic table lookups (aka univariate function evaluation!). This means we no longer need polynomial approximations for non-linear functions, and can guarantee the exactness of the FHE result. From a usability perspective, thatā€™s pretty much all you need, so the only thing remaining is performance.

On that front, we are making very fast progress, both in terms of cryptography, engineering and hardware acceleration. In our latest internal benchmarks, for 32 bit encrypted integers, it takes only 250ms to add, 350ms to multiply, 192ms to compare and 280ms to get the min/max. For 64 bits it 300ms / 870ms / 250ms / 340ms.

As you can see, things are quite good already, even on CPU! Granted, this will still be too slow for large applications, but for simple smart contracts like token transfers, DEXs, voting, auctions etc, itā€™s already usable! Hardware acceleration, which is coming in 2025, will make this 1000x faster / cheaper, which in turn means youā€™ll be able to run pretty much anything in FHE.

With regards to ZKs, as Victor said, we can already use them efficiently to prove the encryption was done correctly. However, to have verifiable FHE computation will take quite a lot more research effort, and will probably not be doable for at least a couple years. Until then, you either need to trust the server that it will do the right computation, or replicate the computation across different servers and have a majority consensus on the resulting ciphertext.

7 Likes
15

@victorshoup @randhindi someone asked about multi-key encryption in t-fhe here: Question: Does tfhe-rs (plan to) support multiparty or multikey FHE? Ā· Issue #381 Ā· zama-ai/tfhe-rs Ā· GitHub

The answer is that threshold FHE is coming in 2024. Is that threshold functionality a product of the research collaboration between DFINITY and Zama, or something else?

4 Likes
16

This is an exciting topic. Where can I learn more about your compiler?

17

@lastmjs you may be interested

1 Like