Big Brain Holdings

Flawed Homomorphic Encryption

Written by:

Caleb Shack

APRIL 18TH, 2024 | 8 minute read

A special thank you to all who contributed to this post: Sam Kim, Idan Sugarman, Rotem Tsabary, Arbion Halili, dWallet Labs, the Octra Foundation, Inco, and Khushi Wadhwa.

Until humans reach a state of global consciousness, privacy will remain a crucial vector in our coordination game. FHE is the way we achieve this.

The cryptography industry is still in its early innings. It is outrageous to claim that something will never work or be slow forever when the aggregate compounding of academic and entrepreneurial minds is nowhere near its apex. There are many fascinating areas of cryptography to delve into, but our focus for this article is on Fully Homomorphic Encryption, or FHE for short.

—

def FHE is an encryption scheme that enables multiplication and addition over ciphertexts. More formally, for some encryption scheme, E, function, f, and message, m, the following holds:

E(f(m)) = f(E(m))

—

Why FHE is Important

The need for privacy on blockchains (and elsewhere) is an industry-wide area of consensus. With KYCed exchanges and onramps, wallets can no longer remain pseudonymous while complying with AML standards. Moreover, decentralized training and compute protocols will not reach mass adoption without shielding user data. With all information on the table at all times, we are disadvantaged. 

This is not long-term sustainable. Privacy is important. FHE unlocks this.

Our Thesis

Many early privacy solutions were proposed under the domain of Zero Knowledge Proofs, or ZKP. These solutions have all largely been shown to be incompatible with computations over shared private state and suffer from risks of storing data off-chain (ZKP has 114 problems, and FHE ain’t one). The Achilles heel of ZKP is that whoever is proving the private data must know the data. This makes privacy schemes solely dependent on ZKPs at the crux of the validators who see everything posted to the network. ZKPs alone will not work.

There are a handful of approaches for solving private computation over shared private state, and they are naturally linked to a node’s arsenal: either private hardware (TEE’s, Oblivious RAM) or private software (FHE, Garbled Circuits, MPC). While we are also excited by the private hardware space, it is out of scope for this post. If you want to read more about this, read here, here, and here.

Among the latter software solutions, FHE is poised as highly venture-backable and shows much promise for shared private state without limiting nodes to host private hardware and secure enclaves.

Initially, the problem was proposed in 1978 after the invention of the RSA encryption scheme–a multiplicatively homomorphic scheme: E(x) * E(y) = E(x*y). The method whereby all modern FHE schemes are based on came about in 2009 with Craig Gentry’s Stanford PhD thesis on “bootstrappable” fully homomorphic encryption schemes. Today, we have about 4 relevant approaches to FHE, and researchers and entrepreneurs alike are looking to optimize the implementations and search for new, more efficient solutions.

To visualize where we are today, here’s a patent chart for Homomorphic Encryption (HE) compared to other cutting-edge security innovations like ZKP.

The quantity of new patents and publications in HE classifies it as an emerging field in development. To its right, ZKPs are classified as accelerating.

It’s not just entrepreneurs and academics who are building in this space, either. HE has practical applications in cloud computing that make it a desirable option for reducing the risk of custodying data.

With the advent of FHE spawning from a PhD thesis, we believe this space is ripe for new entrants. Overall, (F)HE is at the cusp of acceleration and will be essential for achieving computation over shared private state.

FHE vs ZKP

Many have posed the question: is investing in FHE today like investing in ZKPs 3 years ago?

Our timeline for FHE improvements aligns similarly with the ZKP improvements foreseen when capital was first deployed to that vertical. They share some similarities: 

1. During the early stages, FHE circuits and SDKs will be application-specific and handcrafted
2. No matter what, ASIC’s and FPGA’s will be the end-game for acceleration

However, the two technologies address different market segments. 

ZKPs are amazing tools for computing in highly adversarial environments such as blockchain networks. They are concise truth-tellers who cannot lie unless the system itself is hacked—a reason for our skepticism around zkVMs (20k+ open issues on LLVM at the time of publishing). Thus, ZKPs enable economies of scale for blockchains as thousands of transactions can be boiled down to one, and many proofs can be aggregated into one commitment. ZKPs can also be leveraged for the privacy of personal state; however, they falter in shared state when combined with public state, eventually leaking information. (e.g. consider a public DEX that reveals the pair price but conceals the value of each swap).

FHE does not enable scaling, and thus, its value is solely linked to the value of privacy. There will not be as many FHE commitments as proofs generated on blockchains, and privacy will likely cost a premium. How certain groups and individuals value privacy can be calculated by the opportunity cost of revealing public information vs opting for privacy or could be merely for vanity’s sake. This thought space is quite interesting and can be explored further here, here, and here.  

Areas for Improvement

FHE is often touted as a data type that will never be practical for blockchain-based use cases because it is inherently too slow, threshold insecure, or ASIC-dependent.

There is undoubtedly a lot of room for improvement, but what exactly needs to be improved?

Based on our review, we have identified 5 core sectors for improvement that we are actively investing in solutions:

1. Threshold FHE
2. Multi-key FHE
3. Verifiable FHE
4. New schemes and implementations
5. Acceleration

Threshold FHE

The current scheme proposed for FHE blockchains such as Inco, Octra, Shiba, and others use a universal public key for encryption and a distributed secret key for decryption. The mainstream threshold decryption schemes have weak security assumptions and do not enable a decentralized validator set.

The validator set proposed in the Noah’s Ark paper, for example, can only coordinate with 4 validators. In this case, only 1 node is needed to decrypt. Other thresholds are proposed in the paper, such as 10 (with 3 needed to decrypt) and 40 (with 13 needed to decrypt). These thresholds reduce security guarantees as they require an offline phase and exponentially increase the time to decrypt.

Further, out of the n validators in the set, it is only required that t < n/3 of them join together to decrypt the blockchain. In other words, 1/3 of the network. Combined with a small validator set, a 1/3 privacy assumption is quite insecure.

Thus, there are two core areas to improve here:

1. A larger, more efficient decryption set
2. A larger threshold, ideally > n/2

dWallet Labs’ 2PC-MPC breakthrough enables a more secure threshold decryption scheme, and we are looking forward to seeing the technology leveraged in Threshold FHE.

Multi-key FHE

An often unaddressed problem within threshold FHE schemes is that the universal decryption key can only decrypt ciphertexts encrypted using a universal encryption key. In other words, the network can come to consensus and decrypt all inputs to the network.

Having a universal key poses some serious trade-offs regarding privacy guarantees. Multi-key FHE circumvents this issue by enabling direct computations on data encrypted with multiple keys, producing a result that can be decrypted only with the consent and collaboration of all parties involved (i.e. the user and the validators).

The main reason why this scheme is not leveraged is due to the immense computational overhead it creates on an already cumbersome scheme. We are closely monitoring developments in this field to accelerate Multi-key FHE coordination.

Verifiable FHE

Another area of development in FHE is verified computing. With public blockchains, consensus ensures that all computations are done correctly. The same rough assumption can be made when all computations are encrypted. However, this requires that the consensus threshold of validators all complete the same computation. This is inefficient.

Currently, FHE computations are 4-5 magnitudes slower than their plaintext counterparts. Requiring all validators to compute every expensive operation limits validator economics and does not optimally allocate computational resources.

We need a verification scheme for FHE integrity.

New Schemes and Implementations

This critique is more open-ended and encourages continued innovation in the domain of FHE. As of today, there are around 5 relevant schemes for FHE, each with its tradeoffs:

• BGV/BFV: Uses a plaintext ring. Bootstrapping is slow but can be accomplished ad hoc. These schemes homomorphically compute batches efficiently, making them perfect for repetitive tasks.
• CKKS: Uses a plaintext ring of approximate real numbers. Bootstrapping is relatively fast and can be accomplished ad hoc, but results are not exact.
• TFHE/FHEW: Enables binary plaintext (good for computers). Bootstrapping is the most efficient out of the others but occurs after every operation.

Note that some of these schemes can have ad hoc bootstrapping, making them more efficient at scale than TFHE, in theory. In practice, it’s difficult to determine when bootstrapping needs to occur. An “FHE-compiler” of sorts would be useful (i.e some type of software that is able to predict noise and bootstrap accordingly with 100% success rate).

Further, some schemes work better for certain functions than others. For example, there are cryptographers who see BGV as the optimal scheme for matrix multiplication, whereas TFHE is the standard for more traditional operations. Developing a system by which schemes can be interoperable and composable with one another would enable a plug-and-play system for using the best schemes when appropriate. OpenFHE has a library to convert CKKS to TFHE/FHEW. We’d like to see more of these being developed. 

Lastly, we’re keen to see radically new approaches to implementing FHE schemes. Today, lattices rule the world of FHE ciphertexts, but what if this wasn’t the case? Teams like Octra are working towards implementing FHE as a hypergraph instead, for example. This is another area we are highly interested in seeing people explore.

Acceleration

The lag time in FHE schemes today comes from the inordinate amount of polynomials that are computed. This is a process that today’s CPUs are not efficiently made for. Ultimately, it comes down to ASICs and FPGAs, similar to ZKP hardware, to accelerate these functions. However, efforts are also being tested in the realm of GPU acceleration and Cuda implementations of FHE schemes from the likes of Lattica. If this is proven possible, computing parallel FHE operations will be accessible to anyone with a modern computer or smartphone.

The Somewhat Future

“Fully” means there is general-purpose, programmable privacy on shared and individual state. It is the end game. But much like ZKPs during their early innings, FHE will see individual circuits made on an application-specific basis. All of the faster HE schemes in existence lie in the “Somewhat” section, which usually means you can do a lot of additions and n multiplications without needing to perform bootstrapping. If you can plan out an application where you’ll never need more than n multiplications, it’s best to hand-sew a circuit in the somewhat section.

There’s also “Partial” HE, which falls in the bucket of only addition or multiplication. As mentioned previously, the RSA encryption system is Partial in the multiplicative sense. The most widely-used additive scheme is the Paillier Cryptosystem which enables addition on encrypted data. This type of scheme would work great for a private voting protocol, for example, where all you need to do is tally everyone’s votes.

Private information retrieval (PIR) is another interesting use-case that doesn’t require FHE, instead opting for Partial or Somewhat schemes. PIR enables users to query data from a database or blockchain without revealing the query itself. Instead, users send an encrypted query, signed with their secret key, and receive an encrypted response which they can decrypt using the same key.

Looking Forward

Fully Homomorphic Encryption is an extremely promising technology that will be leveraged on blockchains in the near future. However, a few areas need to be solved before it comes into production. We identified five, but there are likely many other areas that we didn’t cover. If you’re building in the FHE domain, please reach out!