1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is an interesting approach. It is worth to note that doing so, you are increasing the noise in the ciphertexts and you are "wasting" one level of your available multiplicative depth... $\endgroup$ – Hilder Vítor Lima Pereira May 4 '16 at 16:19
  • 2
    $\begingroup$ @Vitor: actually, user153465 asked about Fully Homomorphic Encryption; those schemes have infinite multiplicative depth; that is, you are allowed to multiply as many times as you want. There might be a bootstrapping procedure in there somewhere; however that's an implementation issue that we can (at this level) ignore. $\endgroup$ – poncho May 4 '16 at 16:56
  • $\begingroup$ Yes, I was thinking of leveled fully homomorphic encryption when I commented that... $\endgroup$ – Hilder Vítor Lima Pereira May 4 '16 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.