Fully Homomorphic Encryption
Is fancy encryption our way out?
So, AI is almost everywhere now.
You and I both know how powerful AI can be if used right: Imagine AI analyzing your health data to detect issues early, potentially saving your life.
However, as we delve deeper into AI's capabilities, one significant problem emerges: Privacy Concerns.
Things like AI-driven health scans require constant sharing of extremely personal information, which is usually handled badly and used for analytical purposes.
This begs the question, how can we have the benefits of big data without its downfalls and privacy concerns?
Is there a way to compute data without ever seeing what that data is?
This post will cover Fully Homomorphic Encryption, one way to do exactly that!
1) What is Fully Homomorphic Encryption (HME)?
Understanding FHE might seem daunting at first, but it's essentially about preserving mathematical operations on encrypted data.
Just as multiplication by a constant preserves addition in mathematics, FHE ensures that operations like addition and multiplication can work on data in encrypted form.
Suppose we have two encrypted numbers, E(a) and E(b) (as Encrypted a and Encrypted b), where a and b are the plaintext values we wish to encrypt. Additionally, let's say we want to add these two encrypted values: E(a)+E(b).
Using FHE, the addition operation can be carried out directly on the encrypted data. When we add E(a) and E(b), we obtain a new encrypted value E(a+b). Despite the encryption, the homomorphic property ensures that the result of this addition operation remains encrypted and cannot be decrypted without the appropriate key. This result maintains the same mathematical relationship as if the computations were performed on the plaintext values directly.
2) Where Would HE be used?
The concept of Homomorphic Encryption isn't entirely new, but it wasn't until fairly recently, with the breakthroughs of American computer scientist Craig Gentry, that its practicality was realized.
The goal is to enable computation on encrypted data without the need for decryption keys. The proposed solution involves constructing a scheme with efficient algorithms for encryption, addition, multiplication, and a method called "Recrypt" to refresh ciphertexts, allowing for homomorphic evaluation.
Most of us would agree that preventing search engines from getting to know too much about our personal choices is a good thing. It can be annoying when social media presents us with commercial products that we have been looking up on our internet browsers.
One way they can do that is by tracking our search keywords and patterns. Craig Gentry in his thesis “A fully homomorphic encryption scheme” notes that such sniffing of our searches can be prevented by encrypting search strings with homomorphic encryption – “the user submits an encrypted query, and the search engine computes a succinct encrypted answer without ever looking at the query in the clear”.
The implications of FHE extend beyond individual privacy concerns. It could revolutionize fields like scientific research by enabling analysis of sensitive data currently restricted by privacy regulations.
3) Types of Homomorphic Encryption
There are three main types of homomorphic encryption: Partially Homomorphic Encryption (PHE), Somewhat Homomorphic Encryption (SHE), and the gold standard, Fully Homomorphic Encryption (FHE).
Partially Homomorphic Encryption
Partially Homomorphic Encryption schemes allow for the evaluation of only one type of operation (either addition or multiplication) on encrypted data.
For example, an encryption scheme might allow the computation of additions on encrypted data but not multiplication, or vice versa.
PHE schemes are useful in applications where only one type of operation needs to be performed on the encrypted data.
Somewhat Homomorphic Encryption (SHE):
Somewhat Homomorphic Encryption schemes extend the capabilities of PHE by allowing both addition and multiplication operations to be performed on encrypted data, but with some limitations.
While SHE schemes can support a limited number of operations before the noise1 grows too large and the data becomes unreadable, they are still valuable for many practical applications.
SHE schemes strike a balance between functionality and efficiency, making them suitable for scenarios where a moderate level of computation is required on encrypted data.
Fully Homomorphic Encryption (FHE):
Fully Homomorphic Encryption is the most advanced form of homomorphic encryption, allowing many computations to be performed on encrypted data without any limitations.
FHE schemes enable addition, multiplication operations and more to be carried out on encrypted data indefinitely, without the need to decrypt it at any point.
However, FHE schemes tend to be way more computationally intensive and resource-demanding compared to PHE and SHE schemes, which can impact their practicality in certain scenarios.
4) Unbounded VS Leveled FHE
Bootstrapping is a technique used in homomorphic encryption to refresh the noise in encrypted data.
Until now, I have only presented homomorphic encryption with bootstrapping. That is unbounded FHE; one can do an unbounded number of addition and multiplication problems. The problem with this is that at the size of the circuit (the cipher text) can grow very large with each multiplication and addition operation; and this is why specialized chips are needed for the large circuits. There is, however, leveled FHE.
Leveled FHE uses a limited number of addition and multiplication operations. You can set a level depth of how complex the arithmetic operations are and still have the same security as FHE. This is done using learning with errors2 and can be done using conventional computers.
The scheme relies on a somewhat homomorphic encryption framework, initially capable of handling circuits of limited depth. By introducing bootstrapping, which allows the encryption scheme to evaluate its own decryption circuit, the proposal achieves a fully homomorphic encryption scheme. The construction utilizes ideal lattices3 due to their simple decryption algorithms and additive and multiplicative homomorphisms, making them suitable for the task.
4) So, Why Isn’t This Everywhere?
Despite its potential, FHE has faced challenges due to its computational intensity. Traditional computer hardware struggles with the complex encryption methods, which leaves us with slow processing and high energy consumption.
Another reason why FHE isn’t being used is because the companies doing the calculations really DO want access to the private data, and if it's encrypted, it no longer makes economic sense to them.
Companies Like Google and Microsoft profit immensely from analyzing and profiling your data for ad-purposes. And no for-profit company willingly kills it’s money maker.
Finally, the adoption of FHE faces regulatory problems and legal complexities. Governments are super interested in accessing citizens' data for surveillance, law enforcement, or “national security purposes”. Encrypted data presents a significant barrier to their spying..
Noise: "Noise" refers to the random error or distortion that is introduced during the encryption process. This noise arises primarily due to the complexity, speed and volume of the mathematical operations performed on the encrypted data and the limitations of the encryption scheme itself.
Learning With Errors: Learning with errors (LWE) is a mathematical problem that forms the basis of many cryptographic schemes, including some forms of homomorphic encryption. It's a problem related to lattice-based cryptography, where the difficulty lies in finding a small solution to a system of linear equations with errors. LWE-based encryption schemes often involve encoding the plaintext messages as vectors, encrypting these vectors, and then performing operations on the encrypted vectors while maintaining security.
Ideal Lattices: In mathematics, a lattice is a discrete set of points in n-dimensional space that are arranged in a regular pattern. An ideal lattice, specifically in the context of lattice-based cryptography, is constructed using ideals in the ring of integers of a number field. This construction provides certain algebraic properties that are useful for cryptographic purposes.