Patent Publication Number: US-11645409-B2

Title: Search and access pattern hiding verifiable searchable encryption for distributed settings with malicious servers

Description:
BACKGROUND 
     Searchable encryption allows a data owner to store encrypted data at an untrusted server, and later search the data, in its encrypted form, for records (or documents) matching a search query, such as a given keyword. 
     A problem exists in the art in that existing searchable encryption schemes fail to adequately hide the search results from the servers hosting the encrypted data and conducting the search on the encrypted data. This raises fundamental issues regarding privacy and information leakage since the server can infer or deduce information about the data owner&#39;s queries by recording the frequency of same search results and document retrievals. Furthermore, another problem exists in the art in that existing searchable encryption schemes fail to guarantee correctness of the search results and provide privacy. This includes privacy related to the data owner&#39;s search patterns in the presence of potentially malicious servers. 
     Hence, there is an urgent need to solve the above problems and to enhance the privacy and correctness guarantees of searchable encryption hosted by third party servers. 
     SUMMARY 
     Aspects of the invention described herein are directed to searchable encryption schemes that guarantee privacy, both in terms of access and search patterns, and correctness in the presence of malicious servers. 
     Disclosed herein are solutions to problems that exist in the art. Also disclosed herein are constructs for the first searchable encryption that is both search pattern hiding and verifiable. The presently disclosed scheme provides information theoretic security, i.e., it is unconditionally secure. Furthermore, the schemes disclosed herein rely on established and mathematical constructs. 
     According to a first aspect of the present disclosure, a method for distributed and private symmetric searchable encryption is disclosed. According to the first aspect, the method includes receiving encrypted data. The method also includes creating a search index for one or more servers based on the encrypted data using a distributed point function. The method also includes splitting the encrypted data into a number of portions based on the number of servers. The method also includes partitioning the servers into two or more groups. The method also includes updating the search index based on the splitting and the partitioning. The method also includes transmitting the split encrypted data to the servers based on the updated search index. The method also includes verifying the transmitted data using data not transmitted to the server. The method also includes determining, based on the verifying, whether any server deviated from an assigned protocol. 
     According to a second aspect, a system is disclosed. According to the second aspect, the system includes a hardware processor operatively coupled to a memory where the hardware processor is configured to execute instructions stored on the memory, including instructions for a process for improving data security or privacy in a computing environment. The process includes receiving encrypted data. The process also includes creating a search index for one or more servers based on the encrypted data using a distributed point function. The process also includes splitting the encrypted data into a number of portions based on the number of servers. The process also includes partitioning the servers into two or more groups. The process also includes updating the search index based on the splitting and the partitioning. The process also includes transmitting the split encrypted data to the servers based on the updated search index. The process also includes verifying the transmitted data using data not transmitted to the servers. The process also includes determining, based on the verifying, whether any server deviated from an assigned protocol. 
     According to a third aspect, a computer program product for improving data security or privacy is disclosed. According to the third aspect, the computer program product includes a computer-readable storage medium having program code embodied therewith, the program code comprising computer-readable program code configured to cause a processor to perform steps that include receiving encrypted data. The steps also include creating a search index for one or more servers based on the encrypted data using a distributed point function. The steps also include splitting the encrypted data into a number of portions based on the number of servers. The steps also include partitioning the servers into two or more groups. The steps also include updating the search index based on the splitting and the partitioning. The steps also include transmitting the split encrypted data to the servers based on the updated search index. The steps also include verifying the transmitted data using data not transmitted to the servers. The steps also include determining, based on the verifying, whether any server deviated from an assigned protocol. 
     These and various other features and advantages will be apparent from a reading of the following detailed description. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention will be further explained with reference to the appended Figures, wherein like structure is referred to by like numerals throughout the several views, and wherein: 
         FIG.  1    is a computing environment, according to various embodiments. 
         FIG.  2    schematically shows a searchable encryption scheme, according to various embodiments. 
         FIG.  3    schematically shows search pattern leakage, according to various embodiments. 
         FIG.  4    is a flowchart for a strong data point function search setup protocol, according to various embodiments. 
         FIG.  5    is a flowchart for a strong data point function search protocol, according to various embodiments. 
         FIG.  6    is a flowchart for a method of performing a searchable encryption scheme, according to various embodiments. 
         FIG.  7    is a block schematic diagram of a computer system according to embodiments of the present disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     Distributed point functions (DPFs) are functions used in cryptographic schemes that permit two distributed processes or parties to share a piece of information and to compute functions of their shared information without revealing the information itself to the other process or party. DPFs typically utilize the XOR operator, (⊕ or “bitwise exclusive OR”) whereby the DPF is zero everywhere except for a single point at which the DPF is non-zero. Each party is therefore provided a key that is indistinguishable from random without the other key provided to the other party. If a DPF is known, it is therefore possible to perform private information retrieval. 
     The methods and features described herein are applicable to searchable encryption schemes carried out in various computing environments. In particular, embodiments are directed to searchable encryption schemes based on DPFs in which a data owner wishes to perform a search to encrypted data hosted by a third party server. Efficient searching at the server of the data owner&#39;s plaintext is optimal, while avoiding the server access to the plaintext being queried. The data owner can also desire to prevent the potentially dishonest or malicious third party server hosting the encrypted data being searched from deducing various aspects or keywords used in user (e.g., data owner also used interchangeably herein) searches over encrypted data handled by the server and search results returned to the data owner. The server can comprise or be a part of a cloud database as is known in the art. 
     The following references are referred to in the present application. Each reference below is incorporated by reference in its entirety. The incorporated references are referred to below and throughout herein based on the author(s) name(s) and numerical identifier provided below.
     Reference [1]: B. Applebaum, D. Cash, C. Peikert, and A. Sahai. “Fast cryptographic primitives and circular-secure encryption based on hard learning problems.” In:  CRYPTO.  2009, pp. 595-618.   Reference [2]: D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano. “Public key encryption with keyword search.” In:  Eurocrypt.  2004.   Reference [3]: Christoph Bosch, Qiang Tang, Pieter Hartel, and Willem Jonker. “Selective Document Retrieval from Encrypted Database.” In:  International Conference on Information Security.  2012, pp. 224-241.   Reference [4]: Elette Boyle, Niv Gilboa, and Yuval Ishai. “Function Secret Sharing.” In:  Eurocrypt.  2015.   Reference [5]: Yan Cheng Chang and Michael Mitzenmacher. “Privacy Preserving Keyword Searches on Remote Encrypted Data.” In:  Applied Cryptography and Network Security.  2005, pp. 442-455.   Reference [6]: Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. “Searchable symmetric encryption: improved definitions and efficient constructions.” In:  ACM conference on Computer and communications security.  2006, pp. 79-88.   Reference [7]: Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. “Searchable symmetric encryption: improved definitions and efficient constructions.” In: 13 th ACM conference on Computer and communications security.  2006.   Reference [8]: Niv Gilboa and Yuval Ishai. “Distributed Point Functions and Their Applications.” In:  Eurocrypt.  2014.   Reference [9]: Eu-Jin Goh. “Secure Indexes.” In:  Cryptology ePrint Archive, Report  2003/216 (2003). url: http://eprint.iacr. org/2003/216/.   Reference [10]: Eu-Jin Goh. “Secure Indexes.” In:  In submission.  2004.   Reference [11]: Oded Goldreich and Rafail Ostrovsky. “Software protection and simulation on oblivious RAMs.” In:  Journal of the ACM  ( JACM ) 43.3 (1996), pp. 431-473.   Reference [12]: Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. “Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation.” In:  NDSS, The Internet Society.  2012.   Reference [13]: Seny Kamara and Charalampos Papamanthou. “Parallel and Dynamic Searchable Symmetric Encryption.” In:  Financial Cryptography and Data Security.  2013, pp. 258-274.   Reference [14]: Seny Kamara, Charalampos Papamanthou, and Tom Roeder. “Dynamic searchable symmetric encryption.” In:  CCS.  2012, pp. 965-976.   Reference [15]: Kaoru Kurosawa and Yasuhiro Ohtaki. “UC-Secure searchable symmetric encryption.” In:  Financial Cryptography and Data Security.  2012, pp. 285-298.   Reference [16]: Peter van Liesdonk, Saeed Sedghi, Jeroen Doumen, Pieter Hartel, and Willem Jonker. “Computationally Efficient Searchable Symmetric Encryption.” In:  Workshop on Secure Data Management.  2010, pp. 87-100.   Reference [17]: Chang Liu, Liehuang Zhu, Mingzhong Wang, and Yu An Tan.  Search pattern leakage in searchable encryption: Attacks and new construction . Information Sciences: an International Journal, 2014.   Reference [18]: R. Ostrovsky. “Efficient computation on oblivious RAMs.” In:  STOC.  1990, pp. 514-523.   Reference [19]: Rafail Ostrovsky. “Software Protection and Simulations on Oblivious RAMs.” PhD thesis. MIT, 1992.   Reference [20]: Emily Shen, Elaine Shi, and Brent Waters. “Predicate Privacy in Encryption Systems.” In:  Theory of Cryptography.  2009, pp. 457-473.   Reference [21]: Dawn Xiaodong Song, David Wagner, and Adrian Perrig. “Practical techniques for searches on encrypted data.” In:  IEEE Symposium on Security and Privacy.  2000, pp. 44-55.   

     With reference to  FIG.  1   , an example computing environment  100  is shown in which one or more data owners  112  communicate electronically with one or more servers  114 ,  116 ,  118 , and  120  over a computer network  110 . The servers  114 ,  116 ,  118 , and  120  are optionally comprised within a cloud database  126 . Furthermore, the servers  114 ,  116 ,  118 ,  120  are optionally partitioned into two or more server groups, such as group  1  (e.g., comprising servers  1  ( 114 ) and  2  ( 116 )) and group  2  (e.g., comprising servers  3  ( 118 ) and  4  ( 120 )), as shown. Although four servers and two groups are shown, any number of servers and/or groups of the servers are also contemplated herein. 
     In more detail, a DPF is a type of point function that can be carried out in a computing environment such as computing environment  100  of  FIG.  1   . In one illustrative example, for x, yϵ(element of set) {0, 1}*, a point function P x,y  is defined as: P x,y (x)=y and P x,y (x 0 )=0|y|, for all x′≠x. DPFs are discussed in detail in reference [8] above. In DPFs, a point function (e.g., P x,y ) is divided into keys (shares) which can be separately evaluated and later combined to evaluate the point function. Reference [8] describes an efficient construction of a two-party DPF, under the assumption that a one-way function exists. The key (or share) size of the two-party DPF construction is defined as O(λ·|x| log 3 ), where |x| is the length of the input of the point function, and where “O” represents a mathematical notation that describes the limiting behavior of a function. In other words, in complexity theory and as used herein notation “O” gives the upper bound on the value of the function up to a constant factor. 
     The DPF construction uses a pseudorandom generator (PRG) G to reduce the share length. A PRG provides a random sequence of results (e.g., numbers) in a way that is both random but also reproducible and/or verifiable if the PRG is copied and reinitiated in a second instance. 
     Two-party DPF construction provides a generation algorithm “Gen,” which given a point function generates its two shares (keys), e.g., k 0  and k 1 . A second algorithm, “Eval,” is used to evaluate the two DPF shares and the final result is computed as: Eval(k 0 , x′, |y|) logic exclusive OR (XOR) Eval(k 1 , x′, |y|)=P x,y (x′). Gilboa and Ishai in reference [8] describe that given a PRG G, the DPF shares of length  1 , generated by Gen are computationally indistinguishable from a uniform distribution on strings of length l. Similarly, if G is an exponentially strong PRG then so is the DPF. Byole et al. in reference [4] gives an improved two-party DPF construction and reduced the DPF share size from O(λ·|x| log 3 ) to O(λ·|x|). Improved searchable encryption schemes are discussed herein. In order to ensure secrecy of the data whose storage is outsourced to a third party server, the data owner should encrypt it as that protects against security and/or privacy related risks. But, up to now, searching over encrypted data has typically been difficult if not impossible. In order to search over encrypted data, the data owner typically downloads the data, decrypts it, and performs the search locally and separate from the third party servers. This option is impractical and/or inefficient in most cases. Another option is to provide the potentially non-trustworthy server(s) with the decryption key, which would defeat the purpose of encryption. Alternatively, the server(s) can be permitted to search over the encrypted data, on behalf of the data owner, without leaking any information about the plaintext. 
     More generally, cryptographic schemes that enable searching over encrypted data are called searchable encryption (SE) schemes.  FIG.  2    gives a graphical depiction of a typical SE scheme at  200  carried out in a computing environment (e.g.,  100 ), where the data owner  112  stores encrypted data on an untrusted third party server at operation  210  (cloud database  126 ) such that the data owner  112  can query the encrypted database at operation  212  without any need to decrypt the data. The results are returned in encrypted form to the data owner at operation  214 , which the data owner  112  can read since it knows and/or possesses the (secret) encryption key. 
     Searchable symmetric encryption (SSE), further discussed in reference [21], uses a secure index to allow the data owner to store encrypted data at an untrusted (and therefore potentially malicious) server such that it can later search the data for records (or documents) matching a given keyword. In particular, SSE allows for situations where an entire database is not desired to be encrypted, so an index is used for more common keywords and the like. This allows a user-friendly and performance-enhancing setups without significant user involvement. For example, the user can provide an index because the user knows which document or file is associated with which keyword, which is provided to same in the encrypted server environment. Preferably, one index is provided and utilized per server. 
     The problem of searching over encrypted data has been considered by Goldreich and Ostrovsky in references [11, 18, and 19] when cast as a problem of oblivious random access memory (RAM). Song et al. [21] first provided efficient solutions for equality searches and introduced SSE. Since then, several references [1, 5, 6, 9, 13-16, and 21] have provided analysis of SSE and have provided solutions with varying trade-offs between security, privacy and efficiency. Furthermore, SE schemes for asymmetric setting, such as, public key encryption with keyword search as discussed in reference [2] have also been developed. A “search pattern” as discussed in reference [6] is defined as any information that can be derived or inferred about the keywords being searched from the issued search queries (see also  FIGS.  2  and  3   ). 
     To date, significant weaknesses and shortcomings remain in SE and SSE schemes. One such problem is sometimes referred to as “search pattern leakage,” which relates to the search pattern concept above. Various embodiments of the present disclosure address and substantially solve the search pattern leakage issue that exists in the art. Embodiments also address and solve other shortcomings in the existing art. 
       FIG.  3    illustrates a simplified example 300 of search pattern leakage in searchable encryption, wherein the “malicious” server  308  can infer and/or deduce with a high probability that the search being performed by the data owner  112  includes the keyword “Seagate.” 
     In particular, data owner (or party)  112  is in communication with a malicious server  308 . The data owner at operation  310  sends a query “q” to the server  308  to search for a keyword “Seagate.” The query q is encrypted when sent at  310 , but the server receives the query and analyzes it as possible. The server then performs the requested search based on query q and returns the encrypted results to data owner  112  at operation  312 . However, if the data owner at operation  314  again searches based on the same (or similar) query q, the server  308  can begin to deduce what the data owner is seeking at operation  316 . For instance, the server  308  at operation  316  may speculate or deduce that the data owner  112  is searching for a common or predictable, e.g., alphanumeric, keyword, such as “Seagate.” More repetitions of certain queries and/or keywords may therefore lead to a discernable pattern and greater probability that the malicious server  308  can successfully deduce the nature of the unencrypted search term. 
     Therefore, existing SE schemes have a tendency to leak search patterns to the potentially malicious server(s), e.g., malicious server  308 . Shen et al. in reference [20] introduced the concept of predicate privacy, which was furthered by Bosch et al. in reference [3] to develop an efficient search pattern hiding SSE scheme. Other search pattern hiding SE schemes rely on false queries and/or false positive search results as discussed in references [12 and 17]. 
     As discussed above, no existing SE scheme hides the search results from the servers hosting the encrypted data and conducting the search. This raises fundamental problems regarding privacy and information leakage since the server ( 308 ) can infer or deduce information about the user&#39;s (data owner&#39;s  112 ) queries by recording the frequency or patterns of same search results and document retrievals. Furthermore, no existing SE scheme guarantees correctness of the search results in the presence of one or more malicious servers  308 . 
     In order to address the existing shortcoming in the art, and in order to provide a SE scheme that is both search-pattern hiding and verifying, the present disclosure provides constructs improved and unconditionally secure features, which leverage existing established mathematical constructs in beneficial and heretofore unknown and previously counterintuitive ways. 
     The participants in a single-user (e.g., data owner  112  who stores its data on third-party server and wishes to search over it efficiently and securely) SE scheme include a client (data owner  112 ) that wants to store a private document collection (e.g., data) D=(D 1 , . . . , D n ) on third party servers (e.g., server  308 ), which may be actively dishonest (e.g., malicious). 
     Third party servers can potentially be either semi-honest in which they attempt to determine information, patterns, etc. or can be malicious, in which the server  308  may actually deviate from its requested functions in order to attempt to access or decipher unauthorized and/or encrypted data it hosts. Therefore, the data owner  112  wants to store the private document collection D on the third party servers  308  such that (1) the servers do not learn any useful information about the encrypted data, and that (2) the servers can search through the D and return the appropriate (encrypted) documents to the data owner  112  without knowing the result of the search. 
     As used herein, a “negligible function” can be defined as follows: For a security parameter ω, a function ϵ(ω) is called negligible if for all c&gt;0, there exists a ω 0  such that ϵ(ω)&lt;1/ω c  for all ω&gt;ω 0 . 
     Further, new definitions can also be provided as described herein. According to a first new definition used in this disclosure, a distributed and private searchable symmetric encryption (DPSSE) scheme is defined for n (≥2) servers (e.g., four servers  114 - 120 ) and a client (data owner  112 ), such that all the servers must participate for keyword search. As contemplated herein, a single honest (i.e., neither malicious nor semi-honest) server can provide comparable benefits to each server being honest. This is because even DPFs provide randomness that cannot be easily solved without all or multiple parties collaborating to solve the encryption. A PRG can be used by each server to provide reproducible, traceable randomness as discussed herein. 
     An example DPSSE scheme is a suite of six algorithms, that are executed between the data owner and the servers, with, for example, the following specifications: 
       ←Keygen(1 k ) is defined as a probabilistic key generation algorithm, that is performed by the data owner in collaboration with the servers. It takes a security parameter k, and returns a set, K, of n secret keys, such that the length of each K, E K is polynomially bounded in k. 
     I←PartialIndex ( ,  , W) is defined as a probabilistic algorithm run by the data owner  112  to generate indexes (also known as “indices”) for the given keywords and documents. In some embodiments, indexes can be related or interrelated, and a single index can have multiple sub-indexes. It takes the set K of n secret keys along with a document collection D and a keyword collection W, each of which is polynomially bounded in k. It returns a partial index I, such that the length of I is polynomially bounded in k, and no polynomial-time adversary has non-negligible advantage in distinguishing I from a truly random index. 
     T w [i]←Trapdoor (K i , ω) is performed by the user to generate a trapdoor for the keyword w, for server S i . It takes the server&#39;s secret key K i  and the keyword w as inputs, and returns a (random) trapdoor T w [i]. As used herein a trapdoor is a “key” that allows for a grant of limited access (i.e., less complete and unrestricted access than a backdoor) to a challenging problem in one instance. 
         ω [i]←Search(T ω [i]) is run by the server S, in order to search for the documents in D, that contain the keyword w. It takes as input a (random) trapdoor T w [i], that allows S i  to search for the keyword w. The function returns a partial result, D w [i], which is S i &#39;s share of the set of identifiers, D w , of the documents that contain w. 
         ω ←Combine (   ω ) combines the set of partial results, D w ={D w [1], . . . , D w [n]}, from the n servers, to generate the final search result, D w , for keyword w, which is a list of document identifiers for the documents that contain w. 
     accept/reject←Verify(   w , ω,    ω ) is a Boolean deterministic verification algorithm, which checks the validity of the search result D w , generated by function Combine(D w ), for keyword w. 
     A security definition for disclosed DPSSE schemes can be provided by an example of an “attack game” in which the security of the DPSSE scheme is tested. As known in the art, an attack game provides a testing protocol in which an “oracle” is provided with a certain level of resources and is tasked with attempting to decrypt and solve the encryption scheme being tested. If the attack game determines that the oracle (e.g., an attacker or adversary A) guesses the solution with a non-negligible advantage, then certain conclusions can be deduced, and certain adjustments can be made accordingly. The attack game can also aid in determining which type of adversary the encryption scheme is secure again. 
     An example attack game against a DPSSE scheme for n servers and an attacker “A” includes the following three steps (and additional sub-steps). 
     1. The challenger runs the Keygen algorithm and obtains a set, K={k 1 , k 2 , . . . , k n }, of n secret keys. The challenger picks a random bit b. 
     2. The attacker “A” adaptively makes one or more of the following types of queries (a-c). 
     a. An index oracle query. Attacker A provides two documents, D 0 , D 1 . The challenger returns partial index I b =PartialIndex(K,D b ). 
     b. A trapdoor oracle query. A provides two keywords, w 0  and w 1 , a list, E, of at most n−1 servers. For each S i ϵE, the challenger returns: T wb  [i]=Trapdoor(K i ,w b ) 
     c. A search oracle query. A provides two keywords, w 0  and w 1 , along with two sets, T w0  [E] and T w1  [E], of their trapdoors, generated for servers S i ϵE (|E|&lt;n, i.e., |T w0 |=|T w1 |&lt;n). For each T wb  [i]ϵT wb  [E], the challenger returns: D wb  [i]=Search(T wb  [i]). 
     3. A outputs a guess b′ for b. 
     According to embodiments herein, a DPSSE scheme is secure if no probabilistic polynomial-time attacker has non-negligible advantage against it, in the attack game described above, where the advantage is defined as: |Pr[b=b′]−½|. 
     In the presently disclosed DPSSE schemes, a generic framework is introduced to realize DPSSE functionality. As an example solution, proposed is a DPSSE scheme that relies on and is built upon DPFs and uses the DPFs to create search indexes for the servers. Followed by that, in various embodiments DPFs can be replaced with multi-point functions and/or interval functions as discussed in reference [8]. Various embodiments herein discuss examples with four servers, but the number of servers can be any number greater than 1 (i.e., 2 or more servers). 
     In an example with four servers (S 1 , S 2 , S 3 , and S 4 ), (e.g., corresponding to servers  114 ,  116 ,  118 , and  120  of  FIG.  1   ) the data owner  112  preferably splits the encrypted data into four portions referred to as data 1 , data 2 , data 3 , and data 4 . Servers (S 1 , S 2 , S 3 , and S 4 ) are used to store the data, and the data owner  112  sends data, to server S i  (1≤i≤4). Note that the data owner  112  may choose all data portions to be empty, i.e., it may store the whole data at a single server, but it is the search index is to be shared among the four servers. The four servers are also divided or “partitioned” into two server sets or “groups”: Ser 1 ={S 1 , S 2 } and Ser 2 ={S 3 , S 4 }. Data owner  112  creates two shares of the search index and sends them to the appropriate servers. An example of an initial setup and DPF share distribution is explained in greater detail below. In some example, two servers could combine or share their respective results, e.g., to reverse-engineer the results. However, according to the present disclosure, even one non-colluding (e.g., non-malicious; honest) server would provide for a secure encryption scheme. 
     Various further notations as used herein as follows: StrongDPFindex: An algorithm to generate the server side index. StrongDPFtrap: A trapdoor is generated by StrongDPFindex during index generation, but to avoid ambiguity StrongDPFtrap is used to represent the trapdoor generating function. 
     Now, and with reference in particular to  FIG.  4   , an example Strong DPF Search Setup Protocol computer-implemented process  400 , according to various embodiments is detailed as follows. 
     At step 1 ( 410 ), data owner (e.g., data owner  112  as described herein) generates p (&gt;1) random integers (r 1 , . . . , r p ) of length l such that: ∀i≠j:r i ≠r j  (1≤i, j≤p). At step 2 ( 412 ), for each keyword w i , the owner calculates: x i   j =ω i ⊕r j . Therefore, both i and j are both integers between 1 and p. This provides for distinguishing between different values, comparing the indexes with each other, capturing, and/or determining whether both indexes are unique. At step 3 ( 414 ), data owner picks an integer n′ such that: (k·n′)≥γ. 
     Where γ is the security parameter that decides the probability of identifying the dishonest server(s). At step 4 ( 416 ), the data owner defines a point function family F: {0,1} l →GF(2 n ″), where n″=n+n′. Thus, the point functions take a keyword as input and output a bit vector of length n″. Note that a 0 n ″ is the identity element in the abelian group GF(2 n ″). At step 5 ( 418 ), the data owner randomly assigns identifiers to the n documents from the interval [1, n″]. Then document identifiers represent an entry in the bit vector “ v ” ϵ GF(2 n ″), for example if a document gets an identifier j then the j th  entry of the output bit vectors will represent the keyword search result of that document. At step 6 ( 420 ), the remaining n′ values form the set Dumi. These vector entries do not represent any document identifier but are dummy entries, which evaluate to ‘0’ for all point functions (ϵF) and all valid inputs. At step 7 ( 422 ), for each keyword w i , one nonzero bit vector  v   i  is defined, such that if  v   i [j]=1 then document d j  contains w i , else not. At step 8 ( 424 ), for each x i   j , the data owner defines a point function ƒ i   j ∈F. 
     
       
         
           
             
               
                 f 
                 i 
                 j 
               
               ( 
               x 
               ) 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         v 
                         _ 
                       
                       i 
                     
                   
                   
                     
                       
                         if 
                         ⁢ 
                             
                         x 
                       
                       = 
                       
                         x 
                         i 
                         j 
                       
                     
                   
                 
                 
                   
                     
                       0 
                       _ 
                     
                   
                   
                     otherwise 
                   
                 
               
             
           
         
       
     
     At step 9 ( 426 ), therefore, each keyword is assigned or associated with p point functions ({ƒ i   1 , ƒ i   j , . . . , ƒ i   p }∈F). At step 10 ( 428 ), the data owner computes two DPF shares of the k point functions defined for each r q  value. The data owner randomly selects an r q  value as described below. This step generates two tables T Ser     1       q    and T Ser     2       q   , each holding k DPF shares. At step 11 ( 430 ), for each q value and each index i, the data owner computes a new index i′←Per(i⊕r q ). The DPF share of ƒ i   q  is stored at index i′ in tables T Ser     1       q    and, i.e., the data owner permutes all tables holding the DPF shares. Finally, at step 12 ( 432 ), the data owner transmits T Ser     1       q    and Ser i   q  ((iϵ{1, 2}) where i represents server identifier (ID) and q is the number of values. Following the setup as shown in  FIG.  4   , a search protocol process can proceed. 
     With reference now to  FIG.  5   , an example Strong DPF Search Keyword Search Protocol computer-implemented process  500  is shown. For example, the data owner can perform a keyword search, such as: a “StrongDPFsearch,” which allows one out of the example four servers to be dishonest, i.e., that server may provide wrong DPF share evaluation result or refuse to participate in the requested keyword search. Note that at most one dishonest server implies that at least one set, Ser 1  or Ser i  has only honest servers. 
     An example process of a keyword search as contemplated herein is explained below: 
     At step 1 ( 510 ), and to search for a keyword w the data owner chooses a query q [1,p] and calculates: x i   q =ω i ⊕r q , which is to randomize the query so that search patterns remain hidden. At step 2 ( 512 ), if the data owner wishes to hide the search pattern form the servers then it should not use same q value for any keyword. To be most efficient and practical, the data owner may reuse a q value at most t times for the same keyword, where the small the t value the more secure the search will be. At step 3 ( 514 ), the data owner sends &lt;x i   q ,q&gt; to the four servers. The data owner does not send i′ as part of the initial queries in order to accurately identify the dishonest server (more detail on this herein). Once the dishonest server has been identified, the data owner sends queries of the form &lt;x i   q ,q,i′&gt; and the servers only evaluate the entry of tables T Ser     1       q    and T Ser     2       q   . At step 4 ( 516 ), servers S 1  and S 2  evaluate the DPF shares in table T Ser     1       q    and return the results, 
             (       T     Ser     1   ,     S   1   q           ⁢         and   ⁢           T     Ser     1   ,     S   2   q             )         
to the data owner. At step 5 ( 518 ), similarly, servers S 3  and S 4  evaluate the DPF shares in table T Ser     2       q    and return the results,
 
             (       T     Ser     2   ,     S   3   q           ⁢         and   ⁢           T     Ser     2   ,     S   4   q             )         
to the data owner. Therefore, both server groups perform the evaluation. At step 6 ( 520 ), For 1≤i≤k, the data owner performs two checks, e.g., as follows:
 
     
       
         
           
             
               
                 
                   
                     
                       Verify 
                       1 
                     
                     [ 
                     i 
                     ] 
                   
                   = 
                   
                     
                       
                         T 
                         
                           Ser 
                           
                             2 
                             , 
                             
                               S 
                               3 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                     ⊕ 
                     
                       
                         T 
                         
                           Ser 
                           
                             1 
                             , 
                             
                               S 
                               1 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     1 
                     ≤ 
                     i 
                     ≤ 
                     k 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Verfiy 
                       2 
                     
                     [ 
                     i 
                     ] 
                   
                   = 
                   
                     
                       
                         T 
                         
                           Ser 
                           
                             2 
                             , 
                             
                               S 
                               3 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                     ⊕ 
                     
                       
                         T 
                         
                           Ser 
                           
                             1 
                             , 
                             
                               S 
                               2 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     1 
                     ≤ 
                     i 
                     ≤ 
                     k 
                   
                   ) 
                 
               
             
           
         
       
     
     At step 7 ( 522 ), if all checks return true at decision box  521 , then all servers operated honestly for the current keyword search. Hence, the data owner XORs the i′ (Per(i⊕r q )=i′) entry of a table from the set 
             {       T     Ser     1   ,     S   1   q           ,     T     Ser     1   ,     S   2   q             }         
with the i′ entry of either
 
               T     Ser     2   ,     S   3   q           ⁢         or   ⁢             T     Ser     2   ,     S   4   q           .           
The output is a n″ length bit vector  v   i  As the data owner knows which n indexes represent the document identifiers it can decode the result and ask for the required encrypted documents from the appropriate server(s). At step 8 ( 524 ), if any check fails at  521 , then the data owner knows that one server behaved dishonestly. If Check(1) failed then a server from the set (or group) Ser 1  is faulty otherwise (“else”) it is a server from set Ser 2 .
 
     Without loss of generality for the present illustrative example, let the dishonest server belong to Ser 1 . At step 9 ( 526 ), in order to identify the dishonest server, the data owner computes k bit vectors of length n″. 
     
       
         
           
             
               
                 
                   
                     
                       Verify 
                       1 
                     
                     [ 
                     i 
                     ] 
                   
                   = 
                   
                     
                       
                         T 
                         
                           Ser 
                           
                             2 
                             , 
                             
                               S 
                               3 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                     ⊕ 
                     
                       
                         T 
                         
                           Ser 
                           
                             1 
                             , 
                             
                               S 
                               1 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     1 
                     ≤ 
                     i 
                     ≤ 
                     k 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Verfiy 
                       2 
                     
                     [ 
                     i 
                     ] 
                   
                   = 
                   
                     
                       
                         T 
                         
                           Ser 
                           
                             2 
                             , 
                             
                               S 
                               3 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                     ⊕ 
                     
                       
                         T 
                         
                           Ser 
                           
                             1 
                             , 
                             
                               S 
                               2 
                               q 
                             
                           
                         
                       
                       [ 
                       i 
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     1 
                     ≤ 
                     i 
                     ≤ 
                     k 
                   
                   ) 
                 
               
             
           
         
       
     
     At step 10 ( 528 ), data owner checks the n′ indexes (ϵDumi) of all Verify 1 [i] vectors and if there is any ‘1’ value then the owner concludes that S 1  is the dishonest party. Else the owner similarly checks the Verify 2 [1] vectors. In some embodiments, therefore, if no dishonest party (server) is identified, other parties (servers) are also checked. At step 11 ( 530 ), the data owner discards the evaluated table sent by the dishonest server and calculates the result of the keyword search by XORing entry i′ of two tables sent by honest servers and the process can end. 
     The probability of identifying the dishonest server(s) can depend on various factors and is summarized as follows. In one example, the data owner randomly fixes the n′ dummy indexes and we know that one DPF share gives no information about the point function or about the other DPF share as discussed in reference [4]. Thus, the n′ (ϵ Dumi) are random to the four servers. Without loss of generality, let S 1  be the dishonest party. There is only one (k·n′) length bit pattern which when XORed with 
             (       T     Ser     2   ,     S   3   q           ⁢         or   ⁢           T     Ser     2   ,     S   4   q             )         
will give all zeros at the (k·n′) dummy entries, and the probability that S 1  picks that bit sequence is:
 
     
       
         
           
             
               
                 
                   Pr 
                   ⁡ 
                   ( 
                   
                     cheat 
                     
                       S 
                       1 
                     
                   
                   ) 
                 
                 = 
                 
                   
                     
                       
                         1 
                         
                           2 
                           
                             k 
                             · 
                             
                               n 
                               ′ 
                             
                           
                         
                       
                       . 
                           
                       As 
                     
                     ⁢ 
                         
                     
                       ( 
                       
                         k 
                         · 
                         
                           n 
                           ′ 
                         
                       
                       ) 
                     
                   
                   ≥ 
                   γ 
                 
               
               ; 
             
              
             
               
                 Pr 
                 ⁡ 
                 ( 
                 
                   cheat 
                   
                     S 
                     1 
                   
                 
                 ) 
               
               ≤ 
               
                 1 
                 
                   2 
                   γ 
                 
               
             
           
         
       
     
     With respect to time complexity and efficiency, the time complexity of a keyword search in StrongDPFsearch can be examined as follows. It is known that the time complexity of evaluating one two-party DPF share is O(λ·l) per reference [4], where l is the length of the input of the point functions, and λ is a seed length of a PRG (or other security parameter as appropriate). For each keyword search, the servers evaluate k two-party DPF shares but only till the dishonest server is identified. Thus, on average the servers evaluate only one DPF share. Therefore, the average server side time complexity of each keyword search is O(λ·l). 
     The data owner computes one XOR operation to generate the query, this step takes O(l) time. The second task for the owner is to check if any server is dishonest and if it is the case then identify the faulty server which requires comparing 2·k·n″ bits, this step takes θ(n″) time, where θ signifies that both upper and lower bounds are bounded by n″ within some constant factor. The data owner then computes the final result by XORing two n″ long bit vectors, this step takes O(n″) time. So, the overall time complexity is dominated by the server side time complexity which is O(λ·l). Therefore, the overall time complexity depends on the seed length (λ) of the PRG used in the DPF construction, and the output length of the point functions. Note that in certain preferred example: n″&lt;&lt;size of the database. 
     With respect to security and privacy, in this disclosure it is shown that the security for the case when only one point function is defined for each keyword. This naturally extends to the case with p point functions per keyword because each point function is defined independently. 
     We turn now to information leakage from DPF shares and keyword searches. We know that if DPF share construction algorithm uses a PRG G, then the DPF shares of length len, generated by Gen(x, y) are computationally indistinguishable from a uniform distribution on strings of length len, and if G is an exponentially strong PRG then so is the DPF (see references [4, 8]). We also know that a two-party DPF share leaks no information about the other DPF share or the point function (see references [4, 8]). Hence, prior to a keyword search the servers have no information about the keywords or the plaintext data or the document identifiers. After performing a keyword search for 14) the servers only have their evaluated DPF shares at x i   q  and we know that one evaluated DPF share gives no information about the point function. As the final result is computed by data owner, the servers get no information about the result(s) of the search or the point function(s). 
     We turn now to search pattern and access pattern leakage. For example, using r i  (1≤i≤p) values, data owner defines p different point functions for each keyword. To compute a query for keyword w i  data owner randomly selects a r q  value and uses it to compute the query. To completely hide the search pattern data owner must never use the same r q  for any keyword. Thus, to search for same keyword, data owner preferably always or nearly always sends different queries, so, the data owner&#39;s search pattern looks random to the third party servers. 
     As the servers only evaluate one share of each point function they get no information about the result of the keyword search. The data owner computes the final result and then asks for the appropriate documents. Hence, data owner can easily confuse the servers about the access pattern. Also note than the DPF share size is of order O(λ·l). So, if the data owner defines p point functions and create p DPF shares for each keyword the overall space overhead of the shares&#39; tables will still be linear in l(keyword length). 
     Some specific example security standards are now discussed as they relate to the present disclosure. 
     Two example experiments discussed herein are referred to as the “IND-CKA” and “IND2-CKA” experiments. Each of the example experiments are proof sketches that provide further evidence of the advantages present disclosure. Further extensions are also contemplated, and the IND-CKA and IND2-CKA experiments as discussed herein may be incomplete. 
     In reference [10], EJ Goh describes two example security standards for secure indexes, namely IND-CKA (Semantic Security Against Adaptive Chosen Keyword Attack) and IND2-CKA (Stronger Semantic Security Against Adaptive Chosen Keyword Attack). Herein, it is first shown that StrongDPFsearch is secure against IND-CKA in the form of a proof and then the proof is extended to cover IND2-CKA. Below the IND-CKA experiment is explained and it is then shown that no information is leaked in any step of the experiment. Then we also show that if an adversary A has non-negligible advantage ξ against StrongDPFsearch in IND-CKA or IND2-CKA experiment then adversary A has same ζ advantage in breaking the security of the DPF constructions given in references [4, 8]. 
     We turn now to the IND-CKA experiment. First, as a setup, adversary A selects a set of documents {d 1 , d 2 , . . . , d t } and sends them to challenger C. C creates secure index with one entry for each word present within the given documents. To create the secure index, C first defines a point function for each word w i  present within the given documents. Then C computes two-party DPF shares of each point function, arranges them in two tables such that each table has exactly one DPF share of each point function, and sends one table as the secure index to A. 
     Queries: A queries C for word w i , and receives trapdoor T(w i ), which is data owner&#39;s evaluated DPF share of the point function ƒ i . A uses the trapdoor to search for the keyword w i . A is allowed to make finite number of queries. 
     Challenge: A selects two new documents z 0  and z 1 , containing words from the same dictionary as the previous documents. The symmetric set difference of z 0  and z 1  (z 0   z 1 ) should not be zero i.e. there should be at least one word which is not common between z 0  and z 1 , and A must not have already queried any keyword in z 0  on z 1 . A sends z 0  and z 1  to C. The challenger chooses b {0, 1}, and selects z b . C computes the secure index of z b , and sends it to A. The secure index consists of DPF shares of the point functions defined words present in z b . Note that the point functions will output bit vectors of length n″=2+n′, as there are only two documents in the database. The challenge for A is to determine b. 
     Response: A eventually outputs a bit b′, representing its guess for b. The advantage of A in winning this game is defined as: Adv(A)=|Pr[b=b′]−½|. Where the probability is computed over A and C&#39;s coin tosses. 
     Claim  1 : We claim that if adversary A has a non-negligible advantage ξ against StrongDPFsearch in the IND-CKA experiment, then A has same advantage against the DPF constructions described in references [4, 8]. 
     Proof: To defeat the security of the DPF constructions, the adversary A should be able to compute some information about the point function that is being distributed using DPF. In IND-CKA experiment, A selects two challenge documents and the challenger randomly selects one of those documents, and returns the keyword search index of the words contained within that document. 
     To break the DPF constructions&#39; security, the adversary A selects challenge document z 0  with only one word w 0 . Similarly, second challenge document z 1  also contains only the word w 1 . The adversary sends z 0  and z 1  to the challenger, which returns the index of document z b . We know that A computes the correct value of b with probability ξ+½, but this also gives the keyword (w b ) which is the nonzero point (the only input at which the point function is zero) of the point function. Thus, if the adversary A has non-negligible advantage c  against StrongDPFsearch then it has the same advantage c  against the DPF constructions presented in reference [4, 8]. 
     With reference now to non-adaptive indistinguishability, Curtmola et al. in reference [7] introduced two adversarial models for SE schemes, namely IND SSE,A  (Non-adaptive indistinguishability for SSE) and IND* SSE,A  (Adaptive indistinguishability for SSE). Unlike the security definitions given in reference [10], these definitions include security for trapdoors and require that trapdoors leak no information except what can be inferred from the search and access patterns. Before moving on to a proof, non-adaptive indistinguishability is defined herein and adapted according to the StrongDPFsearch scheme. 
     Definition 5. (History.) Let A be a dictionary and D⊆2 Δ  be document collection over Δ. A q-query history over D is tuple H=(D, w), w is a vector of q keywords. 
     Definition 6. (Access Pattern.) The access pattern induced by history H=(D, w) is a tuple α(H)=(D (w 1 ), . . . , D(w q )). 
     Definition 7. (Search Pattern.) The search pattern induced by history H=(D, w) is a symmetric binary matrix σ(H) such that for 1≥i, j≤q, the element in the i th  row and j th  column is 1 if w i =w j , and 0 otherwise. 
     Definition 8. (Trace.) The trace induced by history H=(D, w) is a sequence r (H)=(|D1|, |D2|, . . . , |Dn|, α(H), σ(H)) comprised of lengths of the documents in D, and access and search patterns induced by H. 
     Let A=(A 1 ,A 2 ), be a non-uniform adversary. In reference [7], the notation used for the probabilistic, non-adaptive indistinguishability experiment is: IND SSE,A (k) where k is the security parameter which is used to generate the secret key that encrypts the index. 
     The following is a version of the experiment adapted according to a presently disclosed scheme and the corresponding settings. 
     IND SSE,A (1 k , 1 p ) (restriction: τ (H 0 )=τ (H 1 )) 
     Step 1: (H 0 , H 1 )←   1    
     Step 2: b←${0, 1} 
     Step 3: parse H b  as (D b ,w b ) 
     Step 4: (I b )−StrongDPFindex(D b ) 
     Step 5: for 1≤i≤q, t b,i −StrongDPFtrap(w b,i ) 
     Step 6: let t b =(t b,l , . . . , t b,q ) 
     Step 7: b′←   2 (I b , t b ) 
     Step 8: if b′=b, output 1, else output 0 
     We say that the index-based SE scheme is secure in the sense of non-adaptive indistinguishability if for all polynomial-size adversaries A=(A 1 , A 2 ), we have: Pr[IND SSE,A =1]≤½+negl(k·p). 
     It has now been determined that τ (H 0 )=τ (H 1 ); thus, if the scheme is secure then knowledge of trace does not allow A to distinguish between the two document collections. In step 4 of experiment IND SSE,A , the challenger C generates an index for the document collection D b . For a presently disclosed scheme, an index in IND SSE,A  experiment setting is a table with single DPF shares of all point functions (defined for the keywords). In step 6, C provides trapdoors for selected keywords. Trapdoors are the data owner&#39;s DPF shares of the point functions, evaluated at their respective nonzero input point (keyword). 
     Claim  2 . We claim that if adversary A has a non-negligible advantage ξ against StrongDPFsearch in IND SSE,A  experiment, then it has same c  advantage in breaking the DPF constructions described in references [4, 8]. 
     Proof. The adversary A performs the following steps to generate the nonzero point of the point function, and hence break the DPF constructions. 
     Step 1: (H 0 , H 1 )←   1  such that H 0 =(D 0 ,w 0 ) and H 1 =(D 1 ,w 1 ) 
     Step 2: b {0, 1} 
     Step 3: parse H b  as (D b ,w b ) 
     Step 4: (I b )−StrongDPFindex(D b ) 
     Step 5: for 1≤I≤q, t b ,i←StrongDPFtrap(w b,i ) 
     Step 6: let t b =(t b,i , . . . , t b,q ) 
     Step 7: b′←   2 (I b , t b ). Note that the adversary A computes b′=b, with probability ξ+½. 
     Step 8: Output b′. With probability ξ+½, b′ gives the nonzero points (w b,i ) of all point functions used to generate I b  and t b . Thus, the adversary A breaks the DPF constructions without requiring any additional steps. 
     Embodiments of the present disclosure also provide for adaptive indistinguishability. As used herein, an adaptive indistinguishability security definition provides more power to adversary A. Challenger C begins by flipping a coin b. A first submits two document collections (D 0 ,D 1 ), subject to some constraints which we describe below, and receives the index of D b . Then A submits two keywords (w 0 , w 1 ) and receives the trapdoor of one of the words w b . This process goes on until the adversary has submitted polynomial number of queries, and eventually A outputs the challenge bit b. The constraint on the documents and keywords is: τ (D 0 , w 0,1 , . . . , w 0,q )=τ (D 1 , w 1,1 , . . . , w 1,q ). 
     As with the non-adaptive definition we adapted the experiment of adaptive indistinguishability according to StrongDPFsearch. The adversary is defined as: A=(A 0 , . . . , A q+i ). The probabilistic algorithm for adaptive indistinguishability is defined as: 
     IND* SSE,A (1 k , 1 p ) 
     Step 1: b {0, 1} 
     Step 2: (D 0 ,D 1 )←A 0    
     Step 3: I b ←StrongDPFindex(D b ) 
     Step 4: (w 0,1 ,w 1,1 )←A 1 (I b ) 
     Step 5: t b,l ←StrongDPFtrap(w b,l ) 
     Step 6: for 2≤i≤q (w 0,i ,w 1,i )←A i (I b , t b,1 , . . . , t b,i−1 ) 
     Step 7: let t b =(t b,1 , . . . , t b,q ) 
     Step 8: b′−A q+1 (I b , t b ) 
     Step 9: if b′=b, output 1, else output 0 
     We say that the index-based SE scheme is secure in the sense of adaptive indistinguishability if for all polynomial-size adversaries A=(A 0 , . . . , A q+1 ), we have: Pr[IND* SSEA =1]≤½+negl(k·p). We know that τ (D 0 , w 0,1 , . . . , w 0,q )=τ (D 1 , w 1,1 , . . . , w 1,q ), hence trace does not leak any information if the scheme is secure. 
     Claim  3 . We claim that if adversary A has a non-negligible advantage ξ against StrongDPFsearch in IND* SSE,A  experiment, then A has same advantage against the DPF constructions described in references [4, 8]. 
     Proof. The adversary follows the below mentioned steps to compute the nonzero point of the point function, and hence break the DPF constructions. 
     Step 1: b {0, 1} 
     Step 2: (D 0 ,D 1 )←A 0    
     Step 3: I b −StrongDPFindex(D b ) 
     Step 4: (ω 0,1 ,ω 1,1 )←   1 (I b ) 
     Step 5: t b,1 &lt;−StrongDPFtrap(w b,1 ) 
     Step 6: for 2≤i≤q (w 0,i ,w 1,i )←A i (I b , t b,1 , . . . , t b,i−1 ) 
     Step 7: let t b =(t b,1 , . . . , t b,q ) 
     Step 8: b′←A q+1 (I b , t b ). Note that the adversary A computes b′=b, with probability ξ+½. 
     Step 9: Output b′. With probability ξ+½, b′ gives the nonzero points (w b,i ) of all point functions used to generate l b  and t b . Thus, the adversary breaks the DPF constructions without requiring any additional steps. 
     Embodiments of the present disclosure also provide for hiding keyword count and document size. For example, an output bit vector of StrongDPFsearch hides n i.e., the total number of documents in the database, but the number of point functions in a table is equal to the total number of keywords in the database. To hide the total number of keywords the owner can define some dummy point functions such that they evaluate to 0 for every input. One DPF share does not give any information about the output of the point function, hence the servers cannot identify the dummy point functions&#39; DPF shares. To hide the document size from the servers the data owner can pad documents so that all documents in the database have the same size. 
     Embodiments of the present disclosure also provide for decreasing the server side time complexity. For example, in StrongDPFsearch, the data owner sends &lt;x i   q ,q&gt; as query to the servers. The servers evaluate their tables (T Ser1   q  and T Ser2   q ) at x i   q  and send the results to the owner. Evaluating the whole table at the queried point is important as this forces the dishonest server to produce an appropriate bit string of length k·n′ to fool the data owner and as (k·n′)≥200, the probability of dishonest server fooling the data owner is negligible. 
     If the data owner provides the servers i′ (Per(i⊕r q )) before identifying the dishonest server then the dishonest server needs to guess only n′ bits to avoid being caught. This can drastically increase chances of dishonest server of escaping the identification process. Thus, once the dishonest server has been identified, the owner includes i′ in the future queries, reducing the server side and overall time complexity to O(λ·l). 
     Distinct keywords can be counted in each document. For example, the data owner can easily add the functionality of counting the number of distinct keywords present within each document. To add this functionality, the owner changes the output group of the point function family to  (k n ″), which has integer (positive) vectors of length n″ as its elements with addition modulo k as the group operator. The nonzero vector  v   i  defined for keyword w i  is identical to the bit vector defined in the original StrongDPF search scheme i.e., a ‘0’ value at j th  entry implies that the document d j  does not contain keyword w i . 
     Let the data owner wishes to count the number of distinct keywords present within each document from the list: w 1 , w 2 , w 7 . The data owner forms a query for these keywords by using any eligible r q  value and sends the query to the servers. Upon receiving the query, servers evaluate their DPF shares at the points and add (integer addition) the resulting vectors locally. Each server returns the resulting value to the data owner, which performs a modular addition (mod k) of all the returned values to get the final result. The i th  entry in the final integer vector has the count of the distinct keywords (out of w 1 , w 2 , w 7 ) present within document di. It is further noted that both XOR and addition operations are commutative. 
     With respect to logical OR and logical AND expressions, counting distinct keywords also gives the result of logical OR queries, for example the count answer for keyword list w 1 , w 2 , w 7  also gives answer to w i ∨w 2 ∨w 7  because a&gt;0 value at i th  entry of the output vector implies a ‘true’ result for document d i , whereas a value of ‘0’ implies that none of the keywords (w 1 , w 2 , w 7 ) is present within document d i . 
     Similarly if the count for some document is q mod k when queried for q distinct keywords then that document contains all the q keywords, else not. Thus, the count function also gives answer to both logical OR and logical AND expressions. 
     With respect to updating the index, to add a new keyword w j , the data owner defines p new point functions {(f j   1 , . . . , f j   p )∈F}, using the p random integers (r 1 , . . . , r p ). The data owner creates two DPF shares (DPF 1 (f j   i ) and of the p point functions, and sends one share to each server. The servers add the new share at the end of the appropriate tables. Notice that the index of the DPF shares added at a later stage are not decided by the permutation function Per. Thus, it is preferable to decide on most of the keywords before the first index generation. 
     To remove a keyword w j  from the index, the data owner computes: j′=Per(j⊕r q ), (1≤q≤p) and sends remove(j′, q) to all servers. The servers on receiving a remove(j′, q) message remove the j′ entry of the q th  table. 
     Updating the database by adding or deleting {circumflex over (n)} documents is suboptimal as it requires the owner to define a new point function family: F′:{0,1} l →GF(2 n″+{circumflex over (n)} ). The data owner create and/or define new point functions in F′, and then create new keyword search index. 
     An example single-writer/multi-reader StrongDPFsearch Protocol is now described. In single-writer/multi-reader setting, the data owner maintains a set U of authorized users. To add a user u q  to set U, the data owner sends it &lt;r q ,q&gt; and &lt;i,w i &gt; values. Using this information u q  can query for any keyword w i  by calculating: x i   q =ω i ⊕r q , and sending query &lt;x i   q ,q&gt; (&lt;x i   q ,q,i′&gt; after the identification of the dishonest server) to the four servers. Note that in this setting the search pattern is exposed to the servers as to search for the same keyword an authorized user sends the same query. But the access pattern can still be hidden as the final result is computed by the users. 
     With respect to revocation, and to revoke a user u q  from the set U, the data owner sends a revoke(q) message to all servers. On receiving a revoke(q) message, the servers delete tables T Ser     1       q    and T Ser     2       q   . Now, even if user u q  sends query &lt;x i   q ,q′&gt; with a valid q′   , it will still receive incorrect result(s). The data owner then preferably picks a new r q  value which is different from all the previously selected r i  values (if no such value exists then the data owner preferably aborts). Using the new r q  value, the data owner preferably creates tables T Ser     1       q    and T Ser     2       q   , and sends them to all servers. Note that in multi-reader setting StrongDPFsearch can support a maximum of p users at a time. 
     The security and privacy follow from that of single-writer/single (i.e., same)-reader StrongDPFsearch. Procedures to count the number of distinct keywords in each document, and evaluate monotone Boolean functions are also similar to those used in the single-writer/single (i.e., same)-reader setting. 
     According to various alternative embodiments, there can be replacements for DPFs in the disclosed embodiments. For example, in the DPSSE scheme described above, DPFs can be replaced with multi-point functions or interval functions to realize additional and diverse search functionalities. 
       FIG.  6    is a flowchart for a method  600  of performing a searchable encryption scheme, according to various embodiments. 
     As shown, method  600  includes operations to be performed in the computing environment  100  as shown in  FIG.  1   . Method  600  starts with operation  610 , in which encrypted data is received. The encrypted data can be received at one or more data owner, one or more third party servers from a data owner directly or indirectly, etc. At operation  612 , a search index is created for two or more servers using a distributed point function. At operation  614 , the received encrypted data is split into a number of portions based on the number of servers. At operation  616 , the servers are partitioned into two or more groups of servers. At operation  618 , the search index is updated based on the splitting and the partitioning. At operation  620 , the split encrypted data is transmitted to the servers based on the updated search index. At operation  622 , the transmitted data is verified using data not transmitted to the servers (e.g., secret decryption key, etc.) At operation  624 , a computer determines whether any server has deviated from an assigned protocol. As described herein, a server that deviates from an assigned protocol can be deemed to be a non-trustworthy or malicious server, and the malicious server can be excluded from future operations. Optionally, a signal can be transmitted as an indication that the identified server is non-trustworthy or dishonest, and as described herein, the method  600  can proceed after excluding the identified malicious server. 
       FIG.  7    is a block schematic diagram of a computer system  700  according to embodiments of the present disclosure. The computer system  700  can be implemented according to the computing environment  100  of  FIG.  1   . 
     Computer system  700 , as shown, is configured with an interface  716  to enable controller  710  to receive a request to provide SE schemes that guarantee privacy, both in terms of access and search patterns, and correctness in the presence of malicious servers, as described in particular with regard to  FIGS.  1 - 6   . An input  718  may be received at interface  716 . In embodiments, the interface  716  can enable controller  710  to receive, or otherwise access, the input  718  via, for example, a network (e.g., an intranet, or a public network such as the Internet), or a storage medium, such as a disk drive internal or connected to controller  710 . The interface can be configured for human input or other input devices, such as described later in regard to components of controller  710 . It would be apparent to one of skill in the art that the interface can be any of a variety of interface types or mechanisms suitable for a computer, or a program operating in a computer, to receive or otherwise access or receive a source input or file. 
     Processors  712 ,  714  included in controller  710  are connected by a memory interface  720  to memory device or module  730 . In embodiments, the memory  730  can be a cache memory, a main memory, a flash memory, or a combination of these or other varieties of electronic devices capable of storing information and, optionally, making the information, or locations storing the information within the memory  730 , accessible to a processor. Memory  730  can be formed of a single electronic (or, in some embodiments, other technologies such as optical) module or can be formed of a plurality of memory devices. Memory  730 , or a memory device (e.g., an electronic packaging of a portion of a memory), can be, for example, one or more silicon dies or chips, or can be a multi-chip module package. Embodiments can organize a memory as a sequence of bit, octets (bytes), words (e.g., a plurality of contiguous or consecutive bytes), or pages (e.g., a plurality of contiguous or consecutive bytes or words). 
     In embodiments, computer  700  can include a plurality of memory devices. A memory interface, such as  720 , between one or more processors and one or more memory devices can be, for example, a memory bus common to one or more processors and one or more memory devices. In some embodiments, a memory interface, such as  723 , between a processor (e.g.,  712 ,  714 ) and a memory  730  can be point to point connection between the processor and the memory, and each processor in the computer  700  can have a point-to-point connection to each of one or more of the memory devices. In other embodiments, a processor (for example,  712 ) can be connected to a memory (e.g., memory  730 ) by means of a connection (not shown) to another processor (e.g.,  714 ) connected to the memory (e.g.,  723  from processor  714  to memory  730 ). 
     Computer  700  can include an input/output (I/O) bridge  750 , which can be connected to a memory interface  720 , or to processors  712 ,  714 . An I/O bridge  750  can interface the processors  712 ,  714  and/or memory devices  730  of the computer  700  (or, other I/O devices) to I/O devices  760  connected to the bridge  750 . For example, controller  710  includes I/O bridge  750  interfacing memory interface  723  to I/O devices, such as I/O device  760 . In some embodiments, an I/O bridge can connect directly to a processor or a memory, or can be a component included in a processor or a memory. An I/O bridge  750  can be, for example, a peripheral component interconnect express (PCI-Express) or other I/O bus bridge, or can be an I/O adapter. 
     The I/O bridge  750  can connect to I/O devices  760  by means of an I/O interface, or I/O bus, such as I/O bus  722  of controller  710 . For example, I/O bus  722  can be a PCI-Express or other I/O bus. I/O devices  760  can be any of a variety of peripheral I/O devices or I/O adapters connecting to peripheral I/O devices. For example, I/O device  760  can be a graphics card, keyboard or other input device, a hard disk drive (HDD), solid-state drive (SSD) or other storage device, a network interface card (NIC), etc. I/O devices  760  can include an I/O adapter, such as a PCI-Express adapter, that connects components (e.g., processors or memory devices) of the computer  700  to various I/O devices  760  (e.g., disk drives, Ethernet networks, video displays, keyboards, mice, styli, touchscreens, gesture input, etc.). 
     Computer  700  can include instructions executable by one or more of the processors  712 ,  714  (or, processing elements, such as threads of a processor). The instructions can be a component of one or more programs. The programs, or the instructions, can be stored in, and/or utilize, one or more memory devices of computer  700 . As illustrated in the example of  FIG.  7   , controller  710  includes a plurality of programs or modules, such as verification module  704 , search module  705 , encryption/decryption module  706  (which can include authentication functionality), index module  707 , distributed point function module  708 , and data (e.g., document, plaintext, etc.) module  709 . A program can be, for example, an application program, an operating system (OS) or a function of an OS, or a utility or built-in function of the computer  700 . A program can be a hypervisor, and the hypervisor can, for example, manage sharing resources of the computer  700  (e.g., a processor or regions of a memory, or access to an I/O device) among a plurality of programs or OSes. 
     Programs can be “stand-alone” programs that execute on processors and use memory within the computer  700  directly, without requiring another program to control their execution or their use of resources of the computer  700 . For example, controller  710  includes (optionally) stand-alone programs in verification module  704 , search module  705 , encryption/decryption module  706 , index module  707 , distributed point function module  708 , and data module  709 . A stand-alone program can perform particular functions within the computer  700 , such as controlling, or interfacing (e.g., access by other programs) an I/O interface or I/O device. A stand-alone program can, for example, manage the operation, or access to, a memory (e.g., memory  730 ). A basic I/O subsystem (BIOS), or a computer boot program (e.g., a program that can load and initiate execution of other programs) can be a standalone program. 
     Controller  710  within computer  700  can include one or more OS  702 , and an OS  702  can control the execution of other programs such as, for example, to start or stop a program, or to manage resources of the computer  700  used by a program. For example, controller  710  includes OS  702 , which can include, or manage execution of, one or more programs, such as OS  702  including (or, managing) verification module  704 , search module  705 , encryption/decryption module  706 , index module  707 , distributed point function module  708 , and/or data module  709 . In some embodiments, an OS  702  can function as a hypervisor. 
     A program can be embodied as firmware (e.g., BIOS in a desktop computer, or a hypervisor) and the firmware can execute on one or more processors and, optionally, can use memory, included in the computer  700 . Firmware can be stored in a memory (e.g., a flash memory) of the computer  700 . For example, controller  710  includes firmware  740  stored in memory  730 . In other embodiments, firmware can be embodied as instructions (e.g., comprising a computer program product) on a storage medium (e.g., a CD-ROM, DVD-ROM, flash memory, or disk drive), and the computer  700  can access the instructions from the storage medium. 
     In embodiments of the present disclosure, computer  700  can include instructions for data management and protection. Controller  710  includes, for example, verification module  704 , search module  705 , encryption/decryption module  706 , index module  707 , distributed point function module  708 , and data module  709 , which can operate to provide searchable symmetric encryption according to various embodiments herein. 
     The example computer system  700  and controller  710  are not intended to be limiting to embodiments. In embodiments, computer system  700  can include a plurality of processors, interfaces, and inputs and can include other elements or components, such as networks, network routers or gateways, storage systems, server computers, virtual computers or virtual computing and/or I/O devices, cloud-computing environments, and so forth. It would be evident to one of skill in the art to include a variety of computing devices interconnected in a variety of manners in a computer system embodying aspects and features of the disclosure. 
     In embodiments, controller  710  can be, for example, a computing device having a processor (e.g.,  712 ) capable of executing computing instructions and, optionally, a memory  730  in communication with the processor. For example, controller  710  can be a desktop or laptop computer; a tablet computer, mobile computing device, personal digital assistant (PDA), cellular phone, or other mobile device; or, a server computer, a high-performance computer (HPC), or a super computer. Controller  710  can be, for example, a computing device incorporated into a wearable apparatus (e.g., an article of clothing, a wristwatch, or eyeglasses), an appliance (e.g., a refrigerator, or a lighting control), a mechanical device, or, e.g., a motorized vehicle. It would be apparent to one skilled in the art that a computer embodying aspects and features of the disclosure can be any of a variety of computing devices having processors and, optionally, memory devices, and/or programs. 
     The present invention has now been described with reference to several embodiments thereof. The foregoing detailed description and examples have been given for clarity of understanding only. No unnecessary limitations are to be understood therefrom. It will be apparent to those skilled in the art that many changes can be made in the embodiments described without departing from the scope of the invention. The implementations described above and other implementations are within the scope of the following claims.