Homomorphic Encryption is a promising cryptographic technique for keeping data private. In this post I give a short a simple summary of Homomorphic Encryption including a clear definition with an example use case in cloud computing.
I assume you are already familiar with basic Encryption/Decryption and have a basic understanding of data processing.
Homomorphic Encryption has received a lot of interest recently due to the high availability of cloud computing environments. It is an area which has been researched for decades, but new breakthroughs are still being made. First I will give a basic definition:
An encryption scheme where \(E\) is an encryption function and \(D\) is a decryption function is called additively homomorphic if for any 2 inputs \(x_1, x_2\) we have \(E(x_1 )⊕ E(x_2 )=E(x_1+x_2 )\). It is multiplicatively homomorphic if \(E(x_1 )⊗ E(x_2 )=E(x_1×x_2 )\). Here the symbols \(⊕\) and \(⊗\) just mean there is some fixed algorithm you can perform to achieve the equalities with any inputs. An encryption scheme is called fully homomorphic if it is both additively and multiplicatively homomorphic.
To give you some examples, the RSA and Elgamal cryptosystems are multiplicatively homomorphic, and the Paillier cryptosystem is additively homomorphic.
In 1978 the question was asked whether a fully homomorphic encryption scheme actually exists, but it took until 2009 for the first one to be found. It was found by the computer scientist Craig Gentry, who has since made many more breakthroughs in the area.
Now I will explain how this can be applied to a real world problem:
Suppose a company is collecting some data and they want to process the data, but they don’t have enough computing power or time available. Over the last decade cloud technology has become the most common solution to this problem. Large tech companies like Amazon, Microsoft or Google provide cloud services where you can rent as much computing power as you need.
But, this has its drawbacks. It introduces a big problem with data privacy since transferring the data to a cloud service provider is effectively giving it to a 3rd party. With new data regulations like GDPR this might not be an option legally (or morally) for the data collector.
Luckily, most data processing only requires simple operations like addition and multiplication applied a large number of times. Therefore fully homomorphic encryption provides a solution to this problem. Before sending the data to the cloud service, the data can be encrypted by the client, i.e. they send data in the form \((E(x_1 ),E(x_2 ),…,E(x_n ))\). This means the cloud service provider cannot extract information from the encrypted data as it looks almost random so the client is not breaking any rules or laws. Then the cloud service can apply the \(⊕\) and \(⊗\) operations to the data, in the place of addition and multiplication to obtain for example:
$$(E(x_1 )⊕ E(x_2 ))⊗ E(x_3 )=E((x_1+x_2)×x_3 )$$
The result still looks random, but when sent back to the client it can be decrypted to give the correct answer, \(D(E((x_1+x_2 )×x_3 ))=(x_1+x_2 )×x_3\).
In fact, the client doesn’t even need to store the data themselves before sending it. Rather than using a local database, they could use a remote database in the cloud where the data can be stored in an encrypted form to make the process even more efficient.
The encryption and decryption functions are usually easy to compute so the client doesn’t need much processing power. Some cloud service providers have already released libraries for this. For example, take a look at Microsoft's SEAL library, released in December 2018.
However there are still improvements to be made. For the cloud service the operations \(⊕\) and \(⊗\) are much harder to compute than regular addition and multiplication. In many cases, cloud services can still provide enough computing power to handle this. But improving these time complexities is a big area of active research.
Homomorphic encryption also suites a range of other use cases. For example, it is the basis of many Secure Multiparty Computation protocols, and it could also be combined with Trusted Execution Environments like Intel SGX.
Data privacy is becoming increasingly important as data is being collected and shared on a huge scale. Privacy preserving techniques like homomorphic encryption might not solve this problem entirely, but in many cases they can form a large part of the solution.
I plan on releasing some posts in the future on similar topics, so please subscribe if you are interested.
Homomorphic Encryption is a promising cryptographic technique for keeping data private. In this post I give a short a simple summary of Homomorphic Encryption including a clear definition with an example use case in cloud computing.
I assume you are already familiar with basic Encryption/Decryption and have a basic understanding of data processing.
Homomorphic Encryption has received a lot of interest recently due to the high availability of cloud computing environments. It is an area which has been researched for decades, but new breakthroughs are still being made. First I will give a basic definition:
An encryption scheme where \(E\) is an encryption function and \(D\) is a decryption function is called additively homomorphic if for any 2 inputs \(x_1, x_2\) we have \(E(x_1 )⊕ E(x_2 )=E(x_1+x_2 )\). It is multiplicatively homomorphic if \(E(x_1 )⊗ E(x_2 )=E(x_1×x_2 )\). Here the symbols \(⊕\) and \(⊗\) just mean there is some fixed algorithm you can perform to achieve the equalities with any inputs. An encryption scheme is called fully homomorphic if it is both additively and multiplicatively homomorphic.
To give you some examples, the RSA and Elgamal cryptosystems are multiplicatively homomorphic, and the Paillier cryptosystem is additively homomorphic.
In 1978 the question was asked whether a fully homomorphic encryption scheme actually exists, but it took until 2009 for the first one to be found. It was found by the computer scientist Craig Gentry, who has since made many more breakthroughs in the area.
Now I will explain how this can be applied to a real world problem:
Suppose a company is collecting some data and they want to process the data, but they don’t have enough computing power or time available. Over the last decade cloud technology has become the most common solution to this problem. Large tech companies like Amazon, Microsoft or Google provide cloud services where you can rent as much computing power as you need.
But, this has its drawbacks. It introduces a big problem with data privacy since transferring the data to a cloud service provider is effectively giving it to a 3rd party. With new data regulations like GDPR this might not be an option legally (or morally) for the data collector.
Luckily, most data processing only requires simple operations like addition and multiplication applied a large number of times. Therefore fully homomorphic encryption provides a solution to this problem. Before sending the data to the cloud service, the data can be encrypted by the client, i.e. they send data in the form \((E(x_1 ),E(x_2 ),…,E(x_n ))\). This means the cloud service provider cannot extract information from the encrypted data as it looks almost random so the client is not breaking any rules or laws. Then the cloud service can apply the \(⊕\) and \(⊗\) operations to the data, in the place of addition and multiplication to obtain for example:
$$(E(x_1 )⊕ E(x_2 ))⊗ E(x_3 )=E((x_1+x_2)×x_3 )$$
The result still looks random, but when sent back to the client it can be decrypted to give the correct answer, \(D(E((x_1+x_2 )×x_3 ))=(x_1+x_2 )×x_3\).
In fact, the client doesn’t even need to store the data themselves before sending it. Rather than using a local database, they could use a remote database in the cloud where the data can be stored in an encrypted form to make the process even more efficient.
The encryption and decryption functions are usually easy to compute so the client doesn’t need much processing power. Some cloud service providers have already released libraries for this. For example, take a look at Microsoft's SEAL library, released in December 2018.
However there are still improvements to be made. For the cloud service the operations \(⊕\) and \(⊗\) are much harder to compute than regular addition and multiplication. In many cases, cloud services can still provide enough computing power to handle this. But improving these time complexities is a big area of active research.
Homomorphic encryption also suites a range of other use cases. For example, it is the basis of many Secure Multiparty Computation protocols, and it could also be combined with Trusted Execution Environments like Intel SGX.
Data privacy is becoming increasingly important as data is being collected and shared on a huge scale. Privacy preserving techniques like homomorphic encryption might not solve this problem entirely, but in many cases they can form a large part of the solution.
I plan on releasing some posts in the future on similar topics, so please subscribe if you are interested.
https://www.youtube.com/watch?time_continue=4&v=cXv2tWX8M4U&feature=emb_logo
ReplyDeletehi
ReplyDelete