Homomorphic encryption is a powerful cryptographic technique that allows computations to be performed on encrypted data without decrypting it first. This blog post will introduce the concept of homomorphic encryption and demonstrate implementations using Python.
What is Homomorphic Encryption?
Homomorphic encryption is a form of encryption that allows specific types of computations to be carried out on ciphertext. The result is encrypted data that, when decrypted, matches the result of operations performed on the plaintext.
How Does Homomorphic Encryption Work?
To understand how homomorphic encryption works, let's break it down into key concepts:
Traditional Encryption vs. Homomorphic Encryption
In traditional encryption, data is scrambled in such a way that it can only be unscrambled with the correct key. Once encrypted, the data can't be meaningfully manipulated without first decrypting it.
Homomorphic encryption allows for meaningful manipulation of the encrypted data. The magic lies in creating an encryption scheme where operations on the encrypted data correspond to operations on the original data.
Mathematical Foundations
Homomorphic encryption schemes are built on complex mathematical structures and problems that are believed to be computationally hard to solve. These often involve concepts from number theory and abstract algebra.
Homomorphic Properties
The key to homomorphic encryption is that certain mathematical operations on encrypted values correspond to operations on the plaintext values. In general:
- For addition: \(E(a) ⊕ E(b) = E(a + b)\)
- For multiplication: \(E(a) ⊗ E(b) = E(a * b)\)
Where \(E()\) represents the encryption function, and \(⊕\) and \(⊗\) represent operations on encrypted values.
Types of Homomorphic Encryption
There are three main types of homomorphic encryption:
- Partially Homomorphic Encryption (PHE): Supports either addition or multiplication, but not both.
- Somewhat Homomorphic Encryption (SHE): Supports both addition and multiplication, but only for a limited number of operations.
- Fully Homomorphic Encryption (FHE): Supports an unlimited number of both addition and multiplication operations.
A Simple Example
Let's start with a simple example using the Paillier cryptosystem, which is a partially homomorphic encryption (PHE) scheme that supports addition operations on encrypted data. We'll use the phe
library in Python.
First, install the required library:
pip install phe
Now, let's write some Python code to demonstrate homomorphic encryption:
This example demonstrates: key generation, Encryption of user-input numbers, Homomorphic addition on encrypted values, and multiplication of one of the encrypted inputs by a scalar. Multiplication of two encrypted values is not supported by PHE. Output from above script,
Advanced Example
Now, let's explore a more powerful approach using Fully Homomorphic Encryption (FHE). We'll use the Concrete library, which is based on the TFHE (Fast Fully Homomorphic Encryption over the Torus) scheme.
First, install the required library:
pip install concrete-python
Now, let's create a simple example that performs basic operations on encrypted data:
This FHE example declares a function definition for addition and multiplication with the @fhe.compiler
decorator, then compiles for specific input set, generates the key, and finally run operations on the encrypted user inputs. The Concrete library handles the complex task of translating our Python function into FHE operations. This abstraction makes it much easier to work with FHE. The encrypt_run_decrypt
method handles the entire process of encryption, computation, and decryption.
Subtraction and Division
While addition and multiplication are the fundamental operations in homomorphic encryption, subtraction and division can also be performed, albeit with some caveats. Let's explore how these operations are handled in both PHE (using the phe
library) and FHE (using the concrete
library).
With Paillier
In the Paillier cryptosystem, subtraction is straightforward, but division is more complex and limited. Subtraction is basically performed by adding the negative of the second encrypted number. Division is not directly supported so we use a logarithm-based approximation, which requires decrypting values. This approach is not secure for real-world applications and is shown here for demonstration purposes only.
With Concrete
In FHE, we can perform both subtraction and division, but with some limitations due to the integer-based nature of most FHE schemes. Subtraction is directly supported in FHE.
Division in FHE is typically integer division (floor division) due to the integer-based nature of most FHE schemes. More complex operations like floating-point division would require additional techniques and approximations. In following example, we are using fhe.multivariate
which allows defining functions with multiple encrypted inputs, which is crucial for operations like division.
Applicability
PHE are useful for specific applications where only one type of operation is needed such secure voting systems where only addition is required or privacy-preserving data aggregation. FHE is applicable to a wide range of complex computation problems, including machine learning on encrypted data, secure multi-party computation, privacy-preserving measurement, etc.
Conclusion
Homomorphic encryption opens up exciting possibilities for privacy-preserving computation and data analysis. We've explored two different approaches: the partially homomorphic Paillier system and a fully homomorphic encryption system using the Concrete library.