The paper discusses the problem of secure computation on encrypted databases, focusing on the k-nearest neighbor (kNN) query. It introduces the SCONEDB (Secure Computation ON an Encrypted DataBase) model, which captures the execution and security requirements for secure query processing. The authors propose an Asymmetric Scalar-Product-Preserving Encryption (ASPE) scheme that preserves a special type of scalar product, enabling secure kNN computation. They develop two secure schemes using ASPE, each designed to resist different levels of attacks with varying overhead costs. The first scheme is resilient to level-2 attacks, while the second scheme, with additional overhead, can resist level-3 attacks. Extensive performance studies are conducted to evaluate the overhead and efficiency of these schemes. The paper also includes a detailed analysis of the security of the proposed schemes against various attack models, including signature linking attacks and brute-force attacks.The paper discusses the problem of secure computation on encrypted databases, focusing on the k-nearest neighbor (kNN) query. It introduces the SCONEDB (Secure Computation ON an Encrypted DataBase) model, which captures the execution and security requirements for secure query processing. The authors propose an Asymmetric Scalar-Product-Preserving Encryption (ASPE) scheme that preserves a special type of scalar product, enabling secure kNN computation. They develop two secure schemes using ASPE, each designed to resist different levels of attacks with varying overhead costs. The first scheme is resilient to level-2 attacks, while the second scheme, with additional overhead, can resist level-3 attacks. Extensive performance studies are conducted to evaluate the overhead and efficiency of these schemes. The paper also includes a detailed analysis of the security of the proposed schemes against various attack models, including signature linking attacks and brute-force attacks.