Homomorphic encryption and the key recovery problem

1 :: What is homomorphic encryption

❚ Homomorphic encryption was for many years the holy grail in cryptography after it was introduced by Rivest, Adleman and Dertouzos [5] in the year 1978, shortly after the first two authors together with A. Shamir published the famous RSA scheme. The idea is simple and its usefulness is obvious: Find an encryption system, that allows to add and multiply ciphertexts, such that the executed operations on the ciphertexts transfer to the plaintexts.

Simplified-Example. Input $m_1 = 4$, $m_2 = 9$ and $m_3 =5$. Then encrypt these three values using a public key PK
\begin{align*}
 \text{Enc}(m_1,PK) & = \text{Enc}(4,PK) = 11 = c_1\\
 \text{Enc}(m_2,PK) & = \text{Enc}(9,PK) = 21 = c_2\\
 \text{Enc}(m_3,PK) & = \text{Enc}(5,PK) = 13 = c_3 \\
\end{align*} Then you compute $$ (c_1 + c_2)*c_3 = (11+21)*13 = 416 = C $$
Next, you decrypt the result $C$ using the secret key SK, which leads magically to $$\text{Dec}(C,SK) = \text{Dec}(416,SK) = 65 = (4+9)*5 = (m_1+m_2)*m_3$$
All operations you do on the ciphertexts are executed in the same manner on the plaintexts, despite they are not directly accessible.

For many years, cryptographers tried to find functions $\text{Enc}$ and $\text{Dec}$ that have this property. In 2009, the theoretically search came to an end when Craig Gentry published [1] the construction of the first working fully homomorphically encryption scheme. The bad news was, that the scheme was not efficient at all. The good news is, that history shows, that after a first new scheme is published, the research community is mostly able to increase the efficiency to a practical degree. And indeed, the efficiency of the new schemes increased but the search for a system that can handle realworld problems is still ongoing.