Mathematical Certainty in Security: The Rise of Fully Homomorphic Encryption

September 17, 2024

Blog

Interest in Fully Homomorphic Encryption (FHE) is growing as companies seek more robust data privacy solutions in an increasingly regulated world. FHE allows data to be processed without ever being decrypted, a breakthrough that could revolutionize industries where data security is paramount. To delve deeper into this technology, let’s look at the development, challenges, and future of FHE, shedding light on its potential to redefine secure data processing.

The development of Fully Homomorphic Encryption (FHE)

Homomorphic encryption developed gradually over the past several decades, first by the accidental discovery of partially homomorphic systems and then more purposefully until its full capability emerged in 2009 and the following decade.  The implications of these developments were staggering: we could send data to the cloud, an AI engine, or another third party for processing without ever worrying about a resulting privacy breach. However, the computational power required to implement FHE remained many orders of magnitude greater than computing “in the clear”, making broad adoption a difficult sell, and relegating FHE to an academic endeavor.

Now, however, interest in and advancement of FHE is driven by new forces. Companies must navigate a complex legal framework encompassing GDPR in Europe, CCPA in California, and diverse regulations in at least 14 other U.S. states.  And yet, the commercial appetite for third-party data continues to grow: Companies are counting on the ability to ingest new data to solve hard problems ranging from detecting financial fraud to researching medical treatments.

At the same time, privacy-assuring alternatives to FHE face significant headwinds. Confidential computing methods such as Trusted Execution Environments (TEEs) have been shown time and again to be vulnerable to both side-channel attacks and direct breaches, placing the companies that rely on them at risk. Other privacy-assuring approaches such as secure multi-party computation typically require networks of computers to be and stay online together throughout computations, requiring complex network configurations and vulnerable to failure if any one of the participating machines or network links fails.

FHE, on the other hand, has cryptographically sound proofs of privacy, requires no complex network configurations, and relies only on a single compute server’s reliability. This pairing of cryptographically strong privacy guarantees with simplicity of deployment makes FHE a strong contender for practical, secure privacy assurance in fields such as finance and healthcare, where privacy is paramount. With FHE, companies can perform computations on encrypted data, ensuring that data remains protected throughout storage, transit, and processing. Now, we’re at the forefront of a new wave of hardware accelerators that will take FHE the last mile to commercial performance viability. We’re on the brink of a whole new era in data privacy. Within a generation, there will be no such thing as sharing or outsourcing computation on unencrypted data.

Computing on encrypted data

In the past, we’ve encrypted data at rest - in storage media such as disk drives - and in transit on networks. However, to process data, we needed to decrypt it, because no practical encryption mechanisms also allowed computation. Decrypting the data also made it visible to anyone performing that computation, requiring the data’s owner to trust those performing the computation. Novel encryption schemes such as those used in FHE not only keep the data from being revealed, but also allow computation on the data in its encrypted state. As a result, data owners need not trust those performing computations to keep the data private. This “zero trust, full computation” breakthrough is a sea change in the relationship between data owner and data processor, enabling outsourcing of computation without risk of data compromise.

Challenges in implementing FHE

There are three main challenges:

1. The computational complexity of FHE is a performance challenge. FHE computations are dramatically slower than unencrypted computations, often by several orders of magnitude, making it difficult to achieve practical performance levels. This slowdown is due to the additional work required by CPUs and GPUs to manage the complicated data representations used in FHE. 

2. The data expansion typically seen in FHE encryptions is a storage and network bandwidth challenge. Homomorphically encrypted data is also substantially larger than unencrypted data, requiring times more storage space. Current research ideas such as hybrid FHE are insufficiently developed to answer this challenge so far.

3. The complex algorithms required to compute in FHE are a usability challenge. Programming in FHE - even with the advent of some fantastic FHE libraries - is a major challenge because of the many parameters that must be correctly chosen for FHE, and because of the many auxiliary operations needed to “manage” FHE computations, which (due to lack of tooling) cannot be automatically handled by the programmer’s tools.

How to encrypt data for FHE and the role of homomorphism

To answer that question in full, we’d need to talk about Gaussian noise sampling, polynomial representations of data, residue number systems, the Learning With Errors math problem, public key encryptions, prime modular arithmetic, and high-dimensional vector spaces – not really great topics for polite company! Instead, let’s do a quick summary. In FHE, we move data from the normal number line into an alternative space. What’s important is that the movement of the data is an encryption - something much harder to undo if you don’t possess a specific key. The other thing that’s important is that the alternative space be homomorphic (homo- for “same”, -morphic for “shape”) to the regular number line with respect to multiplication and addition so that once the data is moved, you can add and multiply at will knowing that when you move the data back (via decryption), those multiplies and adds did the expected thing to the data.

Programs, Computations, and Limitations

The security provided by FHE is based (in part) on adding a little “noise” to data during the encryption process. One of the problems with FHE is that when you add or multiply the data, that noise grows - just as you’d expect. After a certain limited number of operations on a data item, the noise can grow large enough that decryption is no longer possible. To deal with that problem, FHE uses a special but very expensive process to remove noise without revealing data, so that computation can continue. This special process must be done every few operations to keep the data fresh, but it is by far the most expensive operation used in FHE - consuming as much as 95% of computation time.

That’s a long introduction to say that the best-suited computations for FHE are those that don’t require very many operations sequentially on data, so the noise removal process is unused or seldom-used. What kinds of computations fall into that regime? Linear algebra and private information query are two examples. Extending those ideas, statistical computation such as regressions, certain kinds of image processing, and even relatively simple neural networks can be good targets for FHE-assured privacy.

Optimization and careful selection of use cases are essential to maximize the benefits of FHE.

Practical applications for FHE

FHE unlocks entirely new applications across industries that would be impossible without mathematically guaranteed privacy. While some of the following applications are still challenging at scale for FHE, they are all good targets for hardware-accelerated FHE in the near future.

Healthcare statistics: FHE facilitates large-scale analysis of health records while maintaining patient privacy. Clinicians and insurance providers can analyze data on patient satisfaction, hospital readmission, and other factors across their patient populations. This comprehensive analysis helps uncover more effective treatments and personalized care plans, improving overall quality of life.

Finance: FHE enables the secure sharing of financial transaction data across institutions and borders, allowing banks to identify fraudulent accounts and transactions regardless of their origin. This enhanced ability to detect and prevent fraud strengthens the financial system's integrity.

Machine Learning: FHE allows machine learning models to analyze sensitive data without exposing the data itself. For example, image recognition can identify security threats or legal violations without inappropriate surveillance, and medical scans can be analyzed without risking patient data exposure.

Market Intelligence: FHE enables manufacturers to share inventory, sales, distribution data, and more with analysts, data brokers, and even competitors. This collaboration enhances the ability to predict and respond to market changes and manage supply chains effectively. Data brokers can also perform computations on private data such as GPS locations, uncovering valuable population-level insights without compromising individual privacy.

Cross-Organizational Coordination: FHE enables secure and private data sharing between different jurisdictions.

Advancements in FHE, and comparison to unencrypted computations

Advancements in FHE have focused on optimizing algorithms, developing specialized hardware to accelerate processing, and to a lesser degree, leveraging parallel processing. Niobium's FHE Hardware Acceleration chip, for example, includes proprietary optimizations and a hardware-software co-design approach to enhance performance. Despite these improvements, FHE is still slower than traditional unencrypted computations. Even with the first generation of Niobium’s hardware acceleration, well-chosen FHE applications can be hundreds of times slower than "in the clear" computations, though efforts are ongoing to reduce this gap significantly.

Already, we have made meaningful progress. By accelerating FHE computation by a factor of up to 10,000, we have met the practical requirements for several applications, particularly in sectors like finance, insurance, and healthcare. According to feedback from potential users, the current speed of our chip is sufficient to unlock many new and previously infeasible use cases for FHE, allowing them to guarantee data security and privacy during processing. These companies will be able to use and share data for processing and analysis while keeping the actual contents of the data utterly confidential. This is the key to a safe, profitable data economy. Using FHE hardware acceleration, companies can conduct analysis of rich data sets without compromising security or privacy.

Proof-of-concept work in various industries has shown us that our current computation performance is more than adequate for many practical applications, such as neural network-based machine learning or financial fraud detection across international borders. We are also leveraging feedback from this work to refine our hardware architecture and guide future developments to achieve even better performance.

The Future of FHE

Many companies and investors have recognized the potential of FHE to revolutionize the data economy – there has been at least $200M worth of venture investment in FHE hardware acceleration alone, as well as substantial investment by the US Government in the form of a dedicated DARPA program, DPRIVE. These investments are driving toward the future goal of FHE achieving performance parity with traditional unencrypted computations, making FHE practical for a wider range of applications. Developments in the next few years are expected to focus further on optimizing algorithms and hardware to reduce computational overhead, developing user-friendly programming interfaces and tools to simplify FHE implementation, and expanding the range of practical applications to demonstrate the value of FHE in various industries through proof-of-concept projects and real-world deployments.