  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
\textit{k-nearest neighbors} computation that is designed to provide both
\textit{Data Privacy} and \textit{Query 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 \textit{key confidentiality} claim, which further invalidates
the \textit{Data 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 \textit{data privacy}.
We then suggest enhanced encryption schemes that make such attacks on
\textit{data privacy} impossible while incurring meager additional costs in
performance.
