Homomorphic encryption – hard to say, even harder to break.

This blog discusses homomorphic encryption. What it is, how it works, and how it could be applied. We investigate how it deals with encryption in a post-quantum world and consider how it can address headaches surrounding security compliance.

What is homomorphic encryption?

The word homomorphic comes from the Greek ‘Homo’ meaning ‘same’ and ‘Morphe’ meaning ‘shape’. In mathematics, this refers to a mapping between two algebraic structures that is preserved through operations [1].

For example, if I have two structures of type A and B, with a function to convert between the two, and create instances a’ and b’ then we can say:

1. (a’) => (b’) is our conversion function
2. (a’ ) + 1 => (b’ + 1)
3. (a’) => (b’) + 1
4. We have homomorphism if (b’ + 1) is equal to (b’) + 1 as we have performed the same operation on both structures

For homomorphic encryption, this means that if:

1. I encrypt my data,
2. process that encrypted data,
3. decrypt my data,

The result will be the same as if I had performed that process on my original data [2].

[6]

There are several ways to ensure we achieve homomorphism in our structures, for current homomorphic encryption this comes from the use of finite fields.

What is a finite field?

In mathematics, a field is defined as “a set on which we can perform addition, subtraction, multiplication and division”. [3] An example of this is the set of natural numbers, numbers you can count such as 1,2,3… etc.

If we want to make this into a finite field, we need to make it finite, the set of real numbers keeps heading to ‘infinity and beyond’ so we just need to put a limit on how many elements are in our set.

The simplest way to do this is with a modulus of n, for example, if we wanted to represent a clock as a finite field, we would use modulo where n = 12.

[4]

In this example, we started at 9 o’clock and we added four hours, we end up at 1 o’clock because as soon as we pass 12, we restart from the beginning. This would be the same for any of our other operations. The finite part is that we only have 12 numbers to choose from.

The only hiccup this example has, which would make George Orwell very pleased, is our clocks need to strike 13 as finite fields can only be created this way if n is a prime number. Not important for the example, but in the interest of completeness it’s worth mentioning.

A finite field is isomorphic [5], which is a specific type of homomorphism, with ‘iso’ coming from the Greek word ‘equal’. It is defined as a structure-preserving mapping between two structures of the same type and can be reversed with an inverse mapping. Put simply, we need to have a function for converting between Structure A and Structure B.

This is perfect for us; the inverse mapping will be our encryption/decryption algorithms.

Why is homomorphic encryption important?

Post Quantum Encryption

Quantum computers are an interesting topic for another post, but the key thing to note is they are efficient at solving specific types of problems in a way conventional computers are not. The concept of post-quantum encryption is as the name suggests, how we can achieve strong encryption which is difficult for quantum computers to break.

Typically for algorithms such as RSA and AES, we use large prime numbers in a one-way or ‘trapdoor’ [8] functions to generate our keys. These ‘trapdoor’ functions are so-called because going in one direction is easy, but the other way is much more difficult.

These generally relied upon the difficulty of ‘Prime factorisation’ [9], the process of decomposing a number into its prime factors. For example, the number 10 becomes 2 and 5. The problem is that quantum computers are really good at solving this problem, using a method known as ‘Shor’s Algorithm’ [10] which to oversimply takes advantage of doing many calculations simultaneously and then arrives at the result magnitudes faster than a classical computer.

But homomorphic encryption bases its difficulty on ‘Ring learning with errors’ [11].

What is Ring Learning with Errors (RLWE)?

The definition for this problem is “RLWE is more properly called learning with errors over rings and is simply the larger learning with errors (LWE) problem specialised to polynomial rings over finite fields”. [16]

For this let’s start at the beginning, what is a ring?

In this case, mathematics would describe a ring as “a set with two binary operations, addition and multiplication” [15]. There are a few other requirements, but to keep this simple we won’t be including them.

To create a polynomial ring, we form a set consisting of only polynomials whose coefficients are from one other ring. Polynomials are the equations we remember from school that look like “ax² + bx + c”, where a, b, and c are the coefficients.

So how do we make sure these coefficients are from another ring? Well, as it turns out the finite field from before satisfies our definition for a ring, so we just need to situate our problem in the finite field, and the requirement is sustained.

We have the “R”, now we just need to figure out the “LWE”.

First, let’s construct a field. We can use the clock example from before. That would mean that our value q = 12. We will be calling it Field q (F_q for short), so when you read that just think about the numbers on a clock.

Next, we need to define an infinite polynomial ring for F_q. This step is quite simple, we are just going to give it a name.

Since we are going to be using “x” as our variable name, the infinite ring will be written as F_q[x] for short. We can think of this as all the polynomials that could possibly be made only using our finite field, e.g. “2x² + 10x” as two and ten appear on a clock.

Because our maths isn’t going to work with an infinite set of polynomials, we are going to make it finite the same way we made a finite field, by using a modulo. In this case, we are going to use an irreducible polynomial. This is just a fancy way of saying a polynomial we can’t factor down any further. For example, “2x² + 10x” can be factored into “2x” and “x + 5” which are irreducible.

Much like how we had q = 12 to create a finite field, we are going to have a function Φ(x) = {some irreducible polynomial}. The same principle but just with polynomials instead of integers, and we end up with a finite quotient ring we are going to write as F_q[x] / Φ(x).

Hopefully, the previous four paragraphs weren’t too daunting. The reason for their inclusion is because those definitions get used a lot in the problem statement. At this point it is worth noting there are a few other caveats, but for the sake of simplicity, we are going to omit them.

Now that we have that out of the way we can finally define our problem:

• Let a[x] be a set of random and known polynomials from F_q[x] / Φ(x)
• Let e[x] be a set of small, random, and unknown polynomials from F_q[x] / Φ(x)
• Let s(x) be a small unknown polynomial from F_q[x] / Φ(x)
• Let b[x] = (a[x] * s(x)) + e[x]

The problem from RLWE we are going to use is known as ‘the Search problem’ and is defined as, “Given a list of pairs from a[x] and b[x] can you find s(x)”.

Without knowing e[x] this is a herculean task and is computationally infeasible. But if we do know e[x], because we were the ones who generated it in the first place, the problem is trivial. Making it perfect for cryptography.

So, we can make private keys from pairs of s(x) and some value from e[x] we can call “e”, and have the public key be a value from a[x] we can call “a” and t(x) = (a * s(x)) + e.

How do we know that it’s difficult?

The simple answer here is that we have proof for the Smallest Vector Problem (SVP) and we can convert RLWE into SVP fairly easily. Because we know for certain that SVP is an NP-Hard problem we can also say that RWLE is an NP-Hard problem [17].

These problems are at least as hard to solve as the most difficult problems in NP (Nondeterministic polynomial time complexity). It has not been shown that quantum computers are able to solve these problems significantly better than classical computers. So long as this is the case, RWLE is a good basis for quantum-resistant cryptography.

Compliance

From a business perspective, there will be someone in every company whose job is related to information and data. This may be an Information Security Officer or something similar, who under recent EU guidelines must make sure the company is compliant with current regulations.

This is especially difficult when it comes to things like Personally Identifiable Information (PII), or sensitive information like financial statements. For now, let’s just refer to these things as sensitive information.

Many businesses process the sensitive information of other companies, be that working on medical research or aggregating user data. Under GDPR they would be known as a “Processor” [12]. While the compliance you need to meet is not as high as the “Controller” of that information, you will need to safeguard it from breaches in security.

Under the current status quo, this means going through the effort of encrypting the data at rest and in transit. Then when it comes to processing the data, it needs to be decrypted, which means that all processing of sensitive data needs to be protected. The current solution is the use of Hardware Security Modules [13] or Private Enclaves [14] specifically designed to limit access to unencrypted information.

And beyond that, there are the considerations over whether this should be done on-site, in which case you are responsible for the security of your own systems and keeping them up to date. Or you are processing on the cloud and losing governance of that data to a 3^rd party.

All these factors make architecture more complex, delivery slower, and inflates the cost of providing our services. The bottom line is: things become more expensive.

When we introduce homomorphic encryption life becomes simpler. We get strong security, developers can focus on adding value, architects can focus on scalable and reliable solutions, and the information officers can sleep easy knowing that much of the compliance surrounding sensitive information is taken care of by default.

Problems with homomorphic encryption

Hey, remember when we were talking about finite fields earlier. We have an issue in that they are finite, as in they can’t keep going on forever. If we look at our clock example again, there isn’t a whole lot we can do with just 12 numbers to work with. Once I get beyond 12, I go back to 1 and then forwards from there. Now how can I tell if the number I want is 1, or 13, or 25, or 61917364225.

In the real world, we use much larger fields which means that addition is normally fine but if we continually use multiplications, we are eventually going to hit a ceiling and wrap around. We do have a solution which is called ‘Bootstrapping’ [7] which is running something in parallel to keep track of noise generated by operations. The issue is it’s very expensive to run.

Even in broader terms, homomorphic encryption is a heavier computation than public key or private key encryption. This makes the current system incorporating homomorphic encryption slow compared to alternatives, preventing it from being used in high-performance industries.

The largest issue however is when we consider multiple users, which is to say how can multiple users have access to the same information. Because the data is never decrypted in a server, it can only be returned to the person who originally sent it as they have the only decryption key. You would need to share the key, which comes with its own set of problems around security. Or we would need to store a separate version of the data for every user and use their keys to encrypt it, while also keeping everything in sync, which is incredibly complex.

Although there is research into multikey systems, at the time of writing I was unable to find sufficient evidence that the problem has been solved, but it does appear promising [18][19].

Conclusion

In summary, I believe homomorphic encryption has a lot of potential to simplify how we secure our data and give greater protections for our privacy as new technologies emerge. But before we all get too excited it has several drawbacks which need to be fixed before wide-scale adoption can be considered.

****

About the Author

Fraser Brown is one of GlobalLogic's newest Delivery Consultants. Before joining us, he worked for a year as a Software Developer, specialising in cloud delivery and security. He is looking forward to getting involved in project work and delivery quality for GlobalLogic’s clients.

***

Appendix

1. https://en.wikipedia.org/wiki/Homomorphism
2. https://en.wikipedia.org/wiki/Homomorphic_encryption
3. https://en.wikipedia.org/wiki/Field_(mathematics)
4. https://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Clock_group.svg/440px-Clock_group.svg.png
5. https://en.wikipedia.org/wiki/Isomorphism
6. https://ds055uzetaobb.cloudfront.net/brioche/uploads/53gy1Ho70o-homo3-new-page1resized.png?width=2400
7. https://link.springer.com/content/pdf/10.1007/978-3-642-30057-8_1.pdf
8. https://en.wikipedia.org/wiki/Trapdoor_function
9. https://en.wikipedia.org/wiki/Integer_factorization
10. https://en.wikipedia.org/wiki/Shor%27s_algorithm
11. https://en.wikipedia.org/wiki/Ring_learning_with_errors
12. https://ico.org.uk/for-organisations/guide-to-data-protection/guide-to-the-general-data-protection-regulation-gdpr/key-definitions/controllers-and-processors/
13. https://aws.amazon.com/cloudhsm/
14. https://aws.amazon.com/ec2/nitro/nitro-enclaves/
15. https://en.wikipedia.org/wiki/Ring_(mathematics)
16. https://en.wikipedia.org/wiki/Ring_learning_with_errors
17. https://en.wikipedia.org/wiki/NP-hardness
18. https://eprint.iacr.org/2020/304.pdf
19. https://academic.oup.com/comjnl/advance-article-abstract/doi/10.1093/comjnl/bxab154/6408803?redirectedFrom=fulltext