Generating Searchable Public-Key Cipher texts with Hidden Structures for Fast Keyword Search

Abstract

Existing semantically secure public-key searchable encryption schemes take search time linear with the total number of the cipher texts. This makes retrieval from large-scale databases prohibitive. To alleviate this problem, this paper proposes Searchable Public-Key Ciphertexts with Hidden Structures (SPCHS) for keyword search as fast as possible without sacrificing semantic security of the encrypted keywords. In SPCHS, all keyword-searchable ciphertexts are structured by hidden relations, and with the search trapdoor corresponding to a keyword, the minimum information of the relations is disclosed to a search algorithm as the guidance to find all matching ciphertexts efficiently. We construct a SPCHS scheme from scratch in which the ciphertexts have a hidden star-like structure. We prove our scheme to be semantically secure in the Random Oracle (RO) model. The search complexity of our scheme is dependent on the actual number of the ciphertexts containing the queried keyword, rather than the number of all ciphertexts. Finally, we present a generic SPCHS construction from anonymous identity-based encryption and collision-free full-identity malleable Identity-Based Key Encapsulation Mechanism (IBKEM) with anonymity. We illustrate two collision-free full-identity malleable IBKEM instances, which are semantically secure and anonymous, respectively, in the RO and standard models. The latter instance enables us to construct an SPCHS scheme with semantic security in the standard model.

Aim

The aim is to generate Searchable Public-Key Ciphertexts with Hidden Structures (SPCHS) for keyword search as fast as possible without sacrificing semantic security of the encrypted keyword.

Scope

The scope is a generic SPCHS construction from anonymous identity-based encryption and collision-free full-identity malleable Identity-Based Key Encapsulation Mechanism (IBKEM) with anonymity.

Existing System

PUBLIC-KEY encryption with keyword search (PEKS), has the advantage that anyone who knows the receiver’s public key can upload keyword-searchable ciphertexts to a server. The receiver can delegate the keyword search to the server. More specifically, each sender separately encrypts a file and its extracted keywords and sends the resulting ciphertexts to a server; when the receiver wants to retrieve the files containing a specific keyword,  delegates a keyword search trapdoor to the server; the server finds the encrypted files containing the queried keyword without knowing the original files or the keyword itself, and returns the corresponding encrypted files to the receiver; finally, the receiver decrypts these encrypted files1. The authors of PEKS also presented semantic security against chosen keyword attacks (SSCKA) in the sense that the server cannot distinguish the ciphertexts of the keywords of its choice before observing the corresponding keyword search trapdoors. It seems an appropriate security notion, especially if the keyword space has no high min-entropy. Existing semantically secure PEKS schemes take search time linear with the total number of all ciphertexts. This makes retrieval from large-scale databases prohibitive. Therefore, more efficient search performance is crucial for practically deploying PEKS schemes. One of the prominent works to accelerate the search over encrypted keywords in the public-key setting is deterministic encryption. An encryption scheme is deterministic if the encryption algorithm is deterministic. Bellare et al. focuses on enabling search over encrypted keywords to be as efficient as the search for unencrypted keywords, such that a ciphertext containing a given keyword can be retrieved in time complexity logarithmic in the total number of all ciphertexts. This is reasonable because the encrypted keywords can form a tree-like structure when stored according to their binary values. However, deterministic encryption has two inherent limitations. First, keyword privacy can be guaranteed only for keywords that are a priori hardto- guess by the adversary (i.e., keywords with high minentropy to the adversary); second, certain information of a message leaks inevitably via the cipher text of the keywords since the encryption is deterministic. Hence, deterministic encryption is only applicable in special scenarios.

Disadvantages

Existing semantically secure public-key searchable encryption schemes take search time linear with the total number of the cipher texts. This makes retrieval from large-scale databases prohibitive.

Proposed System

Keyword searchable ciphertexts with their hidden structures can be generated in the public key setting; with a keyword search trapdoor, partial relations can be disclosed to guide the discovery of all matching ciphertexts. Semantic security is defined for both the keywords and the hidden structures. It is worth noting that this new concept and its semantic security are suitable for keyword-searchable ciphertexts with any kind of hidden structures. In contrast, the concept of traditional PEKS does not contain any hidden structure among the PEKS ciphertexts; correspondingly, its semantic security is only defined for the keywords. Following the SPCHS definition, we construct a simple SPCHS from scratch in the random oracle (RO) model. The scheme generates keyword-searchable ciphertexts with a hidden star-like structure. The search performance mainly depends on the actual number of the ciphertexts containing the queried keyword. For security, the scheme is proven semantically secure based on the Decisional Bilinear Diffie- Hellman (DBDH) assumption in the RO model. We are also interested in providing a generic SPCHS construction to generate keyword-searchable ciphertexts with a hidden star-like structure. Our generic SPCHS is inspired by several interesting observations on Identity-Based Key Encapsulation Mechanism (IBKEM). In IBKEM, a sender encapsulates a key K to an intended receiver ID. Of course, receiver ID can decapsulate and obtain K, and the sender knows that receiver ID will obtain K. However, a non-intended receiver ID0 may also try to decapsulate and obtain K0. We observe that, (1) it is usually the case that K and K0 are independent of each other from the view of the receivers, and (2) in some IBKEM the sender may also know K0 obtained by receiver ID0. We refer to the former property as collision freeness and to the latter as full-identity malleability. An IBKEM scheme is said to be collision-free full-identity malleable if it possesses both properties. We transform this IBE scheme into a collision-free full-identity malleable IBKEM scheme with semantic security and anonymity in the standard model. Hence, this new IBKEM scheme allows us to build SPCHS schemes secure in the standard model with the same search performance as the previous SPCHS construction from scratch in the RO model.

Advantages

·      It outperforms existing PEKS schemes with semantic security, whose search complexity is linear with the number of all ciphertexts.

·      We identified several interesting properties, i.e., collision-freeness and full-identity malleability in some IBKEM instances, and formalized these properties to build a generic SPCHS construction.

·      SPCHS seems a promising tool to solve some challenging problems in public-key searchable encryption. One application may be to achieve retrieval completeness verification which, to the best of our knowledge, has not been achieved in existing PEKS schemes.

·      Specifically, by forming a hidden ring-like structure, i.e., letting the last hidden pointer always point to the head, one can obtain PEKS allowing to check the completeness of the retrieved ciphertexts by checking whether the pointers of the returned ciphertexts form a ring.

System Specification

Hardware Requirements

• Speed                  -    1.1 Ghz
• Processor              -    Pentium IV
• RAM                    -    512 MB (min)
• Hard Disk            -    40 GB
• Key Board                    -    Standard Windows Keyboard
• Mouse                  -    Two or Three Button Mouse
• Monitor                -     LCD/LED

 Software requirements

• Operating System              : Windows 7             
•  Front End                           : ASP.Net and C#
• Database                             : MSSQL
• Tool                                    : Microsoft Visual studio

References:

Wu, Q.; Wang, W.; Susilo, W. Xu, P. " GENERATING SEARCHABLE PUBLIC-KEY CIPHERTEXTS WITH HIDDEN STRUCTURES FOR FAST KEYWORD SEARCH", IEEE Transactions on Information Forensics and Security Volume:10 , Issue: 9 , June 2015