What is FHE?

Fully Homomorpic Encryption is a technology that enables running arbitrary computer programs directly over encrypted data. What’s magical about it is that the data is never decrypted during computation — meaning users don’t need to trust the computing party with their data. In particular, FHE schemes support adding and multiplying ciphertexts under the same key. Specifically, for a public key pk and encryptions of messages m_a and m_b, we can produce an encryption of the sum or product of m_a and m_b:

$$\mathrm{Enc_{pk}}(m_a + m_b) = \mathrm{Enc_{pk}}(m_a) + \mathrm{Enc_{pk}}(m_b)$$ $$\mathrm{Enc_{pk}}(m_a * m_b) = \mathrm{Enc_{pk}}(m_a) * \mathrm{Enc_{pk}}(m_b)$$

In most FHE schemes, addition is straightforward to implement whereas multiplication is more challenging. Nonetheless, any scheme that supports an unlimited number of both operations can compute anything. There are a number of ways to combine these operations to achieve this goal, but Sunscreen leverages multiplexers to accomplish this. The next few sections describe how Sunscreen internally performs computations.

Multiplexer gates (aka muxs)

Multiplexers are a universal (i.e. they can compute any function) logic element that takes 3 binary inputs: a, b, sel. When sel = 0, the multiplexer outputs a and when sel = 1, it outputs b. If you can add and multiply binary values, you can implement a multiplexer:

$$c=(b - a) * sel + a$$

Homomorphic multiplexers (also called CMux) serve as the central element to perform computation in our scheme. They are computationally efficient, simple to compose into functions, and feature good noise characteristics.

Noise

All of today’s practical FHE constructions are based on some variant of the Learning With Errors (LWE) problem. These cryptosystems’ security requires adding just the right amount of noise during encryption: adding too much noise leads to a garbage value after decryption but adding too little compromises security. Noise is a central issue in FHE because the result of a homomorphic operation contains more noise than its inputs. Noise cascades as one performs computation, with a possibility to eventually accumulate so much noise that the ciphertext becomes garbage (e.g. cannot be decrypted to the correct value). Thankfully, a technique called bootstrapping allows us to reduce the amount of noise in a ciphertext so that we can continue performing computations.

Circuit bootstrapping

A central component of our TFHE scheme variant is a technique known as circuit bootstrapping (CBS). CBS takes a high noise ciphertext of one type (LWE) encrypting a binary message and produces a lower noise ciphertext of another type (GGSW) encrypting the exact same message.

Ciphertext types

There are 3 different types of ciphertexts involved in computation:

• LWE: a compact ciphertext meant for homomorphic addition only.
• GLWE: a less compact ciphertext. Supports homomorphic addition just fine. While multiplication works, it incurs tons of noise.
• GGSW: the largest ciphertext. Supports the required homomorphisms with favorable noise growth.

Interestingly, one can also compute a homomorphic multiplication between a GLWE and GGSW ciphertext, producing a GGSW. This is faster than with two GGSWs and still features favorable noise characteristics, especially when the GGSW has low noise (such as right after a circuit bootstrap operation). Using this trick, we can build an efficient multiplexer where $a$, $b$ and the result are GLWE ciphertexts and $sel$ is a GGSW. However, the type mismatch requires careful composition as we will see below.

Putting it all together

The following diagram shows the FHE computation loop:

The high level goal is to perform general computation using the multiplexer tree (aka the cmux) before going on to reduce the noise (via circuit bootstrapping) so that we can continue performing more computations. The type mismatch between the cmux and circuit bootstrap requires us to perform some additional operations to get the output of the cmux into the “right” form to feed back into the circuit bootstrap.

We start by circuit bootstrapping LWE encryptions of bits (e.g. a 32-bit integer) to produce GGSW encryptions of the same bits. These bits are fed to the select lines in a mux tree transcribed from a lookup-table. Running the mux tree results in GLWE outputs of a function, which must be converted before sending them back to the user for decryption or to be used in further computation. Sample extraction and key switching are techniques in FHE that facilitate this conversion process, but we won’t bore you with their details.

Other interesting properties

FHE features a number of other interesting properties that are useful in building applications for Web3.

Public key

FHE schemes allow for encrypting messages under either a secret (i.e. symmetric) key or a public (i.e. asymmetric) key. This is crucial in web3 as it allows you to encrypt messages under a key you don’t know. Sunscreen supports and simplifies some details of efficiently encrypting messages under a public key.

Threshold FHE

With a few modifications, one can use FHE to enable computing over multiple parties’ data. We do this by using threshold FHE.

Multiple parties each hold a shard of the secret key such that t of n parties must come together to decrypt a message. Introducing a threshold committee simplifies building multi-user applications as all data can be encrypted with respect to this threshold public key. As such, Sunscreen features a threshold committee to support threshold FHE.

Post-quantum

FHE is post-quantum, meaning there are currently no known “practical” attacks against these schemes using a quantum computer. This is with the obvious caveats that the scheme is set up correctly, has appropriate security parameters, etc.