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.