  To securely leverage the advantages of Cloud Computing, recently a lot of
research has happened in the area of "Secure Query Processing over Encrypted
Data". As a concrete use case, many encryption schemes have been proposed for
securely processing k Nearest Neighbors (SkNN) over encrypted data in the
outsourced setting. Recently Zhu et al[25]. proposed a SkNN solution which
claimed to satisfy following four properties: (1)Data Privacy, (2)Key
Confidentiality, (3)Query Privacy, and (4)Query Controllability. However, in
this paper, we present an attack which breaks the Query Controllability claim
of their scheme. Further, we propose a new SkNN solution which satisfies all
the four existing properties along with an additional essential property of
Query Check Verification. We analyze the security of our proposed scheme and
present the detailed experimental results to showcase the efficiency in real
world scenario.
