Homomorphic encryption algorithms are a type of encryption algorithm designed to allow mathematical operations to be performed on encrypted data. This is an extremely useful property with a number of applications.
Introduction to Homomorphic Encryption
Data can be in one of three states: at rest, in transit, and in use. Most encryption deals with the first two of these. The reason for this is that data at rest or in transit is not actively changing. It has the same value when it’s decrypted as it did when it was encrypted.
Data in use, on the other hand, doesn’t have this property. Almost all mathematical operations on ciphertexts would change the value of the corresponding plaintext. Ensuring that the plaintext changes in the “right way” is difficult.
Encryption algorithms are designed to destroy any relationships between plaintext and the corresponding ciphertext. A good encryption algorithm produces a ciphertext that is indistinguishable from a random number. The only way to determine which plaintext corresponds to a certain ciphertext is to use the proper key to decrypt it.
The ability to perform mathematical operations on encrypted data means that there needs to be a relationship between plaintexts and ciphertexts. It needs to be possible to add or multiply two ciphertexts together and have the result be the same as performing the same operation on the two plaintexts and then encrypting it.
At the same time, this relationship needs to be implemented in such a way that it’s hidden from an observer. If watching mathematical operations on ciphertexts reveals information about the corresponding plaintexts, then the encryption is broken.
Achieving these mutual goals of strong encryption and the ability to perform mathematical operations on ciphertexts and get the right answer is really difficult. Homomorphic encryption algorithms are ones that have accomplished this goal.
Applications of Homomorphic Encryption
Homomorphic encryption is a big deal because it makes it possible to perform calculations on encrypted data. This means that data processing can be outsourced to a third party without the need to trust the third party to properly secure the data. Without the proper decryption key, the original data can’t be accessed.
This ability to perform processing on encrypted data has the potential to solve many major business challenges faced by companies across all industries.
Supply Chain Security
Most companies have trusted third parties that they rely upon as part of their business. These contractors, vendors, etc. often need access to the company’s sensitive and proprietary data in order to do their jobs.
Recent events have demonstrated the risks of insecure supply chains and how cybercriminals will target the weakest link in the chain to achieve their objectives. This means that entrusting sensitive data to a partner may leave an organization open to an expensive and damaging data breach.
Homomorphic encryption can help a company to protect itself against these supply chain risks. If all data provided to trusted third parties for processing is encrypted, then a breach of that data poses no risk to the company. This allows an organization to outsource critical data processing with minimal risk.
Regulatory Compliance
In recent years, the data protection regulatory landscape has grown increasingly complex. New regulations like the EU’s Data Protection Regulation (GDPR) have provided data subjects with new rights and placed additional responsibilities and restrictions on businesses.
One GDPR rule that many businesses are struggling with is the requirement that the data of EU citizens remains within the EU or in countries or companies with equivalent data security standards. The Schrems II decision in 2020 invalidated one of the main ways in which EU-US data flows were justified under GDPR, which caused problems for many US companies with EU citizens.
Laws like the GDPR clearly state that their requirements do not apply to encrypted data. With homomorphic encryption, a company could potentially store and process data on systems outside the EU and then only decrypt it on servers in locations that comply with GDPR requirements.
Private Data Analytics
Data analytics is how many companies make their money. Businesses like Facebook are able to provide “free” services by collecting information about their users, processing it, and selling this information to third parties for targeted advertising.
However, this monetization of personal data is controversial. Many people are unhappy with companies building in-depth profiles about them without any visibility and control over the data collected and how it is used.
Homomorphic encryption provides a potential solution to this problem. With homomorphic encryption, a company like Facebook could perform the data analytics that it needs without the ability to view or access the original data. If encryption keys are controlled by users, this provides the potential for private, targeted advertising.
Types of Homomorphic Encryption
The goal of homomorphic encryption is to create an encryption algorithm that allows an infinite number of additions or multiplications of encrypted data. At the end of the process, the result should be the ciphertext that would be produced if the same operations were performed on the corresponding plaintexts and the result was encrypted.
The problem is that designing such an encryption algorithm is really hard. As a result, there are a few different “types” of homomorphic encryption that describe how close a particular algorithm is to that final goal.
Partially Homomorphic Encryption
Partially homomorphic encryption algorithms allow a certain operation to be performed an infinite number of times. For example, a particular algorithm may be additively homomorphic, meaning that adding two ciphertexts together produces the same result as encrypting the sum of the two plaintexts.
Partially homomorphic encryption algorithms are relatively easy to design. In fact, some common encryption algorithms are partially homomorphic by chance.
For example, the RSA algorithm is multiplicatively homomorphic. The reason for this is that encryption in RSA is based on exponentiation: C = (m^x) (mod n) where m is the message and x is the secret key.
The rules of exponents say that (a^n)(b^n)=(ab)^n. This means that multiplying two ciphertexts encrypted with the same key is equivalent to raising the product of the plaintexts to the power of the secret key. Therefore, RSA is multiplicatively homomorphic.
Somewhat Homomorphic Encryption
The next step up from partially homomorphic encryption is somewhat homomorphic encryption. A somewhat homomorphic encryption algorithm allows a finite number of any operation rather than an infinite number of a particular operation.
For example, a somewhat homomorphic encryption algorithm may be able to support any combination of up to five additions or multiplications. However, a sixth operation of either type would create an invalid result.
Somewhat homomorphic encryption algorithms are an important stepping stone on the way to fully homomorphic encryption. It’s more difficult to design an algorithm that supports both addition and multiplication (even for a set number of operations) than it is to create one that allows infinite addition or multiplication of ciphertexts.
Fully Homomorphic Encryption
Fully homomorphic encryption is the holy grail of homomorphic encryption. A fully homomorphic encryption algorithm allows an infinite number of additions or multiplications of ciphertexts while still producing a valid result.
Fully homomorphic encryption algorithms exist today. In fact, the first fully homomorphic encryption algorithm was invented in 2009 by Craig Gentry. Since then, other algorithms have been developed that improve on this original algorithm.
What’s Holding Back Homomorphic Encryption?
Fully homomorphic encryption can solve a variety of major business challenges. The fact that it exists means that, in theory, everyone should be using it.
So why aren’t they?
The problem with fully homomorphic encryption today is that it isn’t efficient. Meeting the requirements of full homomorphism (i.e. allowing ciphertexts to be added or multiplied an infinite number of times without messing up the result) means that these algorithms are slow and can have very high storage requirements.
For example, IBM released an improved version of its HElib C++ library for homomorphic encryption in 2018. This version is 25-75 times faster than the previous version, which was 2 million times faster than the original version, released three years earlier.
The problem is that the original version performed mathematical operations about 100 trillion times slower than performing those same operations on the corresponding plaintexts. This means that the new and improved version is still about a million times slower than plaintext operations on average.
A factor of a million slowdown is pretty significant. A calculation that would take a second to perform using plaintexts would take an average of 11.5 days to perform using the 2018 version of HElib.
Obviously, this sort of slowdown is an unacceptable tradeoff for businesses that would otherwise be interested in homomorphic encryption. However, a speedup of about 100 million times over 3 years is pretty impressive. While homomorphic encryption may not be a viable option today, it’s possible that could change in the near future.
