



URL copied!
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 postquantum 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:
 (a’) => (b’) is our conversion function
 (a’ ) + 1 => (b’ + 1)
 (a’) => (b’) + 1
 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:
 I encrypt my data,
 process that encrypted data,
 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 structurepreserving 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 postquantum 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 oneway or ‘trapdoor’ [8] functions to generate our keys. These ‘trapdoor’ functions are socalled 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^{2} + 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^{2} + 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^{2} + 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 NPHard problem we can also say that RWLE is an NPHard 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 quantumresistant 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 onsite, 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 highperformance 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 widescale 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
 https://en.wikipedia.org/wiki/Homomorphism
 https://en.wikipedia.org/wiki/Homomorphic_encryption
 https://en.wikipedia.org/wiki/Field_(mathematics)
 https://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Clock_group.svg/440pxClock_group.svg.png
 https://en.wikipedia.org/wiki/Isomorphism
 https://ds055uzetaobb.cloudfront.net/brioche/uploads/53gy1Ho70ohomo3newpage1resized.png?width=2400
 https://link.springer.com/content/pdf/10.1007/9783642300578_1.pdf
 https://en.wikipedia.org/wiki/Trapdoor_function
 https://en.wikipedia.org/wiki/Integer_factorization
 https://en.wikipedia.org/wiki/Shor%27s_algorithm
 https://en.wikipedia.org/wiki/Ring_learning_with_errors
 https://ico.org.uk/fororganisations/guidetodataprotection/guidetothegeneraldataprotectionregulationgdpr/keydefinitions/controllersandprocessors/
 https://aws.amazon.com/cloudhsm/
 https://aws.amazon.com/ec2/nitro/nitroenclaves/
 https://en.wikipedia.org/wiki/Ring_(mathematics)
 https://en.wikipedia.org/wiki/Ring_learning_with_errors
 https://en.wikipedia.org/wiki/NPhardness
 https://eprint.iacr.org/2020/304.pdf
 https://academic.oup.com/comjnl/advancearticleabstract/doi/10.1093/comjnl/bxab154/6408803?redirectedFrom=fulltext
Top Insights
Manchester City Scores Big with GlobalLogic
AI and MLBig Data & AnalyticsCloudDigital TransformationExperience DesignMobilitySecurityMediaTwitter users urged to trigger SARs against energy...
Big Data & AnalyticsDigital TransformationInnovationRetail After COVID19: How Innovation is Powering the...
Digital TransformationInsightsConsumer and RetailTop Authors
Top Insights Categories
Let’s Work Together
Related Content
5 Trends & Takeaways from Google Cloud Next
Executives, decisionmakers, technical experts, and Google Cloud partners converged at Google Cloud Next to explore cuttingedge innovations and industry trends. GlobalLogic was there, speaking about modernization strategy and delivering a Cube talk on Intelligently Engineering the Next GenAI Platform we are building for Hitachi. Among the buzz at GCN 2024, using GenAI for customer success … Continue reading Homomorphic encryption – hard to say, even harder to break. →
Learn More
IIoT: The Future of Manufacturing
Evolution of Industrial Innovation: How IIoT Will Impact Manufacturing in the Future? The Manufacturing Industry is entering a new era thanks to the Industrial Internet of Things, or IIoT. This revolutionary technology is dramatically reinventing manufacturing with the integration of digital technology into processes that enhance output quality, reduce costs, and increase productivity. IIoT … Continue reading Homomorphic encryption – hard to say, even harder to break. →
Learn More
Share this page:




URL copied!