A question about fully homomorphic encryption (FHE)

Question

Hypothesis: We define the messages on a field $\mathtt{F}_p$, where $p$ is a large prime number.

I am considering a dynamic outsourced private data scenario.

---

Assume we have 3 messages: $m_1=2, m_2=4$ and $m_3=77$. We encrypt them using FHE, so we would have: $E(m_1), E(m_2)$ and $E(m_3)$.

We send the three ciphertexts to a semi-honest server.

Later on, we want to remove $E(m_1)$ from the outsourced data (in fact we want to remove $m_1$ from there).

Question 1: If we encrypt $m_1$, and send it to the server, can the server "somehow" find $E(m_1)$ and remove it?

Question 2: Is there any other way to remove $m_1$ from the outsourced dataset without leaking any information to the server?

---

Please note that we are using semantically secure encryption (e.i. FHE); therefore, the ciphertexts of the $m_1$ are different.

Answer 1

If we encrypt $m_1$, and send it to the server, can the server "somehow" find $E(m_1)$ and remove it?

Nope; FHE allows a server that knows $E(m_1)$ and $E(m_2)$ to produce a ciphertext which is a representation of the value $E(m_1 \odot m_2)$ (for pretty much arbitrary functions $\odot$); what it doesn't allow a server to do is determine whether $m_1 = m_2$. If it could, then it could decrypt (by guessing various values $m_2$, producing $E(m_2)$, and then checking if that was the same.

Is there any other way to remove $m_1$ from the outsourced dataset without leaking any information to the server?

One thing that occurs to me is to produce $E(m_1)$, and have the server replace all values $E(m_i)$ it knows with $E(m_i \odot m_1)$, with $a \odot b = a \cdot (a-b)^{p-1}$ (and, of course, erase all the original $E(m_i)$ values. In case you don't get the punchline, with this $\odot$, we have $a \odot b = a$ if $a \ne b$, and $a \odot a = 0$; hence any copies of $E(m_1)$ are replaced with an encryption of a fixed constant, while the copies of any other value are unaffected.