Homomorphic Encryption

As our reliance on cloud infrastructure increases and our social interactions become increasingly dependent on the internet, we worry more about data breaches in activities like online conversations and storing personal information on the cloud. Fully homomorphic encryption is a form of encryption that can tackle security issues arising from these activites.

Fully homorphic encryption is regarded as the Holy Grail of information security because it can protect the privacy of data while it is stored in the cloud or while it is in transit. At first glance, the word “homomorphism” might seem unfamiliar, but it is not! “Homo” means similar and “morphism” means change, and homomorphism consequently means a form-preserving map between 2 algebraic structures. Homomorphic encryption is a special method of encryption that allows mathematical operations on encrypted data rather than on its plaintext. This means one can perform these operations on the data and get the encrypted output without ever knowing what the data was. The significant property of this particular type of encryption to note is that decrypting the operated encrypted data should give the same output as operating on the plaintext itself.

Our current homomorphic encryption models are either partially homomorphic or fully homomorphic. Partially homomorphic models allow only a certain number of operations on the data (usually multiplication or division). On the other hand, fully homomorphic encryption allows you to perform multiple sequential operations on the data without exposing the meaning of the message.

This diagram above is a simple demonstration on how homomorphic encryption works. It starts with a plaintext m, let’s assume it’s the name of someone in an organization Boogle “ALICE”. Let function f be decapitalizing the name. The goal is to be able to perform this function on the plaintext m without compromising the actual value of it, i.e. perform f on the value of the enc(m). So first you encrypt the message m into some value, let’s say 23225. This value is then transformed into some other value using some other function, e.g. f(x) = x + 75. The output is 23300, and this corresponds to another completely encrypted message which can be decrypted to give “Alice”.

This property is what allows homomorphic encryption to protect against privacy breaches. With increasing technological infrastructure comes an added necessity to secure it. In the current model of encryption we use when storing information on Amazon or Google provided cloud servers, the information must be decrypted on the server side before performing any operation on it before sending them back to the client for them to review the output. This clearly leaves security vulnerabilities because our information is being revealed at a point while it is being operated on. Homomorphic encryption allows your data to remain encrypted not only while it is at rest, but also while it is in transit and while it is being operated on. As a result, the server would never know what the actual information value was.

An important property of homomorphic encryption to consider is that it is inherently malleable. A malleable encryption model means that any intruder can intercept the encrypted message, transform it into a different encrypted message, and then decrypt it into a plaintext that makes “sense”. This is generally considered unfavorable, because imagine a situation where one is trying to send private medical information about their blood type O, but then someone intercepts then alters it to a different type A. This is an example of why malleability can be looked down on.

However, homomorphic encryption models are supposed to be malleable! Take an example where you’re trying to add information to your blood type, from O to O+. When you encrypt your message and send it along the route, the system only sees your encrypted message, but it can still transform your message from O to O+ as wanted. In this case, malleable systems allow multiple parties, such as in cloud infrastructure, to act on your data without seeing it.

Partial Homomorphic Schemes

RSA Encryption is an example of a partially homomorphic scheme, specifically multiplicative. It selects 2 prime numbers a and b and sets n = a ⋅ b. It then selects y and z such that

y ⋅ z ≡ 1 mod ϕ (N)

This is called the modular inverse of y of z modulo ϕ (N). The ≡ operator symbolizes congruence and means that the product y ⋅ z and 1 have the same remainder when divided by ϕ (N). ϕ (N) is called the Euler’s totient function and counts the positive integers up to N that are relatively prime to N. 2 relatively prime integers a and b, or coprime integers, are said to be so if the only positive integer that divides them both is 1. This forms a ring of possible values.

In this case, a and b are private and are only known by the sender and receiver whereas p and q are public. Taking this information, the encryption and decryption schemes become

Enc(x)=x^b mod(n)

Dec(x)=y^a mod(n)

You can prove the homomorphism by taking a and b as example messages.

Enc(a) . Enc(b) = Enc(a . b)

Fully Homomorphic Algorithms

Now fully homomorphic systems are ones in which any types of mathematical operations can be performed on the plaintext. Craig Gentry was the first to suggest that they could be theoretically possible.

In his thesis, he used the analogy of a jewelry shop owner. Lavinia is the jewelry shop owner, and she has employees that create jewelry from materials like diamond and gold. However, she’s afraid of her employees stealing these valuable items. To combat this, she creates a box with gloves attached to them. The employees can stick their hands into the box to create the jewelry, but cannot take anything out as only Lavinia has the key to open the box.

In this model, there is some noise in the morphic process. Each transformation adds more noise to the system, but this makes the model impractical as the system gets much slower. This necessarily means that Gentry’s scheme grows in complexity as more and more operations are performed. For example, one search using this scheme on Google’s search engine would increase computations by not millions, but trillion of times.

However, despite this impracticality, this discovery at least shows that homomorphic encryption exists and proves that these schemes are possible, even if theoretically.