The Analysis Of Searchable Symmetric Encryption Problems
Problem Statement
With the inception of internet and cloud, data sharing and accessing over the internet has been widely adapted across all domain starting from education, health, entertainment etc. With the wide adaption came some really critical security privacy concerns as well. One of them was data privacy over the cloud. And for this there has been a lot of work in this domain specifically cryptography-based solutions like Homomorphic Encryption, Oblivious RAM etc.
One of such technique is called searchable encryption which basically means user can perform search operations over encrypted data. This can allow different companies working over internet to provide more valuable features to the end user without impacting their privacy. A lot of research work has already been done on the searchable encryption technique. But most of the works prior to this work had some serious drawbacks. Some of them had weaker security models and others had some serious security threats like statistical attacks.
Some of the existing works are based on IND2-CKA security definition which is not essentially enough for the security of the searchable encryption scheme. And one of the large drawbacks of all the existing works was that the adversarial model all of them were based was non-adaptive Which basically means the users search operations basically is performed at once and the further search operation does not use the knowledge of the past search operation results. Also, none of the previous works has considered a multi-user setting and all were based on single user setting. Which basically means the search operation can only be carried out by a single user, not a group of users. But from the point of real-life application this two drawbacks were a serious setback. Because in real life applications the operations are expected to be adaptive and a multi-user feature is huge add on to this application.
Proposed Solution
The paper proposed couple of novel ideas in order to overcome the shortcomings of the existing research works in searchable encryption domain. First of all, the paper gave an in-depth review of existing security definition named IND2-CKA and explained why this definition is not enough for the SSE. For this the paper proposes two new set of security definitions based on indistinguishability and simulation.
The paper provides two set of adversary models for the constructions to be based on. One of them is non-adaptive and the other is adaptive which basically can use adversary with queries which are dependent on the results of the past search queries. On top of these security settings, the authors proposed two different schemes of Symmetric Searchable Encryption (SSE) one in non-adaptive and another in adaptive settings.
Lastly, they proposed an SSE scheme in multi-user setting where a group of people can search over the data of another user. Here the owner of the data has the credentials to grand different levels of access to the group participants. All the above proposed schemes assume the server to be semi-honest rather than malicious. Meaning, the server may try to gain more knowledge that ideally it should, but it will not deviate from the proposed protocol.
Results/Findings: The proposed non-adaptive SSE scheme is the state of the art most efficient solution for the problem with one round of communication and constant space unlike the previous solutions which required the space and communication rounds to be linearly dependent on the document size. The proposed adaptive SSE scheme incurs a higher cost in terms of query and space. Nonetheless the adaptive SSE is itself a novel approach which was not considered in any of the previous works. The paper also has proven that the proposed schemes are secured in the defined security model and the adaptive SSE is secured in the simulation-based definition. Their proposed multi-user SSE has a novel approach of doing away with the authentication which reduced the cost and gave a boost to the performance. They have also given comparative analysis of the proposed SSE-1, SSE-2 with the existing works and has shown how the proposed schemes are not only efficient but also avoids some of the serious security drawbacks.
Critique: The paper proposes some groundbreaking novel approach for the searchable symmetric encryption. Their security definitions are more concrete and avoid the flaws present in the prior works. The paper also gives a clear chronological order of related work with specific flaws and security drawbacks in each of those schemes. Their comprehensive analysis of the security proof gives a clear confidence on the proposed system. Their comparative analysis of the existing schemes with the proposed schemes establishes the authors claims. Although the proposed schemes are efficient and novel, the paper does have some shortcomings in terms of security settings of malicious server. The paper has only concentrated on the semi-honest server not the malicious one. Overall the paper was well structured with proper flow which makes it easy to read and understand. The paper does miss a clear picture on the future direction of works in this area.
Ideas for follow-on work: One of the major works which can be done on top of this paper is to find solutions which are secured in both semi-honest and malicious server setting. The current solutions only assume the server to be semi-honest i.e. honest but curious server. The malicious server setting solution can be achieved using some existing technique called memory checking and universal arguments which has already been proposed but has not been incorporated to this setting. Also, the work has only been on the symmetric encryption family. Similar works can be done in the Searchable Asymmetric Encryption and Private information Retrieval area as well. Inspired by this paper the existing solutions in the area of Searchable Asymmetric Encryption and Private information Retrieval can be improved in terms communication round efficiency and storage space in the server.
