Secure Computation over Encrypted Databases

Sensitive applications running on the cloud often require data to be stored in an encrypted domain. To run data mining algorithms on such data, partially homomorphic encryption schemes (allowing certain operations in the ciphertext domain) have been devised. One such line of work yields schemes for secure $\mathit{\text{k-nearest}}\mathit{\text{neighbors}}$ computation that is designed to provide both $\mathit{\text{Data}}\mathit{\text{Privacy}}$ and $\mathit{\text{Query}}\mathit{\text{Privacy}}$. Enhancements in this area further ensure that the data owner approves each query issued by a query user before the cloud server processes it. In this work, we describe an attack that invalidates the $\mathit{\text{key}}\mathit{\text{confidentiality}}$ claim, which further invalidates the $\mathit{\text{Data}}\mathit{\text{Privacy}}$ claim for these schemes. We show that a query user can specially tailor a query to extract information about the secret key used to encrypt the data points. Furthermore, the recovered secret information can be used to derive all the plaintext data points breaking $\mathit{\text{data}}\mathit{\text{privacy}}$. We then suggest enhanced encryption schemes that make such attacks on $\mathit{\text{data}}\mathit{\text{privacy}}$ impossible while incurring meager additional costs in performance.