A computer-implemented method when executed by data processing hardware of a user device associated with a user causes the data processing hardware to perform operations comprising: receiving a search query for a keyword , the keyword appearing in one or more encrypted documents within a corpus of encrypted documents stored on an untrusted storage device ; accessing a count table to obtain a count of unique documents within the corpus of encrypted documents that include the keyword ; generating a delegatable pseudorandom function "DPRF" based on the keyword , a private cryptographic key , and the count of unique documents that include the keyword ; 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 causing the untrusted storage device to: evaluate the remaining second portion of the DPRF ; access an encrypted search index associated with the corpus of encrypted documents stored on the untrusted storage device ; determine 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 return, 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 . receiving a search query for a keyword , the keyword appearing in one or more encrypted documents within a corpus of encrypted documents stored on an untrusted storage device ; accessing a count table to obtain a count of unique documents within the corpus of encrypted documents that include the keyword ; generating a delegatable pseudorandom function "DPRF" based on the keyword , a private cryptographic key , and the count of unique documents that include the keyword ; 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 causing the untrusted storage device to: evaluate the remaining second portion of the DPRF ; access an encrypted search index associated with the corpus of encrypted documents stored on the untrusted storage device ; determine 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 return, 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 . evaluate the remaining second portion of the DPRF ; access an encrypted search index associated with the corpus of encrypted documents stored on the untrusted storage device ; determine 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 return, 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 . <EOS>