Towards Fully Homomorphic Encryption in Smart Contracts
(Skip the talk, go straight to the code.)
NuCypher’s mandate is to implement the cryptographic primitives of today, and research the cryptographic primitives of tomorrow that will enable individuals to assert their right to privacy. We believe that the most intriguing privacy technology on the horizon is fully homomorphic encryption (FHE).
FHE offers the tantalizing promise of performing arbitrary computation on encrypted data and lacks the limitations associated with other promising privacy technologies. For example, zk-SNARKS/STARKS are limited to transactional privacy; secure multi-party computation (sMPC) is constrained by fundamental technical limitations due to network overhead; trusted execution environments (TEE) are prone to fatal flaws like Meltdown, Spectre, and Foreshadow, and currently place the root of trust in the hardware manufacturer.
For a given ciphertext C = E(K,P), FHE enables you to calculate a new ciphertext C′ = F(C), without decrypting the initial ciphertext C. Theoretically, this enables the outsourcing of private computations to cloud providers or decentralized networks, opening up many exciting possibilities, from private cryptocurrencies to fully private decentralized applications and confidential smart contracts.
Of course, many challenges remain to be solved. Can FHE be made performant enough for practical application? Can ciphertext expansion be limited to feasible levels? Are the security properties of FHE such that it can be implemented and used safely?
While it’s early days, we’ve been working on these questions and have made significant progress. Today, we’re excited to share our initial work on nuFHE. We’ve applied GPU-acceleration of fast Fourier transforms (FFT) in the TFHE library to achieve ~100x performance over TFHE’s existing benchmarks. We think this makes nuFHE the fastest publicly available FHE library.
For thoroughness, we also benchmark against the cuFHE library, which uses an improved CUDA implementation of the number-theoretic transform (NTT).
Since FFT is the bottleneck in the TFHE algorithm, optimizing it yields significant performance improvements. The data being transformed has two exploitable properties: it is real (in fact, integer) and antiperiodic. These properties allow us to use a quarter-size complex-to-complex FFT with some pre- and post-processing of the data.
Commonly used optimization techniques preserve the frequency order in the transformed data, which means that some processing that isn’t fully parallel is required (namely, prefix sums). In the TFHE algorithm, FFT is used for convolution only, so the frequency order does not matter. This means that a much simpler, fully parallel pre- and post-processing can be used. As an additional bonus, it also preserves the sequential memory access, which is important for optimal performance on GPUs.
The road ahead
Our primary interest in nuFHE lies in its application to blockchain-based smart contracts and its potential to further our mission of empowering individual’s to assert their right to privacy in the digital age.
Fully homomorphic encryption is often cited as the holy grail of encryption. The time has come to regard FHE as something less mythical, that is worth applied research and engineering effort.
We believe the performance levels we’ve achieved of ~4,500 MUX and 7,500 gate operations per second are sufficient for most smart contracts. The difficulty is that smart contract privacy isn’t compatible with having one global shared state for all contracts and users like in Ethereum. Each user is only able to decrypt what is encrypted for them and FHE doesn’t support working with random access memory — one needs to pass all the state through a circuit. Thus, a practical implementation requires more diligent thinking than merely continuing to accelerate FHE (which we plan to continue doing).
While nuFHE is a major step towards achieving homomorphic smart contracts, much work remains to be done. We’re extremely interested in collaborating with universities, labs, and researchers working in this problem space. And, we’re actively hiring for fully homomorphic encryption researcher roles (firstname.lastname@example.org)!