what is homomophic gryptography

The encryption function of homomorphic cryptosystems is a homomorphism so that it allows a third party to take two ciphertexts $e_K(m_1)$ and $e_K(m_2)$, and calculate one of $e_K(m_1+m_2)$ or $e_K(m_1cdot m_2)$ without knowledge of any secret information. Usually, the plaintext space and the ciphertext space are groups or rings so that the cryptosystems can support one or two operations. We can regard the encryption as a mapping from the plaintext space to the ciphertext space. The following figure reflect the homomorphic properties.

Through the figure we can see that given ciphertexts $c_1$,$c_2$ that encrypt $p_1,p_2$ under some key then we can calculate the encryption of $p_1cdot p_2$ without knowledge of $p_1,p_2$. I want to note that $cdot$ and $otimes$ are different because of the operation between plaintexts is different from the operation between ciphertexts. In the third chapter of this thesis almost all homomorphic cryptosystems can only support one operation, linear operation or multiplication. So how to construct a homomorphic cryptosystem that can support both linear operation and multiplication?

The birth of Gentry cryptosystem which named FHE is in this background. Through this crptosystem we can calculate arbitrary numbers of additions and multiplications on encrypted data. I want to make a brief introduction here. Given ciphertexts $c_1,ldots,c_t$ that encrypt $p_1,ldots,p_t$ under some key, that is $c_1=e_K(p_1),ldots,c_t=e_K(p_t)$, then for any efficient computable function $f$ we can calculate a ciphertext that encrypts $f(p_1,ldots,p_t)$under that key.

Chapter 1 of this thesis tell us some notions of security. The usual method of demonstrating that a cryptosystem is secure is showing that if an adversary can invert the encryption function or break semantic security. Under this criterion we want a cryptosystem to be indistinguishable under different attacks, then we obtained three main security levels of the cryptosystem. The following is the relaitonship between these three security levels.

We can see that IND-CCA2 is the strongest security level of cryptosystems, however because of the malleablity of homomorphic cryptosystem, no homomorphic cryptosystem can be IND-CCA. How about IND-CCA1?Observed that in chapter 3, many homomorphic cryptosystems are just proved to be semantic secure because the security of them are based on the hardness of math problems. Can they be IND-CCA1 ? or it’s difficult to construct a homomorphic cryptosystem to be IND-CCA?

In fact, under the assumption that the homomorphic operations are implemented in an ideal black box model we have such a theorem: IND-CCA1 is a tight upper bound for the security of a homomorphic cryptosystem. However, for an algorithm-based homomorphic cryptosystem IND-CCA1 is still an upper bound but not a tight upper bound. So there are alternate security notions for homomorphic cryptosystems which are weaken than IND-CCA2 but stronger than IND-CCA1. The following figure is the relationship between them.

For a homomorphic cryptosystem IND-gCCA2 and IND-rCCA2is still too strong to achieve, but in some cases IND-hCCA2 security can be achieved. It’s necessary to note that CCA2, gCCA2 and rCCA2 can be obtained as special cases of hCCA2.

In chapter 3 of this thesis the author give us a survey of homomorphic cryptosystems. All these homomorphic cryptosystems are built upon math problems and security assumption also depends on these math problems. On the one hand the difficulty of these math problems ensure the security of cryptosystems on the other hand these math problems also restrict the homomorphic operation for encrypted data. The following table is a summary of homomorphic cryptosystems which I excerpt from the thesis.

In this table +,-,$times_c$ are used to denote homomorphic addition, subtraction and multiplication on ciphertexts. We can regard them as linear operations. $times$ is used to denote homomorphic multipication.

As we can see from this table, almost all cryptosystems can only support one homomorphic operations linear operation or multiplication because of the security assumption thus if we want to improve the homomorphic we must find better math problem to construct the cryptosystem. What makes me confused is the message expansion. Usually the ciphertext space is larger than the plaintext space so it causes the message expansion and the encryption method also causes message expansion. What problems will it bring to the cryptosystem?

In the thesis there is only one cryptosystem named BGN cryptosystem that can support both linear operations and multiplication. So FHE is a very important cryptosystem. And more details of these cryptosystems can be found in thesis.

Reference: