Today we are going to talk about a very special encryption system. Although this type of encryption has been proposed for a long time (it was first proposed during the creation of the RSA algorithm), it has been unsuccessfully tried to be implemented for the last 40 years. It has a feature that no other cipher has: it is possible to manipulate the information encrypted with this system without the need to decrypt it. Let’s take a closer look.
Description
Homomorphic encryption is a form of encryption that allows users to perform calculations on their encrypted data without first decrypting it. These resulting calculations are left in an encrypted form which, when decrypted, produces a result identical to that which would have been produced if the operations had been performed on the unencrypted data. A cipher is homomorphic if it satisfies the following equality:
That is, the decryption of an Op’ operation with encrypted data is the same as another Op operation with decrypted data. Op’ and Op can be the same operation or not, the important thing is that by means of an operation with encrypted data, the encrypted result of an operation with unencrypted data is obtained. Perhaps it is easier to understand with the following scheme:
The cipher 200 is X, the cipher 88 is Y, and the cipher 288 is Z. A cipher is homomorphic if an operation with X and Y (in this case addition) yields Z.
Homomorphic encryption would allow working with sensitive information without needing to know that information. This is key to protect privacy and to allow critical operations to be carried out securely.
There are two types of homomorphic encryption:
– Partially homomorphic encryption: cipher that is homomorphic only in addition or multiplication. There are several examples of partially homomorphic ciphers, such as Unpadded RSA, ElGamal, Goldwasser-Micali, Benaloh or Paillier.
– Fully homomorphic encryption (FHE): encryption that supports both addition and multiplication. There are implementations of fully homomorphic ciphers such as Helib, Microsoft SEAL, PALISADE or HEAAN. The importance of this type of cipher is that with addition and multiplication it is possible to build the circuits to perform any computation, so that with this type of cipher any task could be performed with encrypted data.
Current State of Art
Homomorphic encryption currently exists only at a theoretical level. Although homomorphic ciphers have been developed that are capable of processing certain operations, they are very limited and not fast enough to be used in real applications.
Nevertheless, research continues every year to improve the algorithms. IBM’s Helib stands out in particular, and you can find this implementation at the following github: https://github.com/homenc/HElib
This implementation is based on the fully homomorphic Brakerski, Gentry and Vaikuntanathan (BGV) cipher, is written in C++ and licensed under the GNU GPL and currently allows low-level operations. You can find more information here. It is the result of years of research that began with Craig Gentry’s doctoral thesis.
Homomorphic encryption is currently in the fourth generation, where the CKKS scheme is implemented. This scheme supports several rounds of cipher operations. The biggest problem with cipher rounds is that they generate noise, especially in cipher multiplication. The CKKS scheme manages to eliminate this noise by approximating the values in each round instead of storing the exact value (it uses only the most significant bits, efficiently dealing with the errors produced by this approximation). This approach is similar to how noise is dealt with in Machine Learning, so CKKS is intended to be a solution to encrypted Machine Learning.
Attacks against homomorphic ciphers
Since a form of homomorphic encryption that works in real environments has not yet been achieved, there are few attacks on this type of encryption.
However, last year researchers Baiyu Li and Daniele Micciancio published a paper on passive attacks against CKKS. The authors performed the attack on 4 modern homomorphic cipher libraries: HEAAN, Helib, PALISADE and SEAL. They showed that for certain configurations it is possible to obtain the private encryption key.
However, measures to prevent this attack have already been implemented in most current libraries.
Cloud Computing
The main purpose of homomorphic encryption is to be able to manipulate encrypted information. This may seem trivial but it is extremely important due to the rise of Cloud Computing: companies have to entrust the most sensitive information they have, their customers’ data, to providers such as Amazon Web Services, Google Cloud, Microsoft Azure…
This implies a very high risk, as they have to trust that the provider will take the necessary measures to protect their data. Moreover, they only have to take the provider’s word for it, as they won’t even know on which physical device the data is located.
All in all, the only option for companies to migrate to the cloud is to encrypt all their data and use the cloud as a container to store all that information. And if they need the provider to do something with their data, they will have to provide encryption keys or find a way to add decryption of the data as part of the process.
But if this homomorphic encryption can be achieved, it could allow customers using these cloud services to upload their encrypted data and continue to use it without needing to share encryption keys. This will allow cloud environments to be used even more widely by customers who handle very critical information.
Practical Example: Voting System
We are going to see a simple example by means of which a voting system could be created for an election, where each citizen can vote completely anonymously and the machine that computes each vote can count all the votes without the need to decrypt them and clearly show the voter’s personal information and the party they have voted for. It should be noted that this system could be implemented today without any problem, as it only requires adding up encrypted data.
We propose a system with 3 candidates, A, B, C and 3 voters, V1, V2 and V3. This would show the table of results in plain text (left) and the table with the results encrypted with a public key encryption system (right):
If we have a homomorphic cipher in which we can add up encrypted elements, we would only have to decrypt the total sum of the votes of each candidate (Xa, Xb and Xc), giving privacy to each citizen’s vote.
As we can see, homonymous encryption offers many advantages in different fields, and achieving an efficient implementation will mark a turning point in the security of our communications. If you are interested in this article, stay tuned because I will publish here all the information I have as progress is made.
Lethani