Patent Description:
Searchable encryption (i.e., encrypted search) has increased in popularity as storage of large quantities of data in the cloud becomes more common. More and more, a user or client owns a large corpus of encrypted documents that are stored at a server not under the client's control (i.e., the server is untrusted). With searchable encryption, the client can store their encrypted documents on the untrusted server, but still maintain the capability of searching the documents and, for example, retrieve identifiers of all documents containing a specific keyword. However, such searchable encryption often comes with security and privacy drawbacks.

US patent publication <CIT> is further prior art.

One aspect of the disclosure provides a method for providing encrypted search with no zero-day leakage. The method includes receiving, at data processing hardware of a user device associated with a user, a search query for a keyword. The keyword appears in one or more encrypted documents within a corpus of encrypted documents stored on an untrusted storage device. The method also includes accessing, by the data processing hardware, a count table to obtain a count of unique documents within the corpus of encrypted documents that include the keyword and generating, by the data processing hardware, a delegatable pseudorandom function (DPRF) based on the keyword, a private cryptographic key, and the count of unique documents that include the keyword. The method also includes evaluating, by the data processing hardware, a first portion of the DPRF and delegating, by the data processing hardware, a remaining second portion of the DPRF to the untrusted storage device. The remaining second portion of the DPRF when received by the untrusted storage device causes the untrusted storage device to evaluate the remaining second portion of the DPRF and access an encrypted search index associated with the corpus of encrypted documents stored on the untrusted storage device. The untrusted storage device also determines one or more encrypted documents within the corpus of encrypted documents associated with the remaining second portion of the DPRF based on the encrypted search index and returns, to the user device, an identifier for each encrypted document of at least a portion of the one or more encrypted documents associated with the remaining second portion of the DPRF.

Implementations of the disclosure may include one or more of the following optional features. In some implementations, generating the DPRF includes generating a binary tree where the binary tree includes a set of nodes that includes a root node and a plurality of other nodes. Each other node includes a non-leaf node or a leaf node. The method may also include where a quantity of leaf nodes of the binary tree is equal to or greater than the count of unique documents that include the keyword.

In some examples, the root node of the binary tree includes a first hash of the private cryptographic key and the keyword. The root node may be associated with a first child node and a second child node, where the first child node includes a first portion of a second hash of the first hash of the private cryptographic key and the keyword, and the second child node includes a second portion of the second hash of the first hash of the private cryptographic key and the keyword. Optionally, the first portion of the second hash concatenated with the second portion of the second hash is equivalent to the second hash of the first hash of the private cryptographic key and the keyword.

Each leaf node of the set of nodes of the binary tree may be associated with a value stored in the encrypted search index. Each other node of the set of nodes of the binary tree may include a portion of a hash of a parent node associated with the corresponding other node. In some implementations, evaluating the first portion of the DPRF includes evaluating a first subset of the set of nodes of the binary tree. When the untrusted storage device evaluates the remaining second portion of the DPRF, the untrusted storage device evaluates a second subset of the set of nodes of the binary tree. The second subset includes different nodes from the set of nodes of the binary tree than the first subset.

In some examples, the method further includes, for each unique keyword of a new encrypted document uploaded by the user into the corpus of encrypted documents stored on the untrusted storage device, incrementing, by the data processing hardware, the count of unique documents within the corpus of encrypted documents that include the corresponding unique keyword in the count table and generating, by the data processing hardware, a unique keyword hash based on the private cryptographic key, the corresponding unique keyword, and the incremented count of unique documents within the corpus of encrypted documents that include the corresponding unique keyword. The method may also include generating, by the data processing hardware, a hash pair including the unique keyword hash and an encrypted document identifier associated with the new encrypted document uploaded by the user and sending, by the data processing hardware, the hash pair to the untrusted storage device.

When the untrusted storage device returns the identifier for each encrypted document of the at least the portion of the one or more encrypted documents associated with the remaining second portion of the DPRF, the untrusted storage device may return encrypted metadata associated with each returned identifier.

Another aspect of the disclosure provides a system for providing encrypted search with no zero-day leakage. The system includes data processing hardware of a user device associated with a user and memory hardware in communication with the data processing hardware. The memory hardware stores instructions that when executed on the data processing hardware cause the data processing hardware to perform operations. The operations include receiving a search query for a keyword. The keyword appears in one or more encrypted documents within a corpus of encrypted documents stored on an untrusted storage device. The operations also include accessing a count table to obtain a count of unique documents within the corpus of encrypted documents that include the keyword and generating a delegatable pseudorandom function (DPRF) based on the keyword, a private cryptographic key, and the count of unique documents that include the keyword. The operations also include evaluating a first portion of the DPRF and delegating a remaining second portion of the DPRF to the untrusted storage device. The remaining second portion of the DPRF when received by the untrusted storage device causes the untrusted storage device to evaluate the remaining second portion of the DPRF and access an encrypted search index associated with the corpus of encrypted documents stored on the untrusted storage device. The untrusted storage device also determines one or more encrypted documents within the corpus of encrypted documents associated with the remaining second portion of the DPRF based on the encrypted search index and returns, to the user device, an identifier for each encrypted document of at least a portion of the one or more encrypted documents associated with the remaining second portion of the DPRF.

This aspect may include one or more of the following optional features. In some implementations, generating the DPRF includes generating a binary tree where the binary tree includes a set of nodes that includes a root node and a plurality of other nodes. Each other node includes a non-leaf node or a leaf node. The operations may also include where a quantity of leaf nodes of the binary tree is equal to or greater than the count of unique documents that include the keyword.

In some examples, the operations further include, for each unique keyword of a new encrypted document uploaded by the user into the corpus of encrypted documents stored on the untrusted storage device, incrementing the count of unique documents within the corpus of encrypted documents that include the corresponding unique keyword in the count table and generating a unique keyword hash based on the private cryptographic key, the corresponding unique keyword, and the incremented count of unique documents within the corpus of encrypted documents that include the corresponding unique keyword. The operations may also include generating a hash pair including the unique keyword hash and an encrypted document identifier associated with the new encrypted document uploaded by the user and sending the hash pair to the untrusted storage device.

Searchable encryption (which may also be referred to as encrypted search) has been increasing in popularity. The goal of searchable encryption is to enable a client to outsource the storage of a corpus of encrypted documents to an untrusted server. For example, the client may wish to store a large number of documents (or any other item uploaded to the server, such as pictures, emails, etc.) securely in a cloud-based storage solution. The term documents is used generally, and may represent any sort of digital files (e.g., pictures, songs, database entries, etc.). Typically, the client will want to keep the ability to efficiently search the documents (i.e., search for a specific keyword), while simultaneously maintaining the privacy and security of the documents that encryption provides. In order to maintain this privacy, information related to the contents of the documents or the queries from the client must remain hidden from the untrusted server. A common way to address this problem is the creation of a separate encrypted search index that indexes the keywords and associated document identifiers of all of the documents stored on the untrusted server.

This search index is encrypted with a key the untrusted server does not have access to, and then stored along with the documents. The client may then generate a search query that the server evaluates against the encrypted search index. The evaluation results in the encrypted document identifiers associated with the keyword of the search query, which the untrusted server returns to the client. In this way, the client receives a list of document identifiers of documents that include the keyword while minimizing information leakage (e.g., to the untrusted server).

As the untrusted server evaluates the search index in response to queries from the user, the index will gradually leak information about search patterns and, by deploying attacks such as frequency analysis, the server may eventually be able to make informed guesses on the historical searched terms with non-negligible probability. This leakage cannot be efficiently prevented as it is an inherent problem due to the searching repeatedly over the same index.

However, many searchable encryption schemes suffer from a number of additional security or privacy concerns beyond this slow leakage of using the search index. In one example, some schemes are vulnerable to zero-day attacks. A zero-day attack is an attack that reveals or leaks information to an adversary (e.g., the untrusted storage server) before any queries have been processed by the storage server. That is, search queries (i.e., searching for a keyword among the encrypted documents) typically leak at least some information to the server. However, a successful zero-day attack does not require any search queries at all to gain information about the encrypted documents.

For example, some searchable encryption schemes hash each keyword in a document into one or more small values that are attached to each encrypted document. To search for the keyword, each associated hash value may be searched. However, this scheme reveals to the server a frequency table of the number of documents (as well as the identifier of the documents) that contain a specific hash value. For example, a hash value associated with a lot of documents is likely to be a more common word than a hash value that is associated with less documents. This information is revealed to the server before any search queries have been performed. Study has shown that frequency tables can reveal a large number of keywords. While the schemes may attempt to mitigate this weakness (e.g., by adding random terms), a significant amount of noise must be added to ensure that the frequency problem is overcome, which significantly reduces the efficiency of the scheme.

Another common security issue that many searchable encryption schemes are vulnerable to are file-injection attacks. These attacks work on the premise that an adversary may send encrypted documents (e.g., emails) to a target. These emails will contain specific keywords. When the target queries for these specific keywords, the adversary may view which of the injected emails are returned and thus determine the queried keyword. In some instances, the adversary may even hide the identity of the injected emails by hiding keywords that may notify the target via, for example, invisible Hypertext Markup Language (HTML). This attack may be compounded if the adversary is able to save the queries that the target performs (or retrieve queries that were performed from a log). The adversary may then apply all these historical queries to emails that were recently injected (i.e., injected after the queries were performed) to compromise the privacy of queried keywords for historical queries. Thus, when the scheme uses the same hash for all emails in the past or future, the scheme is vulnerable to an adversary applying all previous queries into files that were only injected recently.

In order to mitigate zero-day attacks and file-injection attacks of encrypted documents while maintaining search functionality and efficiency, implementations herein are directed toward an encrypted search scheme using delegatable pseudorandom functions (DPRF) to completely hide frequency tables before any search queries have been performed.

Referring now to <FIG>, in some implementations, an example system <NUM> includes a user device <NUM> associated with a respective user or client <NUM> and in communication with an untrusted remote system <NUM> via a network <NUM>. The user device <NUM> may correspond to any computing device, such as a desktop workstation, a laptop workstation, or a mobile device (i.e., a smart phone). The user device <NUM> includes computing resources <NUM> (e.g., data processing hardware) and/or storage resources <NUM> (e.g., memory hardware).

The remote system <NUM> may be a single computer, multiple computers, or a distributed system (e.g., a cloud environment) having scalable / elastic computing resources <NUM> (e.g., data processing hardware) and/or storage resources <NUM> (e.g., memory hardware). An untrusted document data store <NUM> (i.e., a remote storage device <NUM>) is overlain on the storage resources <NUM> to allow scalable use of the storage resources <NUM> by one or more of the client or computing resources <NUM>. The document data store <NUM> is configured to store a corpus of documents <NUM>, 152a-n. Each document <NUM> includes a document identifier <NUM> that uniquely identifies the associated document <NUM> (e.g., a document name). Each document <NUM> also includes a set of keywords <NUM>. The set of keywords <NUM> includes all keywords that appear in the associated encrypted document <NUM> that the user <NUM> may search for. As used herein, a document <NUM> may refer to any item uploaded onto the remote system <NUM> for storage within the document data store <NUM>, such as, without limitation, emails, calendar events, notes, database entries, pictures, audio files, etc. In some examples, the untrusted storage device <NUM> stores a corpus of emails <NUM>, and the user <NUM>, via the user device <NUM>, accesses an inbox for receiving and composing emails. In some implementations, the user device <NUM> executes a Searchable Encryption (SE) manager <NUM> for managing access to the encrypted documents <NUM> within the data storage <NUM>.

The user <NUM> may interact with the SE manager <NUM> via a software application (e.g., a web browser) executing on the user device <NUM>.

The SE manager <NUM> receives, from the user <NUM>, a search query <NUM> for one or more keywords <NUM> that appear in one or more of the encrypted documents <NUM> stored on the untrusted storage device <NUM>. The SE manager <NUM> accesses a count table <NUM> to obtain a count <NUM> of unique documents <NUM> within the corpus of encrypted documents <NUM> that include the keyword <NUM>. That is, the count <NUM> indicates the number of unique documents <NUM> that the keyword <NUM> appears in. For example, when the queried keyword <NUM> is "cat", and "cat" appears in <NUM> different documents <NUM> stored on the storage device <NUM> and associated with the user <NUM>, the count <NUM> would be <NUM>.

Referring now to <FIG>, a schematic view <NUM> shows the SE manager <NUM> receiving the keyword count <NUM> of the queried keyword <NUM> from the count table <NUM>. The count table <NUM> includes a count <NUM> of how many different documents <NUM> that the keyword <NUM> appears in. In the illustrated example, the keyword "cat" appears in <NUM> documents <NUM>, the keyword "dog" appears in <NUM> different documents <NUM>, and the keyword "yak" appears in <NUM> different documents <NUM>. In some examples, the count table <NUM> may be encrypted and the SE manager <NUM> may decrypt either the count table <NUM> and/or count <NUM> using a cryptographic key. As discussed in more detail below with reference to <FIG>, the count table <NUM> may be stored locally at the user device <NUM> or remotely (e.g., at the untrusted storage device <NUM>). To maintain privacy, the count table <NUM> must remain secret, and therefore will generally be encrypted, especially when stored remotely from the user device <NUM>.

Referring back to <FIG>, the SE manager <NUM> also obtains a private cryptographic key <NUM>. In some examples, the SE manager <NUM> generates the private key <NUM>. In other examples, the SE manager <NUM> retrieves or receives the private key <NUM> from the user device <NUM> or from a third-party (e.g., a third-party key management service). The SE manager <NUM> generates a delegatable pseudorandom function <NUM> (DPRF) based on the keyword <NUM>, the private cryptographic key <NUM>, and the count <NUM> of unique documents <NUM> that include the keyword <NUM>. When the user <NUM> queries for more than one keyword <NUM>, the SE manager <NUM> may generate a separate DPRF <NUM> for each keyword <NUM>.

As used herein, a DPRF is a function that, using an in input cryptographic key K and an input x, generates an output F(K, x) that appears random to any party that does not have access to the key K. Specifically, the DPRF <NUM> allows for delegation of evaluation of a strict subset of the domain of the function to an untrusted proxy without the proxy being able to evaluate the function outside of the strict subset.

As an example, assume that a user desires to retrieve values stored on a server that are associated with a large number of outputs from the function F. That is, the user wants the server to retrieve or evaluate values associated with F(K, x<NUM>),. , F(K, xm) that are stored on the server. The user could simply send the function F, the key K, and the range of values for x to the server and the server could evaluate the range of values for x to obtain the outputs. However, in this scenario, the server then could evaluate the function F for any value of x, as the server has access to the key K. Another possible avenue for the user is to evaluate each value of x themselves and then send each output to the server. While this limits the information the server receives, it requires sending of m outputs, which is highly inefficient.

Ideally, the user would like to minimize the amount of information the user must send the server while also minimizing the amount of information the server learns. The DPRF <NUM>, as described in more detail with regards to <FIG> below, is a function that bounds the server from evaluating values of x outside of a specified range, thus limiting the amount of information the sever gains. For example, when the user sends the range values of x<NUM> to xm for the sever to evaluate, the server will not be able to evaluate the function F for values of x less than x<NUM> and for values of x greater than xm. To establish these bounds, the SE manager <NUM> evaluates a first portion 126A of the DPRF <NUM> and delegates a remaining second portion 126B of the DPRF to the untrusted storage device <NUM>.

Referring again to <FIG>, the SE manager <NUM>, in some implementations, includes a DPRF generator <NUM> and a DPRF evaluator <NUM>. The DPRF generator <NUM> generates the DPRF <NUM> for the queried keyword <NUM> based on the private key <NUM>, the keywords <NUM>, and the keyword count <NUM> received from the count table <NUM>. The DPRF generator <NUM> passes the DPRF <NUM> to the DPRF evaluator <NUM>. The DPRF evaluator <NUM>, as described in more detail below with reference to <FIG>, evaluates at least a portion of the DPRF <NUM> (e.g., a first portion 126a), and based on the portion evaluated, delegates (i.e., sends) the remaining second portion 126B to the untrusted remote storage device <NUM>.

Referring back to <FIG>, the untrusted storage device <NUM> (i.e., the document data store <NUM> storing the encrypted documents <NUM> store), in response to receiving the remaining second portion 126B of the DPRF <NUM> delegated by the DPRF evaluator of the SE manager <NUM>, evaluates the remaining second portion 126B of the DPRF and accesses an encrypted search index <NUM> associated with the corpus of encrypted documents <NUM> stored on the untrusted storage device <NUM>. The storage device <NUM> determines one or more encrypted documents <NUM> within the corpus of encrypted documents that are associated with the remaining second portion 126B of the DPRF based on the encrypted search index <NUM>.

The encrypted search index <NUM>, in some implementations, includes a list of entries <NUM>, 162a-n, where each entry <NUM> includes an association between a keyword <NUM> and at least one encrypted document identifier <NUM> that the keyword <NUM> appears in. The evaluation of the remaining second portion 126B provides the untrusted storage device <NUM> with one or more of the encrypted keywords <NUM> associated with one or more encrypted document identifiers <NUM> without revealing the plaintext keyword or document identifier to the storage device <NUM>. The storage device <NUM> returns, to the user device <NUM>, an identifier <NUM> for each encrypted document <NUM> of at least a portion of the one or more encrypted documents <NUM> associated with the remaining second portion 126B of the DPRF. That is, in some implementations, the storage device <NUM> does not return every identifier <NUM> associated with a document <NUM> containing the queried keyword <NUM>, and instead only returns a portion (e.g., fifty) of the document identifiers <NUM>. Subsequent queries <NUM> made by the user <NUM> may return additional results (e.g., the next fifty document identifiers <NUM>). In some examples, the storage device <NUM> returns to the user device <NUM> an empty set (i.e., returns no document identifiers <NUM>) when, for example, the queried keyword <NUM> does not appear in any of the documents <NUM>.

In some implementations, when the untrusted storage device <NUM> returns at least a portion of the document identifiers <NUM> associated with encrypted documents <NUM> that includes the queried keyword <NUM>, the untrusted storage device also returns encrypted metadata <NUM> associated with each returned identifier <NUM>. The metadata <NUM> may include additional relevant or contextual information for the user <NUM>. For example, the metadata <NUM> may include dates (e.g., a date the document <NUM> was created or uploaded), the author of the document <NUM>, size of the document <NUM>, a sentence that includes the keyword <NUM>, etc..

Referring now to <FIG>, as previously discussed, the SE manager <NUM> generates the DPRF <NUM> to solve for a range of values from F(K, x<NUM>),. , F(K, xm) by generating a binary tree <NUM>. In some examples, the key K is associated with a specific keyword <NUM> and each x value of the DPRF <NUM> represents one of the documents <NUM> that the select keyword <NUM> appears in. For example, if the select keyword <NUM> is "cat", and the count value <NUM> associated with "cat" is <NUM>, then cat appears in <NUM> unique documents <NUM>. In this example, x would have a maximum size of <NUM> (e.g., <NUM> to <NUM>) and each x would represent one of the documents <NUM> the keyword <NUM> appears in. Each value of F(K, x) is then associated with a value stored in the encrypted search index <NUM> that represents a document identifier <NUM> that the select keyword <NUM> appears in.

Thus, for the SE manager <NUM> to retrieve all of the documents <NUM> with the keyword "cat", the SE manager <NUM> and/or the untrusted storage device <NUM> may evaluate the DPRF <NUM> from F(K, <NUM>),. , F(K, <NUM>). Each of the <NUM> results are associated with a different value stored in the encrypted search index <NUM>. In another example, the SE manager <NUM> may retrieve only a portion of the <NUM> documents <NUM> that include the keyword "cat". In this examples, the SE manager <NUM> and/or the untrusted storage device <NUM> would evaluate only a portion of the DPRF <NUM>. For instance, to retrieve fifty documents <NUM>, the SE manager <NUM> and/or the untrusted storage device <NUM> may evaluate F(K, <NUM>),. , F(K, <NUM>). Each of the fifty results are again associated with a different value stored in the encrypted search index <NUM>. Similarly, to retrieve the next fifty documents, the SE manager <NUM> and/or the untrusted storage device <NUM> may evaluate F(K, <NUM>),. , F(K, <NUM>) and so on. In this way, the SE manager <NUM> and the untrusted storage device <NUM> may evaluate the DPRF <NUM> to obtain results associated with values within the encrypted search index <NUM> (i.e., entries <NUM>). The untrusted storage device <NUM> may return all or some of the values associated with the results to the SE manager <NUM>.

In some implementations, the SE manager <NUM>, in response to receiving a search query <NUM>, generates a DPRF <NUM> associated with the queried keyword <NUM> by generating the binary tree <NUM>. In other implementations, the SE manager <NUM> generates a binary tree <NUM> for each keyword <NUM> in the count table <NUM> prior to receiving a search query <NUM>. A binary tree is a tree data structure with a plurality of nodes where each node in the structure has at most two children. The binary tree <NUM> includes a set of nodes <NUM> that includes a root node 310R and a plurality of other nodes <NUM>. The other nodes <NUM> are either non-leaf nodes 310NL or leaf nodes <NUM>. Each input value of x is uniquely assigned a leaf node <NUM> in ascending order. A quantity of leaf nodes <NUM> of the binary tree <NUM> may be equal to or greater than the count of unique documents <NUM> that include the associated keyword <NUM>. For example, if the keyword "cat" has a count value <NUM> of <NUM>, the SE manager <NUM> may generate a binary tree <NUM> for the keyword "cat" that has at least <NUM> leaf nodes <NUM><NUM>. Each of the <NUM> instances of "cat" is associated with a specific leaf node <NUM>.

Each node <NUM> is also associated with a value <NUM>, 330A-N which herein may be referred to generally as "tokens". In some implementations, the value <NUM> of each leaf node <NUM> is associated with a value within an entry <NUM> of the encrypted search index <NUM>. That is, each value <NUM> of each leaf node <NUM> of the binary tree <NUM> is associated with a value within the encrypted search index <NUM> that is associated with the corresponding keyword <NUM>. Returning to the example of the keyword <NUM> "cat", each of the <NUM> leaf nodes <NUM> in the binary tree <NUM> generated for the keyword <NUM> "cat" may be associated with a value stored in the encrypted search index <NUM> and each of the associated values with the encrypted search index <NUM> corresponds to a document identifier <NUM> of a document <NUM> that includes the keyword <NUM> "cat".

In some implementations, the value <NUM> of root node 310R of the binary tree <NUM> is a value of a first hash <NUM> of the private cryptographic key <NUM> and the keyword <NUM> associated with the binary tree <NUM>. Thus, each binary tree <NUM> will have a unique value 330R for each root node 310R for each binary tree <NUM> generated for a corresponding keyword <NUM>. Each root node 310R is associated with a first child node (e.g., node 'B' in <FIG>) and a second child node (e.g., node 'C' in <FIG>). The first child node includes a first portion 330B of a second hash <NUM>, 342a of the first hash <NUM> of the private cryptographic key <NUM> and the keyword <NUM>, and the second child node includes a second portion 330C of the second hash <NUM> of the first hash <NUM> of the private cryptographic key <NUM> and the keyword <NUM>. That is, in some examples, the value 330A of the root node 310R is the first hash <NUM> of the key <NUM> and the keyword <NUM>. This value (labeled 'A' in <FIG>) is then hashed (e.g., using SHA256) and the resulting second hash 342a is split into the first portion 330B and the second portion 330C. As used herein, the terms "hash" and "hash function" are used to indicate any one-way function (i.e., a function where the input cannot be determined from the output) and as such, is equally applicable to encryption operations (e.g., Advanced Encryption Standard (AES)) in addition to hash operations.

In some examples, the first portion 330B of the second hash <NUM> concatenated with the second portion 330C of the second hash <NUM> is equivalent to the second hash <NUM> of the first hash <NUM> of the private cryptographic key <NUM> and the keyword <NUM>. As illustrated in <FIG>, the second hash <NUM> (e.g., a SHA256 hash) is a hash of 330A (i.e., the root node 310R value 330A) and is equal to 'B' ∥ 'C' (i.e., value 330B concatenated with value 330C). For example, the output of the SHA256 hash is a <NUM> bit number. The value 330B may be equivalent to the first <NUM> bits of the SHA256 output while the value 330C may be equivalent to the last <NUM> bits of the SHA256 output. Thus, the value 330B concatenated with the value 330C is equivalent to the hash <NUM> of the value of 330A.

In some implementations, each other node <NUM> of the binary tree <NUM> includes a portion of a hash <NUM> of a parent node <NUM> associated with the corresponding other node <NUM>. That is, for each non-root node 310R of the binary tree <NUM> (i.e., all non-leaf nodes 310NL and all leaf nodes <NUM>), the value <NUM> of the node <NUM> may be a portion of a hash <NUM> of the parent node. With continued reference to <FIG>, node 'B' (as with root node 310R node 'A") has two child nodes <NUM>, node 'D' and node 'E'. Node 'C' also has <NUM> child nodes <NUM>, node 'F' and node 'G'. As node 'D', node 'E', node 'F', and node 'G' have no child nodes <NUM>, in this example each of these four nodes is a leaf node <NUM>. As previously discussed, the value 330B of node 'B' may be the first portion of the hash 342A of the value 330A of node 'A'. Similarly, the value 330B of node `B' may be hashed (again with, for example, SHA256) and the resulting hash 342b may be split into a first portion 330D and a second portion 330E, each assigned as a value <NUM> of one of the two child nodes <NUM> (node 'D' and node `E'). Also as previously discussed, the value 330C of node 'C' may be the second portion of the hash 342A of the value 330A of the node 'A'. Likewise, the value 330C of node 'C' may be hashed (e.g., with SHA256) and the resulting hash 342c may be split into a first portion 330F and a second portion <NUM>, each assigned as a value <NUM> of one of the two child nodes <NUM> (node 'F' and node 'G'). While in the illustrated example, the binary tree <NUM> stops at these nodes, the binary tree may continue on for any number of nodes <NUM> until there are a sufficient number of leaf nodes <NUM> to account for the count value <NUM> of the associated keyword <NUM>.

To retrieve all of the document identifiers <NUM> associated with each leaf node <NUM> (i.e., every document identifier <NUM> associated with a document <NUM> that includes the queried keyword <NUM>), the SE manager <NUM> may simply send the token of node 'A' (e.g., a hash of the key <NUM> and the keyword <NUM>) and the count value <NUM> and allow the untrusted storage device <NUM> to determine the value for each leaf node <NUM><NUM>. In the example where the SE manager <NUM> needs to only retrieve a portion of the documents identifiers <NUM> associated with the keyword <NUM>, the SE manager <NUM> may evaluate the first portion 126A and delegate just the second portion 126B to the untrusted storage device <NUM> to limit the information leaked to the untrusted storage device <NUM>. For example, when the documents <NUM> include emails, the user <NUM>, when querying for a keyword <NUM>, may receive the <NUM> most recent emails that include the queried keyword <NUM> and only if the user indicates a desire for more results will additional emails be returned.

In some implementations, the document identifiers <NUM> are ordered chronologically (e.g., the document identifier <NUM> associated with the first leaf node <NUM> is the oldest document while the document identifier <NUM> associated with the last leaf node <NUM> is the newest document or vice versa), a range of leaf nodes <NUM> starting at the bottom left or the bottom right of the binary tree may be associated with the newest or oldest documents <NUM> associated with the keyword <NUM>. This allows for returning only a portion of the document identifiers <NUM> associated with the queried keyword <NUM> (e.g., the fifty most recent documents <NUM>) without the need look up each keyword <NUM> instance in the search index <NUM>. This may drastically reduce the total amount of computation required. While in this example, chronological ordering is illustrated, the document identifiers <NUM> may of course be ordered based on any other desired criteria.

With continued reference to <FIG>, in the example where the SE manager <NUM> needs only to retrieve the document identifiers <NUM> associated with the tokens 330D, 330E of node 'D' and node 'E', it is ideal to refrain from giving the untrusted storage device the information necessary to determine the values of node 'F' and node 'G', as these nodes are unnecessary for the query <NUM>. In this case, the SE manager <NUM> may evaluate a first subset of the nodes <NUM> of the binary tree <NUM> and the untrusted storage device <NUM> may evaluate a second subset of the nodes <NUM> of the binary tree <NUM> that is different from the subset that that the SE manager <NUM> evaluated.

For example, when the SE manager <NUM>, instead of providing the untrusted storage device <NUM> with the value 330A of the root node 310R, provides the untrusted storage device <NUM> with the value 330B of node 'B', the untrusted storage device <NUM> may evaluate the DPRF <NUM> (e.g., the binary tree <NUM>) using the token 330B of node 'B' to obtain the values 330D, 330E of the leaf nodes <NUM> node 'D' and node 'E'. Because the hash function used to obtain the token 330B is a one-way function, the untrusted storage device <NUM> is not able to use that value to obtain the value 330A of the root node 310R and thus the tokens 330C, 330F, <NUM> of node 'C', node 'F', and node 'G'. Thus, by determining a minimal number of nodes <NUM> whose union of leaf nodes <NUM> covers exactly (and only) the set of values <NUM> that correspond to the range of document identifiers <NUM> to be retrieved, the amount of information provided to the untrusted storage device <NUM> is minimized while bandwidth requirements are kept low. To return additional document identifiers <NUM>, the SE manager <NUM> may follow up by sending additional values <NUM> to the untrusted storage device (e.g., the value 330C of node 'C' to obtain the values 330F, <NUM> of node 'F' and node 'G').

In some implementations, each entry <NUM> of the encrypted index <NUM> is an association between exactly one keyword <NUM> and one document identifier <NUM>. However, in some implementations, the search index <NUM> may be optimized without reducing privacy. Instead of each entry <NUM> of the encrypted index <NUM> including an association between one keyword <NUM> and one document identifier <NUM>, each entry <NUM> may include an association between one keyword <NUM> and a plurality of document identifiers <NUM>. That is, each entry <NUM> associates a keyword <NUM> to multiple document identifiers <NUM> that the keyword <NUM> appears in. Note that if there was no limit to how many document identifiers <NUM> each entry <NUM> could associate with a single keyword <NUM>, the search index would risk leaking frequency table information. To mitigate this risk, each entry <NUM> may be limited to a maximum number of document identifiers. For example, each entry <NUM> may be limited to fifty or one hundred document identifiers <NUM>. In practice, this ensures that keywords with large frequencies (i.e., appear in many documents <NUM>) will be split into many different entries <NUM> in the search index <NUM>.

In some examples, the maximum number of document identifiers may be dynamically changed based on the frequency of the keywords <NUM>. As the frequency of the keyword <NUM> increases (i.e., the keyword <NUM> is more common in the documents <NUM>), the size of the maximum number of document identifiers may increase. As a result, the untrusted storage device <NUM> does not have to process as many hashes. The count table <NUM> may be used to keep track of the maximum number of document identifiers for each keyword <NUM> as well as the number of document identifiers <NUM> currently associated with each entry <NUM>. Optionally, instead of the count table <NUM> tracking the number of document identifiers <NUM> currently associated with each entry <NUM>, the SE manager <NUM>, each time a new keyword <NUM> is added, a SE manager <NUM> may create new entry <NUM> and add the keyword <NUM> to the new entry <NUM> based on a keyword probability. This leads to, on average, an expected number of document identifiers <NUM> to be added to the entry <NUM> prior to the creation of another new entry <NUM>. In this way, the count table <NUM> does not need to track the number of document identifiers <NUM> assigned to each entry <NUM>, thus reducing the size of the count table <NUM>.

Referring now to the schematic view <NUM> of <FIG>, in some examples, the SE manager <NUM> receives a disjunctive, conjunctive, or negation search query 122D, 122C, 122N. A disjunctive query 122D includes a query of two or more keywords <NUM> combined with a logical OR. For example, a disjunctive query 122D may include a query for "cat" OR "dog" and should result in returning any document identifiers <NUM> associated with documents <NUM> that include either or both the keyword "cat" and the keyword "dog". For disjunctive queries 122D, the SE manager <NUM> may generate a DPRF <NUM> and a corresponding portion 126B, 126Ba-n for each keyword <NUM> separately. After receiving the document identifiers <NUM> for each keyword <NUM> at the user device <NUM>, the SE manager <NUM> may combine the results and, in some implementations, rank the results using any metadata <NUM> returned with the document identifiers <NUM>.

A conjunctive query 122C includes a query of two or more keywords <NUM> combined with a logical AND. For example, a conjunctive query 122C may include a query for "cat" AND "dog" and should result in returning any document identifiers <NUM> that are associated with documents <NUM> that include both "cat" and "dog". Similar to the disjunctive query 122D, for conjunctive queries 122C, the SE manager <NUM> may generate a DPRF <NUM> and a corresponding portion 126B for each keyword <NUM> separately. After receiving the document identifiers <NUM> for each keyword <NUM> at the user device <NUM>, the SE manager <NUM> may return to the user <NUM> only document identifiers <NUM> that were returned for each keyword <NUM>.

A negation query 122N includes a query for results that do not include one or more keywords <NUM>. For example, a negation query 122N may include a query for all documents <NUM> that do not include the keyword "cat. " For negation queries 122N, the SE manager <NUM> may generate a DPRF <NUM> and corresponding portion 126B for the negated keyword <NUM>. After receiving the results for the negated keyword <NUM>, the SE manager <NUM> may retrieve all document identifiers <NUM> and remove from the list the identifiers <NUM> associated with the negated keyword <NUM>, and return the remaining results to the user <NUM>. Using the above described methods for disjunctive queries 122D, conjunctive queries 122C, and negation queries 122N, complex queries <NUM> that combine or include multiple different types of queries may be resolved with the same techniques by splitting the complex query into multiple simpler queries.

Referring now to <FIG>, in some examples, the system <NUM> shows the user <NUM> adding/uploading a new document 152N to the corpus of encrypted documents <NUM> stored on the untrusted storage device <NUM>. In this situation, the encrypted search index <NUM> is updated with the keywords <NUM> present in the newly added document <NUM>. The new document 152N is associated with a new document identifier 154N. In some implementations, for each unique keyword <NUM> of the new encrypted document 152N uploaded by the user <NUM> into the corpus of encrypted documents <NUM> stored on the untrusted storage device <NUM>, the SE manager <NUM> increments the count <NUM> of unique documents <NUM> within the corpus of encrypted documents <NUM> that include the corresponding unique keyword <NUM> in the count table <NUM>. For example, when the new document 152N includes the keyword "cat", and the current count <NUM> associated with the keyword "cat" is <NUM>, the count <NUM> is incremented to <NUM>.

The SE manager <NUM>, in some examples, generates a unique keyword hash <NUM> based on the private cryptographic key <NUM>, the corresponding unique keyword <NUM>, and the incremented count <NUM> of unique documents <NUM> within the corpus of encrypted documents that include the corresponding unique keyword <NUM>. For example, the SE manager <NUM> may use a hash function <NUM> to compute Hkw = F(K∥kw, cntkw), where Hkw represents the hash value <NUM>, K represents the private key <NUM>, kw represents the keyword <NUM>, and cntkw represents the incremented count <NUM>. Any suitable one-way function or algorithm may be used to hash or encrypt the keyword <NUM> (e.g., SHA256).

The SE manager <NUM> may also generate a hash pair <NUM> that includes the unique keyword hash <NUM> and an encrypted document identifier 154N (i.e., the SE manager <NUM> hashes or encrypts the new document identifier 154N) associated with the new encrypted document <NUM> uploaded by the user <NUM>. The SE manager <NUM> sends the hash pair <NUM> to the untrusted storage device <NUM>. The SE manager <NUM> may generate a separate and unique hash pair <NUM> for each unique keyword <NUM> within the newly uploaded document 152N.

Draft documents <NUM> (e.g., emails that are saved without sending or are actively being composed) are typically saved frequently (e.g., every few seconds) by the user device <NUM>. The SE manager <NUM> may update the search index <NUM> at the same frequency as the draft is saved or at a different frequency. For example, when the draft is saved every <NUM> seconds, the SE manager <NUM> may update the encrypted search index <NUM> every <NUM> minutes. In some implementations, the SE manager <NUM> may update the encrypted search index <NUM> at the same rate as the draft is saved, but update the count table <NUM> at a slower frequency. In this case, tokens <NUM> may temporarily be reused for updating the search index <NUM> until the count table <NUM> is updated at a future time.

When the documents <NUM> stored on the untrusted storage device <NUM> are emails, the SE manager <NUM> may automatically add received emails at the user device <NUM> to the corpus of encrypted emails on the untrusted storage device. In some examples, emails that have been received, but not yet opened, are not added to the search index <NUM>. That is, in some examples, the SE manager <NUM> automatically adds opened emails to the search index <NUM>. In this way, an email may be revoked by the sender without the SE manager <NUM> and/or the untrusted storage device <NUM> inferring content of the revoked email from the keywords <NUM>.

Referring now to <FIG>, similar to adding a document <NUM>, the system <NUM> shows the SE manager <NUM>, in some implementations, receiving a deletion request <NUM> to delete a document <NUM> from the untrusted storage device <NUM>. In this case, the SE manager <NUM> retrieves each keyword <NUM> present in the document <NUM> to be deleted (e.g., from the untrusted storage device <NUM>) and, for each keyword <NUM>, decrements the corresponding count <NUM> in the count table <NUM>. The SE manager then instructs the untrusted storage device to delete the values within the encrypted search index associated with the deleted document 152D. For example, the SE manager <NUM> may generate a hash <NUM> of the private key <NUM>, the keyword <NUM>, and the appropriate count <NUM> (or other identifier) using a hash function <NUM> to generate a hash pair <NUM> with the document identifier <NUM>. The SE manager <NUM> may send the hash pairs <NUM> to the untrusted storage device <NUM> to indicate to the untrusted storage device which entries within the encrypted search index <NUM> to delete. The untrusted storage device <NUM> may run a periodic task to update the search index <NUM> at regular intervals. In some implementations, the untrusted storage device <NUM> keeps a list of all document identifiers <NUM> of deleted documents <NUM>, and prior to returning results from a search query <NUM>, removes any document identifiers <NUM> that are associated with deleted documents <NUM>.

Optionally, the untrusted storage device <NUM> may periodically compress (e.g., perform garbage collection) the search index <NUM> after one or more documents <NUM> have been deleted. After a document is deleted, the deleted document may create a "hole" at the count <NUM> associated with the deleted document <NUM>. The untrusted storage device <NUM> may move or shift entries in the search index <NUM> with higher counts <NUM> to ones of lower counts as the lower counts become available from document deletions. The resulting empty higher count entries may then be deleted from the search index <NUM>.

In some scenarios, the user <NUM> may desire to delete portions of a document <NUM> without deleting the entire document <NUM>. In this situation, some keywords <NUM> are removed from the document <NUM> and the encrypted search index <NUM> no longer accurately reflects the keywords <NUM> present in the modified documents <NUM>. In some implementations, a deletion index <NUM> includes reference to keywords <NUM> deleted from documents <NUM> stored within the corpus of encrypted documents on the untrusted data storage <NUM>. The deletion index <NUM> may be generated and maintained similarly to when new document keywords <NUM> are added to the search index <NUM>. Prior to the untrusted storage device <NUM> returning the document identifiers <NUM> associated with the queried keyword, the untrusted storage device may reference the deletion index <NUM> to determine if the deletion index <NUM> indicates that any of the document identifiers <NUM> include keywords <NUM> that have been deleted. The untrusted storage device <NUM> may remove document identifiers <NUM> that the deletion index indicates the queried keyword <NUM> was deleted from.

In order to prevent zero-day leakage (e.g., frequency table attacks), it is important that the plaintext of the count table <NUM> is not available to anyone other than the user <NUM>. However, it is also desirable that the user <NUM> have easy access to the count table <NUM> from a variety of user devices <NUM> simultaneously. There are a variety of methods for storing the count table <NUM> that address these concerns to varying degrees. For example, the count table may be stored only locally on the user device <NUM>. However, this implementation has significant drawbacks in that the user is limited to only the user device <NUM> that the count table <NUM> is stored on, and it would be difficult if not impossible to recover the count table <NUM> if the user device <NUM> loses it (e.g., the user device <NUM> crashes).

Another implementation is storing the count table <NUM> in an encrypted format on the untrusted storage device <NUM>. The count table <NUM> may be encrypted with a second private cryptographic key that is different from the private cryptographic key <NUM>, or alternatively the count table <NUM> may be encrypted with the same private key <NUM>. The user device <NUM> may then, when performing a query, first download the encrypted count table <NUM> from the untrusted storage server <NUM>, decrypt it, and perform the query. The user device <NUM> may send to the untrusted storage device <NUM> an updated count table <NUM> each time a document <NUM> is added or removed from the corpus of encrypted documents. This allows for synchronization between multiple user devices <NUM> and ensures backups in case a user device crashes, however, the bandwidth requirements may be significant, especially for some user devices (e.g., mobile phones). At the cost of greatly increased complexity, the untrusted storage device <NUM> may instead store incremental backups of the count table <NUM>. For example, the backup may be uploaded at regular intervals (e.g., once a day or every few hours). User devices may upload changes to the count table <NUM> (e.g., adding or deleting a document <NUM>) and the untrusted storage device <NUM> may track these changes to the count table <NUM> until the next backup upload.

Yet another implementation for storing the count table <NUM> involves storing an encrypted count table <NUM> on the untrusted storage device <NUM> and accessing encrypted entries of the count table <NUM>. For example, for each keyword <NUM>, the untrusted storage device <NUM> may store an identifier encrypted with a unique key that points to an encryption of the count <NUM> for that keyword. When the user <NUM> adds a document <NUM>, the user <NUM> requests the untrusted storage device to return the encrypted counts <NUM> associated with the identifier. The user device <NUM> may then perform a search as described above using the recovered counts <NUM>, and then send encrypted incremented counts back to the untrusted storage device <NUM> for the untrusted storage device <NUM> to update. This implementation provides protection from crashed user devices and minimizes the bandwidth required. However, logs of accessing the encrypted counts, if not properly deleted, may leak frequency information. This frequency information may allow for the generation of a frequency table which may be used in an attack.

In yet another implementation, the count table <NUM> is instead replaced with a single max count integer. The max count integer may be set to the largest count <NUM>. That is, the max count integer may be set the count <NUM> of the keyword <NUM> with the highest count <NUM> (i.e., appears in the most documents <NUM>). When searching for a keyword <NUM>, the SE manager <NUM> may delegate to the untrusted storage device <NUM> a DPRF <NUM> over the entire range up to the max count integer. The untrusted storage device may perform a search (e.g., a binary search) over the encrypted search index <NUM> to obtain the actual count <NUM> of the queried keyword <NUM>. For example, the untrusted storage device <NUM> may determine that the largest count value that matches a result in the encrypted search index <NUM> is the actual count <NUM> of the keyword. This implementation removes the need for the count table <NUM>, but increases the number of lookups the untrusted storage device <NUM> must perform on the encrypted search index <NUM> while also potentially degrading privacy, as logs of the search may leak a frequency of counts of keywords <NUM>.

In yet another implementation, the count table <NUM> is partitioned into a plurality of different access buckets. Here, the partitioning may use k-anonymity, whereby k-anonymity refers to a property of anonymized data where a specific member of a population cannot be readily identified or distinguished from the data.

Referring now to the schematic view <NUM> of <FIG>, in some implementations, the SE manager <NUM> divides the count table <NUM> into a plurality of buckets <NUM>, 710a-n and stores the buckets <NUM> on the untrusted storage device <NUM>. Here, each bucket <NUM> stores one or more counts <NUM> of unique documents <NUM> within the corpus of encrypted documents <NUM> that include a respective keyword <NUM>. That is, each keyword <NUM> and associated count <NUM> pair <NUM>, 712a-n (e.g., "cat" and <NUM>) are encrypted and assigned to a bucket <NUM> and each bucket is stored on the untrusted storage device <NUM>. The untrusted storage device <NUM> may host any number of buckets <NUM> and each bucket <NUM> may store any number of keyword-count pairs <NUM>, however each keyword-count pair <NUM> is only assigned to a single bucket <NUM>. The SE manager <NUM> may request a specific pair <NUM> (e.g., a count <NUM> for a specific keyword <NUM>) by generating and sending a bucket request <NUM> to the untrusted storage device <NUM> that indicates a specific bucket <NUM> of the plurality of buckets <NUM>. In response, the untrusted storage device <NUM> returns each pair <NUM> stored in the specific bucket <NUM>. In this way, the untrusted storage device <NUM> cannot discern the specific pair <NUM> from the bucket of pairs that the untrusted storage device <NUM> returned to the SE manager <NUM>. The SE manager <NUM> may determine which bucket <NUM> a pair <NUM> is assigned to by generating second DPRF <NUM> whose output domain is simply the number of buckets <NUM>.

The bandwidth required for bucketization is balanced against the strength of the anonymity the bucketization provides. That is, the greater the number of keyword and count pairs <NUM> per bucket <NUM> (i.e., when the total number of buckets <NUM> is small), the greater number of pairs <NUM> returned for each query <NUM>, the greater the anonymity, and the greater the bandwidth consumption. Conversely, the fewer the number of keyword and count pairs <NUM> per bucket <NUM> (i.e., when the total number of buckets <NUM> is large), the fewer number of pairs <NUM> returned for each query <NUM>, the less the anonymity, and the less the bandwidth consumption. This implementation ensures that, even if logs generated by the untrusted storage device are not deleted, the leakage is mitigated by the k-anonymity techniques. In particular, the leakage of frequencies occur at the granularity of buckets (which typically will contain k encrypted pairs <NUM>) and therefore the frequency leakage only leaks frequencies for groups of approximately k keywords <NUM>.

In some examples, the total number of buckets <NUM> is fixed. That is, the number of buckets <NUM> in use does not change and new keyword count pairs <NUM> are continually added to the same buckets <NUM>. Over time, as the number of keyword count pairs <NUM> per bucket increases, the overall bandwidth consumption of the bucketization technique similarly increases. In other examples, the number of buckets <NUM> is not fixed (i.e., dynamic bucketization). In this case, the output domain of the second DPRF <NUM> is a maximum number of buckets that may be deployed (e.g., <NUM>). As with the fixed bucket implementation, the second DPRF <NUM> is used to assign the keyword count pair <NUM> to the buckets <NUM>. To reduce the number of bucket <NUM> from the maximum amount assigned by the second DPRF <NUM> to a desired amount, different possible outputs of the second DPRF <NUM> may be combined into a single bucket <NUM>. That is, two or more buckets <NUM> may be dynamically associated together.

For example, if <NUM>,<NUM> is the maximum number of buckets, but the target number of buckets is <NUM>, every <NUM> buckets <NUM> may be combined, such that when a keyword-count pair <NUM> from one of the <NUM> buckets is requested, the untrusted storage device <NUM> will return all of the pairs <NUM> from each of the <NUM> buckets. Note that each group of buckets <NUM> does not have to constitute the same number of buckets <NUM>. For example, one group may be <NUM> buckets, while another group is <NUM> buckets. To increase or decrease the number of buckets <NUM>, the SE manager <NUM> may simply change the number of buckets <NUM> that are combined. This allows the SE manager <NUM> to dynamically change the number of buckets <NUM> in use without physically changing the underlying count table <NUM>. When the count table <NUM> is stored in a sorted order, dynamic bucketization also ensures that counts <NUM> that are placed into the same bucket <NUM> are logically nearby for efficiency purposes.

<FIG> shows a plot <NUM> depicting a likelihood of inserting a new keyword <NUM> into the count table <NUM> when a probability <NUM> to enter keyword is <NUM>. The plot <NUM> has an x-axis denoting a number of documents <NUM> with the same new keyword <NUM> and a y-axis denoting a probability or likelihood that the new keyword <NUM> is added to the count table <NUM>. As is apparent from the plot <NUM>, as the number of documents <NUM> with the new keyword <NUM> approaches <NUM>, the probability that the keyword <NUM> is entered approaches <NUM> percent. In some implementations, a size of the count table <NUM> is reduced by adding new keywords <NUM> to the count table <NUM> based on a probability. That is, when a new document 152N (<FIG>) is added to the corpus of encrypted documents stored on the untrusted storage device <NUM>, when the new document 152N contains a keyword <NUM> that is not already in the count table <NUM>, the SE manager <NUM> may determine whether to add the keyword <NUM> to the count table <NUM> based on a probability <NUM>. For example, the probability <NUM> that a new keyword <NUM> is added to the count table <NUM> may be <NUM> in <NUM> (i.e., <NUM> percent). When the SE manager <NUM> determines, based on the probability <NUM>, that the keyword <NUM> is to be added to the count table <NUM> (e.g., <NUM>% of the time), the keyword <NUM> is added as described with regards to <FIG>. When the SE manager <NUM> determines, based on the probability <NUM>, that the keyword <NUM> is not to be added to the count table <NUM>, the SE manager <NUM> may instead randomly assign the keyword <NUM> to a token <NUM> within a threshold range. In some examples, the threshold range may be the default number of documents identifiers <NUM> that are retrieved in response to a search query (e.g., fifty).

For example, when the SE manager <NUM> determines to not add a new keyword <NUM> to the count table <NUM>, the SE manager <NUM> may instead generate a hash pair <NUM> as described with regard to <FIG> using a random count value <NUM> between one and fifty. The new keyword <NUM>, as it is used in additional documents, will eventually be added to the count table <NUM> (i.e., eventually, based on the probability <NUM>, the keyword <NUM> will be added to the count table <NUM>).

While there is a chance that some tokens <NUM> will be used for multiple documents <NUM>, i.e., when randomly selecting the count value <NUM> between <NUM> and <NUM>, the same number is randomly selected more than once, due to the nature of the infrequent keyword <NUM> and the strong likelihood that the keyword <NUM> will eventually be added to the count table <NUM>, the amount of information leaked from sharing the token <NUM> is minimal. At most, the untrusted storage device <NUM> may learn that each document <NUM> that shares the same token <NUM> has a keyword <NUM> in common. The untrusted storage device <NUM> does not learn what the keyword <NUM> is or the total number of documents <NUM> that include the keyword <NUM>. This technique may drastically reduce the size of the count table <NUM>, as rarely used keywords (e.g., symbols, acronyms, names, etc.) will not be included. This decreases both the storage cost of storing the count table <NUM> and the communication costs during count table operations (e.g., with regards to <FIG>).

<FIG> is a flowchart of an exemplary arrangement of operations for a method <NUM> of providing encrypted search with no zero-day leakage. The method <NUM> includes, at step <NUM>, receiving, at data processing hardware <NUM> of a user device <NUM> associated with a user <NUM>, a search query <NUM> for a keyword <NUM>. The keyword <NUM> appears in one or more encrypted documents <NUM> within a corpus of encrypted documents <NUM> stored on an untrusted storage device <NUM>. The method <NUM> includes, at step <NUM>, accessing, by the data processing hardware <NUM>, a count table <NUM> to obtain a count <NUM> of unique documents <NUM> within the corpus of encrypted documents <NUM> that include the keyword <NUM> and, at step <NUM>, generating, by the data processing hardware <NUM>, a delegatable pseudorandom function (DPRF) <NUM> based on the keyword <NUM>, a private cryptographic key <NUM>, and the count <NUM> of unique documents <NUM> that include the keyword <NUM>.

At step <NUM>, the method <NUM> includes evaluating, by the data processing hardware <NUM>, a first portion of the DPRF 126A, and at step <NUM>, delegating, by the data processing hardware <NUM>, a remaining second portion of the DPRF 126B to the untrusted storage device <NUM>. The remaining second portion of the DPRF, when received by the untrusted storage device <NUM>, causes the untrusted storage device <NUM> to, at step <NUM>, evaluate the remaining second portion of the DPRF 126B, access an encrypted search index <NUM> associated with the corpus of encrypted documents <NUM> stored on the untrusted storage device <NUM>, and determine one or more encrypted documents <NUM> within the corpus of encrypted documents <NUM> associated with the remaining second portion of the DPRF 126B based on the encrypted search index <NUM>. The untrusted storage device <NUM> also returns, to the user device <NUM>, an identifier <NUM> for each encrypted document <NUM> of at least a portion of the one or more encrypted documents <NUM> associated with the remaining second portion of the DPRF 126B.

For example, it may be implemented as a standard server 1000a or multiple times in a group of such servers 1000a, as a laptop computer 1000b, or as part of a rack server system 1000c.

Claim 1:
A computer-implemented method when executed by data processing hardware causes the data processing hardware to perform operations comprising:
receiving a search query for a keyword appearing in one or more encrypted documents within a corpus of encrypted documents stored on an untrusted storage device;
generating a delegatable pseudorandom function (DPRF) based on the keyword, a private cryptographic key, and a count of unique documents within the corpus of encrypted documents that include the keyword;
evaluating a first portion of the DPRF;
delegating a remaining second portion of the DPRF to the untrusted storage device; and
receiving, from the untrusted storage device, an identifier for each encrypted document of at least a portion of the one or more encrypted documents associated with the remaining second portion of the DPRF.