Homomorphic Encryption: How It Works

Like any encryption, homomorphic encryption is a method to make data confidential or secret. What sets it apart from other types of encryption is that the data, once encrypted, can be ‘worked with’ (have mathematical operations performed on it) all while retaining its secrecy. 

This is exciting because encrypted data is usually meaningless unless decrypted, so if you wanted to share data with someone else, you either had to trust them and allow them to see the decrypted data, or you couldn’t do any shared work on that data. 

With homomorphic encryption, however, you can share encrypted data with another party and they can do something with it, without ever knowing what the underlying unencrypted data was.

What is homomorphic encryption?

So, what exactly does homomorphic mean?  

I’m going to try really hard not to get into excited maths nerd mode. Homomorphic comes from the Greek words for ‘same structure’. It means that I can perform operations on things, and the structure is preserved after a mapping.

In maths speak, “a group homomorphism is a map between groups that preserves the group operation.” 

But that’s a bit icky, so let’s take a really simple (flawed) example.

Example 

Say I have two numbers. I add them together, and take the last digit. This would give me the same result as taking the last digit of both numbers and then adding them together*.

(**Yes, I hear you saying, “What if those numbers are 28 and 19? Then you get 17 instead of 7.” You’re right, and I know that it’s a flawed example, but I’m trying really, really hard to stay away from group theory. So, please assume the two numbers do not add to more than 10… and let me know if you have a better example. :)

These operations I can perform are addition, multiplication, or both. If you take my flawed example, you’ll see it works with multiplication too. If you’ve heard terms like ‘partially homomorphic’ and ‘fully homomorphic’ encryption, that’s what the difference is - which operations you can perform on the data where the mapping still works.

Types of homomorphic encryption

The fundamental difference between the different types is the frequency of mathematical operations that can be performed on the ciphertext.

• Partially Homomorphic Encryption (PHE). In PHE, ‘partially’ means that only a single mathematical function can be performed on encrypted values. So only one action — either addition or multiplication — can be performed an unlimited number of times on the encrypted data.
• Somewhat Homomorphic Encryption (SHE). ‘Somewhat’ is more general than PHE in that it supports homomorphic operations with additions and multiplications. However, only a limited number of operations can be performed on the encrypted data.
• Fully Homomorphic Encryption (FHE). Where PHE and SHE have limited operations, fully homomorphic encryption has the capability of using both operations, addition and multiplication, with no limit on the number of times they’re performed on the encrypted data.

Homomorphic encryption schemes

If you’re a cryptography enthusiast, you likely already know one partially homomorphic scheme: RSA. This works with multiplication, because encryption works by raising the message to an exponent, described in words and notation as follows:

Ciphertext = secret message raised to the power of publicly known encryption exponent, all taken modulo n (which is the multiplication result of two well-chosen, large prime numbers).

Or,

C1 = (m1^e) (mod n)

If you perform the same operation on a different message, let’s call it message 2 or m2, you get:

C2 = (m2^e) (mod n)

Multiplying the two cipher texts, C1 and C2, gives you:

(m1^e) (mod n) ✕ (m2^e) (mod n)

With some rearranging as follows:

(m1^e) (mod n) ✕ (m2^e) (mod n) = ( (m1^e) ✕ (m2^e) ) (mod n) =  ( (m1 ✕ m2) ^e) (mod n)

We end up with the result that encrypting and then multiplying the messages gives the same result as doing those operations in reverse (multiplying the messages and then encrypting them). Therefore, RSA is partially homomorphic, with the operation of multiplication.

When to use homomorphic encryption: it's not for most things

However, don’t rush out to use RSA on all your data and declare yourself a homomorphic genius. It’s slow and expensive relative to other encryption methods (it’s not a lightning-fast AES), which is why we use RSA to encrypt small pieces of data, like keys, rather than whole blocks of data (which are large).