Introduction to Homomorphic Encryption

24 Dec 2020

Homomorphic Encryption – Basics

TagsCSPs, Encryption, FIPS, GDPR, Homomorphic encryption, Masking, Tokenization

Read time: 5 minutes 2 seconds

Organizations nowadays are storing and performing computation of the data on the cloud instead of handling themselves. Cloud Service Providers (CSPs) provide these services at an affordable cost and low maintenance. But to ensure compliance and retain privacy, organizations need to transfer the data in an encrypted format, which does ensure the confidentiality of the data. However, once the data reaches the cloud, the CSP has to decrypt the data to perform operation or computation.

Decrypting the data to the CSP loses the data’s confidentiality, which may concern the organization for not being compliant to data privacy regulations such as GDPR, FIPS, PCI DSS, CCPA, etc.

What is Homomorphic Encryption?

Homomorphic Encryption makes it possible to do computation while the data remains encrypted. This will ensure the data remains confidential while it is under process, which provides CSPs and other untrusted environments to accomplish their goals. At the same time, we retain the confidentiality of the data.

Like other asymmetric encryptions, homomorphic encryption is encrypted using a public key and can only be decrypted by the respective private key. But while the data is encrypted, operations can be performed on the data, which retains confidentiality, and helps organizations achieve compliance even when using untrusted environments.

Why do we need Homomorphic Encryption?

Data creation has been increased tremendously in recent times, sent/stored in multiple environments belonging to other parties such as CSPs or other third-party organizations. From startups to big organizations, everyone uses CSPs to store or process data, where tools such as Big Query are used for data processing.

CSPs do provide some control over the data customers store in their environments, but those controls depend on CSPs. While users can encrypt and store data on CSPs, conducting computation on the data would be limited. Thus, standard encryption is only limited to data storage alone and does not provide any meaningful analysis that can be used.

To be able to process data while ensuring data privacy, researchers are focusing on privacy-enabled computation. Homomorphic Encryption (HE) is one of the promising approaches in this direction.

Types of Homomorphic Encryption

Homomorphic Encryption allows computation on encrypted data without decrypting. Mathematical operations that can be performed on the ciphertext differentiates the types of Homomorphic Encryptions.

They are mainly of two types:

Partial Homomorphic Encryption (PHE) (supports either addition/multiplication, but not both)
Fully Homomorphic Encryption (FHE) (supports both addition and multiplication)

Partial Homomorphic Encryption such as RSA and Paillier cryptosystems does support additive and multiplicative homomorphism. In 2009, Craig Gentry proposed an FHE scheme based on lattices for the first time. An FHE scheme usually supports addition and multiplication ciphertexts as follows:

HE(a+b) = HE(a) + HE(b) and HE(a*b) = HE(a) * HE(b)

Addition/Multiplication of plaintext is equal to the addition/multiplication of two ciphertexts.

Applications

HE makes it possible to achieve privacy-preserving computation in almost every scenario. Some of those include:

Private Search
Search Engines rely on ads to generate revenue. While serving searches to their users, search engines get a better view of the user’s preferences. This does help them provide customized ads for the user they serve. Homomorphic encryption does solve the problem. Search Engines can crawl the encrypted data, serve them as the algorithm is designed to, and serve the user with encrypted data. The user would get the desired result, while the search engines remain unaware of the data requested, which keeps preferences private and more challenging to serve ads.
Encrypted Databases
In any cyber-attacks, databases are often the most crucial infrastructure to protect. It may cost an organization a considerable fine in compliance and have a bad reputation to go along. Several security measures are kept in place, which includes Encrypting a database. In case of a breach, the database would remain encrypted and decrypted by a specific key, preventing unauthorized access to the database.
If we employ the standard encryption, the encrypted database will not allow any operations on the records. We can use deterministic encryption, order-preserving encryption, and order-revealing encryption to support the encrypted database. But these would lead to leakages, such as memory access patterns and search patterns.
With Homomorphic Encryption, it is possible to encrypt data in the database to obtain confidentiality, while we can also perform operations and computation on the data. Only authorized users with the key to decrypt the database can access the data in the database.
Computation on Cloud
Cloud Computing saves money and reduces maintenance that an organization needs to maintain its infrastructure for the services offered. Organizations can lease cloud infrastructure on a need basis to run their applications. CSPs also provides the ability to scale up according to the load on the infrastructure. Since the service providers typically manage clouds, organizations require the CSP to be compliant and get better privacy and security for their organization.
If we choose to keep the data encrypted on the cloud and perform operations on those encrypted data, it will make CSP’s compliance and security measures less relevant. CSPs can maintain the infrastructure that store and process the encrypted data, while never accessing the plaintext.

Limitations and Drawbacks

Homomorphic Encryption computations are slow, and only a finite number of operations can be performed on the encrypted data. FHE based computation is at least 106 times slower than computation on the plaintext.

Homomorphic Encryption is also not feasible for multiple users. If we have a database, which we would need multiple users to access, we would need to create a separate database for every user, which is encrypted using the user’s public key. This would become impractical if the number of users increases or the size of the database increases.

Conclusion

Homomorphic Encryption in the current state is computationally expensive and practically inefficient. It can certainly be used to encrypt data, while we can perform different computations on the data. HE enables privacy-preserving computation, which helps us work with untrusted environments while maintaining the data’s confidentiality. Check out Format Preserving Encryption if interested in privacy-preserving computations.