Skip to main content

Homomorphic Encryption: a guide to advances in the processing of encrypted data

Homomorphic encryption potentially allows rival organisations to be able to collaborate on projects without fear, cloud computing will enter a new era and IT will Fully come of age. Here’s why.

 
We’ve been encrypting data for decades. Today, we routinely encrypt data – every time we send an email or shop online or access our bank accounts, for instance - so strongly that it is effectively impossible to steal. And that happens so quickly and automatically that we don’t even notice we’re are doing it.

So far, so good. But if we want to use that information, perhaps exporting it to a spreadsheet for analysis, we must first decrypt it.  And as soon we do that the entire set of data becomes vulnerable to unauthorised access and theft. That’s not a problem for the man in the street, but it’s a real stumbling block when it comes to sharing data at a corporate or governmental level.

The solution to this – to processing and sharing data while it is still protected by strong encryption -  lies in in the science of Homomorphic Encryption and its related technologies.

Here are some of the questions most frequently asked about Homomorphic Encryption, with their answers in plain English:
 

How would you explain Homomorphic Encryption to a layman?

There are a number of useful analogies. Let’s start by looking at ordinary encryption. Imagine taking all of your credit card statements and locking them into a safe, to which you have the only key. Your statements are now protected from prying eyes. This is what encryption does.

But what if you wanted to analyse your expenditure on groceries in the last 12 months? First you would have to unlock the safe and retrieve the statements. So now the documents are out in the open and they can be read by anyone. This is what decryption does.

The difference with Homomorphic Encryption is that you can create your report without taking the documents out of the safe.

To you, that’s a useful convenience. But to corporate business, governments and research institutes it opens almost unimaginable opportunities.

Note: the above analogy is usefully extended by Brian Hayes in his supremely readable ‘Alice and Bob in Cipherspace’ article (‘American Scientist’ 2012, Vol 100) in which he discusses the potential for two parties who distrust each other to collaborate while using the same set of encrypted data.
 

How will Homomorphic Encryption solve real-life issues?

The IT industry has been quick to develop cloud-based ‘Pay as you Go’ software, which removes the need for substantial capital investment.
 
Provided under the banner ‘Software as a Service’ (SaaS) Pay as you Go solutions can include highly sensitive applications such as accounting, HR, payroll processing, enterprise resource planning, customer relationship management, and more.

Unfortunately, the requirement to decrypt data before it can be processed means that such services are not fully secure even if the data is transmitted and stored in an encrypted format.  Homomorphic Encryption can help to solve this.
 

What is the history of Homomorphic Encryption?

Although some encryption technologies were already partly homomorphic, a plausible Fully homomorphic system was not described until 2009, when computer scientist Craig Gentry published his dissertation ‘Fully Homomorphic Encryption using ideal lattices’.

Although ground-breaking in its scope and novelty, Gentry’s scheme was fundamentally impractical because of the excessive computational time it required. Various refinements were swiftly proposed, though, and a new scheme was published by Gentry, Marten van Dijk, Shai Halevi and Vinod Vaikuntanathan the following year.

Additional refinements led to the development of more efficient second-generation homomorphic cryptosystems in 2011 and 2012, and two implementations are now available in open source libraries. Research continues.
 

Are there any practical applications for Homomorphic Encryption in its current state?

Yes. Although Fully Homomorphic Encryption is still in the research phase and without any practical applications, there are other technologies that can protect sensitive data during computation.

Most promising for the immediate to near future are the limited forms of HE, such as ‘Somewhat Homomorphic Encryption’, ‘Searchable Encryption’ and ‘Multi-Party Computation’. These can achieve some of what Fully Homomorphic Encryption can –  enough to be commercially viable – but without the drawback of crippling computational overheads.
 

How long will it take before Fully Homomorphic Encryption systems are in common use?

Many experts believe that it will be the year 2030 before we see the first Fully Homomorphic Encryption systems.
 

What are the main benefits of Fully Homomorphic Encryption?

Fully Homomorphic Encryption will overcome the security limitations of cloud computing, enabling highly secure applications, storage and services to be offered regardless of where the servers reside.

It will also empower safe inter-organisational and cross-border collaboration even when there is a lack of trust.
 

What impact does Homomorphic Encryption have on society?

In short, it makes international trade and co-operation possible between multiple parties even when there is no trust. To see why, we must first consider the rise of cloud computing.

The introduction of cloud computing has, at least logically, made the physical location of data servers irrelevant. A server farm in Germany can satisfy the needs of customers in America as easily as its customers in France.  Not every nation has the same data protection legislation, however.

The EU’s Safe Harbour Privacy Principles were introduced at the turn of the century to improve data security. It also made a provision for US companies to enter the programme in return for self-certifying their compliance with the Principles.

Effectively, this made it possible to transfer confidential data from the EU to the US, on the understanding that it would remain protected.

But in October 2001 George W. Bush signed The USA PATRIOT Act (‘P.A.T.R.I.O.T.’ is an acronym for ‘Uniting and Strengthening America by Providing Appropriate Tools Required to Intercept and Obstruct Terrorism’). This seemed to pave the way for America to intercept and retrieve data by whatever means necessary, effectively making a nonsense of the Safe Harbour Principles in those instances where US companies had opted in.

Ten years later, Gordon Frazer, MD of Microsoft UK went on public record with the comment:
 
"Cloud data, regardless of where it is in the world, is not protected against the Patriot Act."
 
This led to the Dutch Government refusing to accept contracts from any US cloud providers on the grounds that its data could not be guaranteed to remain confidential. A wider ban was also considered.

This mistrust between the US and the EU may or may not be well-founded. But the point is that Homomorphic Encryption eliminates the need for trust. The data is always encrypted. Only the outputs are in plain text.
 

What can Homomorphic Encryption do that other encryption technologies can’t?

Homomorphic encryption allows encrypted data to be processed while it is still in an encrypted state. If data is encrypted by any other means it must first be decrypted before processing, and this renders it vulnerable to unauthorised access.
 

Why will it take so long for Fully Homomorphic Encryption systems to be mainstream?

The processing power to accomplish Fully Homomorphic Encryption is immense. When first proposed it was shown to take billions of times longer than conventional encryption. Now it is ‘only’ millions of times longer but the problem will clearly not be solved by computing power alone. More efficient algorithms are needed.
 

What are the alternatives to Fully Homomorphic Encryption that we can use today?

Searchable Encryption and Multi-Party Computation can do some of what Fully Homomorphic Encryption has the potential for but without the crippling processing overheads. These Somewhat Homomorphic Encryption technologies will continue to advance in scope and commercial viability.
 

What are some real life applications for Fully Homomorphic Encryption?

The only limit is our imagination. Fully Homomorphic Encryption has the potential to empower worldwide cloud computing and to be the founding technology that enables inter-organisational and cross-border collaboration.

For example, hospitals and universities collect and store masses of valuable data. What if they could share that however they wanted to without compromising data security – even if they are in different countries? What if they could fully collaborate even if they don’t trust each other?

Credit card companies, banks, research organisations, educators, data miners and anyone who wants to be able to share data without losing control of it could one day use Homomorphic Encryption without so much as a second thought.

Before that happens, though, there are some daunting computational challenge to be overcome.
 

What is Thales’s involvement in helping to develop Homomorphic Encryption and related technologies?

Thales has a long standing commitment to developing and providing state-of-the-art e-security and encryption technology to customers in the security, military and commercial sectors. Thales is also deeply involved in the  Homomorphic Encryption Applications and Technology (HEAT) Project.
 

What is the HEAT project?

Thales is working with Europe’s leading researchers in Homomorphic Encryption as part of the HEAT project, which aims to produce a step change in the efficiency and applicability of Homomorphic Encryption.
Rather than focus on the long-term objectives of Fully Homomorphic Encryption, HEAT is exploring what can be done with Somewhat Homomorphic Encryption over a timescale of five years.
 

How will the HEAT project benefit society?

The proposed outputs of HEAT include an open source software library to support applications that wish to use Homomorphic Encryption, and making the research available to a wide audience of developers.

As part of the project, Thales has also been investigating the use of Homomorphic Encryption in satellite scenarios, with a special focus on the data processing of imaging products.
 

Where does Thales fit in the Homomorphic Encryption sector?

With a presence throughout the entire security chain, Thales is one of the world leaders in cyber-security products and solutions for critical state and military infrastructures, satellite networks and industrial and financial companies.
 
Written by Adrian Waller
Chief Technical Consultant