Paper 52 (Research track)

Secure k-NN as a Service Over Encrypted Data in Multi-User Setting

Author(s): Gagandeep Singh, Akshar Kaul, Sameep Mehta

Full text: submitted version

Abstract: Many enterprises are exploring utilizing cloud services for their IT needs. However, security of the outsourced data, both from external attacks and from cloud service provider, remain a big concern which hinders many enterprises from migrating to cloud. To handle this concern a new paradigm of ”Always Encrypted Data” has emerged. It utilizes advancements in the homomorphic encryption techniques to allow a set of computations to be directly performed on the encrypted data. This allows the Cloud Server (CS) to provide storage and analytics as a service over encrypted data. As a concrete use case, many encryption schemes have been proposed for securely processing k Nearest Neighbors (skNN) queries over encrypted data in the outsourced setting. Any secure kNN (skNN) should achieve the following properties : (1) Data Privacy (2) Key Confidentiality (3) Query Privacy (4) Query Controllability (5) Query Verification. However, most of the existing skNN solutions trust Query Users with the secret key of Data Owner and hence they are not able to provide Key Confidentiality, Query Controllability, and Query Verification. Recent work by [1] proposes a new skNN solution which claims to satisfy first four properties. However, on the detailed analysis, we found that Query Controllability of the proposed scheme can be broken. Specifically, we show an attack by which a Query User can generate a valid encryption of a new query point without any involvement of Data Owner. In this paper, we propose a new skNN solution which satisfies all the five property requirements. We provide security proofs to show that our proposed solution is provably secure. We also present detailed experimental results to showcase that our proposed scheme is efficient and can be deployed in real-world scenarios.

Keywords: Data Security; Encryption; Cloud Computing; k-nearest neighbors

Decision: reject

Review 1 (by anonymous reviewer)

(RELEVANCE TO ESWC) This is the main issue of this paper. See overall evaluation.
(NOVELTY OF THE PROPOSED SOLUTION) There are many approaches for secure-kNN, and there are quite a few methods being proposed recently. Also, the introduced method is strongly based on previous work, somewhat limiting novelty. However, the property of "Query Check Verification" as well as finding an attack on an existing algorithm and appropriate solution appear to be novel.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) The proposed solution seems sound.
(EVALUATION OF THE STATE-OF-THE-ART) There are many new articles about secure-kNN, and many of them claim to solve several issues with existing solutions. These should be checked and cited:
* A secure kNN query processing algorithm using homomorphic encryption on outsourced database, Hyeong-Il Kim, Hyeong-Jin Kim, Jae-Woo Chang, 2017 (July)
* Efficient k-NN query over encrypted data in cloud with limited key-disclosure and offline data owner, Lu Zhou, Youwen Zhu, Aniello Castiglione, 2017 (August)
* Secure kNN Computation and Integrity Assurance of Data Outsourcing in the Cloud, Jun Hong, Tao Wen, Quan Guo, and Zhengwang Ye, 2017 (May)
* Secure k-NN Query on Encrypted Cloud Data with Limited Key-Disclosure and Offline Data Owner, Youwen Zhu, Zhikuan Wang, Yue Zhang, 2016 (April)
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) Seems to be valid.
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) Parameters are given.
However the used data is not described and the code is not available, reducing reproducibility.
(OVERALL SCORE) === Summary of the Paper
The authors examine an existing approach for secure-KNN and find an attack with regard to query controlability, i.e., where a user can not query data from the cloud service without engaging the data owner. They propose an alternative algorithm to solve this problem. They give a proof of the correctness of their solution. Then, they evalute the properties of the proposed approach with regard to computation time for query encryption, data base encryption, as well as knn computation. 
=== Strong Points (SPs)
* motivation is easy to understand
* example of attack is given
* description and proof seem thorough
=== Weak Points (WPs)
* relation to conference; no semantic component
* very technical
=== Questions to the Authors (QAs)
* Is the proposed solution by chance obsolete given the mentioned related work or other recent advances?
=== Overall
While the established issue with the examined secure-knn algorithm as well as the proposed solution seem valid, the proposed paper does not fit the conference. While the paper is somewhat related to the "Web APIs, Processes, and Cloud Computing", it misses any link to "latest advances in semantic technologies that are suitable to address the challenges and opportunities raised in the context of Web". In particular, the paper is very technical on concerned with algorithmic issues focused around kNN rather than any semantic technology or application. Consequently the paper is rejected.


Review 2 (by anonymous reviewer)

(RELEVANCE TO ESWC) The paper is about secure query processing over encrypted data. After reading the abstract and introduction, I'm sorry, though the paper is simply irrelevant to ESWC. Not surprisingly, no references belongs to a Semantic Web conference and/or journal. As such, I stopped reading it further. Bear in mind that researcher's time has a cost.
(NOVELTY OF THE PROPOSED SOLUTION) I didn't read the contribution beyond the introduction, as, IMHO, the content is unrelated to ESWC.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) I didn't read the contribution beyond the introduction, as, IMHO, the content is unrelated to ESWC.
(EVALUATION OF THE STATE-OF-THE-ART) I didn't read the contribution beyond the introduction, as, IMHO, the content is unrelated to ESWC.
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) I didn't read the contribution beyond the introduction, as, IMHO, the content is unrelated to ESWC.
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) I didn't read the contribution beyond the introduction, as, IMHO, the content is unrelated to ESWC.
(OVERALL SCORE) The paper is about secure query processing over encrypted data. After reading the abstract and introduction, I'm sorry, though the paper is simply irrelevant to ESWC. Not surprisingly, no references belongs to a Semantic Web conference and/or journal. As such, I stopped reading it further. Bear in mind that researcher's time has a cost.


Review 3 (by anonymous reviewer)

(RELEVANCE TO ESWC) The authors talk about secure cloud computing environments, but does not talk about any use case for the semantic web.
(NOVELTY OF THE PROPOSED SOLUTION) The approach proposed to calculate Verifiable Secure k-Nearest Neighbor on the data that is stored in the cloud environment considering that Data Owner, Query User and Cloud Server are different entities and do not collide with each other.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) Section 4.2 describes the details about how secure is the proposed approach is. There is more than one aspect of the security as minimum three different parties are involved in the process. For security of data authors used the same encryption technique used by the state-of-the-art and argues that it is secure. Security of the query from the user is defined by query privacy, key confidentiality and query controllability. Lacks the formal proof of security for all the aspects of the approach.
(EVALUATION OF THE STATE-OF-THE-ART) Section 6 provides details about related work done previously. They also identify one state-of-the-art technique which they compare with the proposed approach. The Authors presented graphs that compare their system with state-of-the-art and also demonstrate the example to their claim to break the query controllability of the state-of-the-art but lacks the formal proof.
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) The Authors talk about the security of the proposed approach as well as presented an example to their claim of breaking the query controllability feature of the state-of-the-art. But it lacks the discussion of formal proof of their claim and also lacks any formal discussion about cost analysis of the proposed approach.
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) Description of experimental evaluation is written in section 5 that empirically compares state-of-the-art with the proposed approach. The graphs in section 5 show that proposed system performs data encryption in almost similar time, but can compute and query encryption are a bit more expensive in terms of time comparing with state-of-the-art due to adding verifiability of the proposed approach. The authors claim to implement the state-of-the-art, proposed solution and also attack on state-of-the-art in Java, but does not provide any link to the source codes.
(OVERALL SCORE) Authors propose a new SkNN solution which satisfies data privacy, key confidentiality, query privacy, query controllability and query Check Verification. They also present an attack which breaks the Query Controllability claim to the State-Of-the-art. analysis the security of proposed a scheme and present experimental results to showcase the efficiency in real world scenario.
Strong Points :
- Clearly presented approach
- Problem statement is clear
- Evaluation over large scale dataset
Weak Points :
-Formal proof of the security of the proposed approach is not presented as well as formal discussion of cost calculation is missing that must be presented while you add security.
-Lacks formal proof of the breaking the query controllability of the state-of-the-art algorithm
-Authors do not talk about any use case of the proposed scheme.
Question(s) to Authors:
Is this work an open accessed work for future? If yes, please provide all the source code and experiment data if possible.


Review 4 (by Brian Davis)

(RELEVANCE TO ESWC) While the paper does relate to the Services track - security, privacy and cloud computing and is  quite well written I see no mention of the addition, application of  and semantics  in the content of this paper, and cannot see it fitting the conference.
(NOVELTY OF THE PROPOSED SOLUTION) The novelty on the work appears that the authors have present an improvement over a state of the art k nearest neighbour - KNN solution over secure query processing querying over Encrypted  data.    The state of the art claims to satisfy the properties of data privacy, key confidentiality, query privacy and query controllability.    However the authors describe in detail and simulate an automated attack on the state of the art algorithm which rejects the query controllability claim.  The other contribution provided is that the implement new KNN algorithm which satisfies all of the the properties in addition to another property of query check verification, whereby the cloud service should be capable of verifying whether a received encrypted query has been authorised by the data owner.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) The paper is quite well written and provides detailed formal description of their improved KNN algorithm as well as the baseline competitor. It provides a through formal description of  the experiment set up  and results.  More importantly the authors clearly spell out the delta in their work with respect to 
1) rejecting the state of the art claim with respect to query controllability.
2) providing a comparable implementation in performance which satisfies the above property in addition to satisfying query check verification.
(EVALUATION OF THE STATE-OF-THE-ART) The authors appear to have convincing command of the state of the art and are able to differentiate their work clearly.
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) As mentioned earlier the proposed approach,algorithm and experiment are described in detail.  While much detail is provided in the discussion, the conclusion from a structural point of view reads very short. It needs rewriting and fleshing out.  Content for a resubmitted version can be edited in the discussion or related work sections in order conclude the paper correctly.
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) While the algorithm and mathematics appear to be well described, the executable/source code and datasets are not mentioned as being available online for download and experimental reproducibility.   Adding this for a resubmission would improve scores in my opinion.
(OVERALL SCORE) The novelty on the work appears that the authors have present an improvement over a state of the art k nearest neighbour - KNN solution over secure query processing querying over Encrypted  data.    The state of the art claims to satisfy the properties of data privacy, key confidentiality, query privacy and query controllability.    However the authors describe in detail and simulate an automated attack on the state of the art algorithm which rejects the query controllability claim.  The other contribution provided is that the implement new KNN algorithm which satisfies all of the the properties in addition to another property of query check verification, whereby the cloud service should be capable of verifying whether a received encrypted query has been authorised by the data owner.
Main Contributions
1) their algorithm rejects the state of the art claim with respect to query controllability.
2) provides a comparable implementation in performance which satisfies the above property in addition to satisfying query check verification.
Strong Points
1)Very well written and self contained paper.
2)Algorithms, and mathematics are very well described
3) Experimental setup is well described and discussed in detail
4) Good related work section
5) Contribution is spelled out clearly
Weak Points
1)Relevance to semantic web community.
While the paper does relate to the Services track - security, privacy and cloud computing and is  quite well written I see no mention of the addition, application of  semantics  in the content of this paper, and cannot see it fitting with the conference. 
2)Conclusion is very thin and detracts from a strong discussion in the pervious section.
3) Replicability of experiments:  The code and or datasets are not available for inspection or to reproduce experiments.
4)The English needs checking in general as their appear to be unnecessary uses of the passive voice in sections.
Questions
1) Clarify the relevance of the paper to the conference how it related to application of  semantics to your domain.


Metareview by Amrapali Zaveri

Our main concern is the lack of topical relevance of this paper to ESWC. The connection with semantic technologies is unclear. Our suggestion would therefore be to submit this work to a conference that focuses specifically on security or encryption. Other concerns include insufficient formal proof, lack of a strong conclusion, and lack of replication. As such, we cannot accept this paper for ESWC.


Share on

Leave a Reply

Your email address will not be published. Required fields are marked *