Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 2 down vote accepted

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.

share|improve this answer
    
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... – Vitor May 4 at 16:19
2  
@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. – poncho May 4 at 16:56
    
Yes, I was thinking of leveled fully homomorphic encryption when I commented that... – Vitor May 4 at 16:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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