# US 11,308,224 B2 · Encrypted search system design for email client-side encryption > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,224 B2 - Document ID: US11308224B2 - Status: Granted - Kind: B2 - Application number: 16/713,872 - Filed: 2019-12-13 - Published: 2021-06-17 - Granted: 2022-04-19 - Earliest claimed: 2019-12-13 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Kevin Yeo; Ahmet Erhan Nergiz; Laetitia Estelle Baudoin; Nicolas Lidzborski; Sarvar Patel - Web page: https://patentgrep.com/patent/US11308224B2 ## CPC - G06F 21/602: {Providing cryptographic facilities or services} - H04L 9/006: {involving public key infrastructure [PKI] trust models (network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823)} - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - H04L 9/0662: {with particular pseudorandom sequence generator} - H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage} - H04L 63/0428: {wherein the data content is protected, e.g. by encrypting or encapsulating the payload} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method for providing an encrypted search system includes receiving a search query for a keyword that appears in one or more encrypted emails stored on an untrusted storage device and accessing, a count table to obtain a count of unique emails within the emails that include the keyword. The method also includes generating a delegatable pseudorandom function (DPRF) based on the keyword, a private cryptographic key, and the count of unique emails that include the keyword and delegating at least a portion of the DPRF to the untrusted storage device that causes the storage device to evaluate the delegated DPRF, access an encrypted search index associated with the emails, and determine one or more encrypted emails associated with the delegated DPRF based on the encrypted search index. The storage device also returns, to the user device, an identifier for each encrypted email associated with the delegated DPRF. ## Claims ### Claim 1 A method comprising: receiving, at data processing hardware of a user device associated with a user, a search query for a keyword, the keyword appearing in one or more encrypted emails within a corpus of encrypted emails stored on an untrusted storage device; accessing, by the data processing hardware, a count table to obtain a count of unique emails within the corpus of encrypted emails that include the keyword; generating, by the data processing hardware, a delegatable pseudorandom function (DPRF) based on the keyword, a private cryptographic key, and the count of unique emails that include the keyword; and delegating, by the data processing hardware, at least a portion of the DPRF to the untrusted storage device, the delegated at least the portion of the DPRF when received by the untrusted storage device causing the untrusted storage device to: evaluate the delegated at least the portion of the DPRF; access an encrypted search index associated with the corpus of encrypted emails stored on the untrusted storage device; determine one or more encrypted emails within the corpus of encrypted emails associated with the delegated at least the portion of the DPRF based on the encrypted search index; and return, to the user device, an identifier for each encrypted email of at least a portion of the one or more encrypted emails associated with the delegated at least the portion of the DPRF. ### Claim 2 (depends on 1) The method of claim 1, wherein: the count table is encrypted with a second private cryptographic key available only to the user, and the encrypted count table is stored on the untrusted storage device. ### Claim 3 (depends on 2) The method of claim 2, wherein: the encrypted count table comprises a plurality of buckets, each bucket storing one or more counts of unique emails within the corpus of encrypted emails that include a respective keyword, and accessing the count table to obtain the count of unique emails within the corpus of encrypted emails that include the keyword comprises sending a bucket request indicating a specific bucket of the plurality of buckets to the untrusted storage device, the bucket request when received by the untrusted storage device causing the untrusted storage device to return, to the user device, each count stored within the specific bucket. ### Claim 4 (depends on 3) The method of claim 3, wherein when the untrusted storage device returns each count stored within the specific bucket, the untrusted storage device also returns each count associated with one or more other buckets, the one or more other buckets dynamically associated with the specific bucket. ### Claim 5 (depends on 4) The method of claim 4, wherein the untrusted storage device returns each count associated with the one or more other buckets dynamically associated with the specific bucket based on a total number of counts in the specific bucket. ### Claim 6 (depends on 2) The method of claim 2, further comprising assigning, by the data processing hardware, each count to a respective bucket based on an output of a second DPRF. ### Claim 7 (depends on 1) The method of claim 1, wherein accessing the count table to obtain the count of unique emails within the corpus of encrypted emails that include the keyword comprises downloading at least a portion of the count table from the untrusted storage device. ### Claim 8 (depends on 1) The method of claim 1, further comprising, for each unique keyword of a new encrypted email uploaded by the user into the corpus of encrypted emails stored on the untrusted storage device: determining, by the data processing hardware, whether to add a new keyword to the count table based on a probability, the new keyword not currently present in the count table; when the data processing hardware determines to add the new keyword: adding, by the data processing hardware, the new keyword and a new keyword count to the count table; generating, by the data processing hardware, a unique keyword hash based on the private cryptographic key, the corresponding unique keyword, and the new keyword count; generating, by the data processing hardware, a hash pair comprising the unique keyword hash and an encrypted email identifier associated with the new encrypted email uploaded by the user; and sending, by the data processing hardware, the hash pair to the untrusted storage device. ### Claim 9 (depends on 8) The method of claim 8, further comprising, when the data processing hardware determines to not add the new keyword: generating, by the data processing hardware, a unique keyword hash based on the private cryptographic key, the corresponding unique keyword, and a random keyword count; generating, by the data processing hardware, a hash pair comprising the unique keyword hash and an encrypted email identifier associated with the new encrypted email uploaded by the user; and sending, by the data processing hardware, the hash pair to the untrusted storage device. ### Claim 10 (depends on 8) The method of claim 8, wherein the probability is one in fifty that the new keyword is to be added to the count table. ### Claim 11 A system comprising: data processing hardware of a user device associated with a user; and memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing receiving a search query for a keyword, the keyword appearing in one or more encrypted emails within a corpus of encrypted emails stored on an untrusted storage device; accessing a count table to obtain a count of unique emails within the corpus of encrypted emails that include the keyword; generating a delegatable pseudorandom function (DPRF) based on the keyword, a private cryptographic key, and the count of unique emails that include the keyword, and delegating at least a portion of the DPRF to the untrusted storage device, the delegated at least the portion of the DPRF when received by the untrusted storage device causing the untrusted storage device to: evaluate the delegated at least the portion of the DPRF; access an encrypted search index associated with the corpus of encrypted emails stored on the untrusted storage device; determine one or more encrypted emails within the corpus of encrypted emails associated with the delegated at least the portion of the DPRF based on the encrypted search index; and return, to the user device, an identifier for each encrypted email of at least a portion of the one or more encrypted emails associated with the delegated at least the portion of the DPRF. ### Claim 12 (depends on 1) The system of claim 1, wherein; the count table is encrypted with a second private cryptographic key available only to the user, and the encrypted count table is stored on the untrusted storage device. ### Claim 13 (depends on 12) The system of claim 12, wherein: the encrypted count table comprises a plurality of buckets, each bucket storing one or more counts of unique emails within the corpus of encrypted emails that include a respective keyword, and accessing the count table to obtain the count of unique emails within the corpus of encrypted emails that include the keyword comprises sending a bucket request indicating a specific bucket of the plurality of buckets to the untrusted storage device, the bucket request when received by the untrusted storage device causing the untrusted storage device to return, to the user device, each count stored within the specific bucket. ### Claim 14 (depends on 13) The system of claim 13, wherein when the untrusted storage device returns each count stored within the specific bucket, the untrusted storage device also returns each count associated with one or more other buckets, the one or more other buckets dynamically associated with the specific bucket. ### Claim 15 (depends on 14) The system of claim 14, wherein the untrusted storage device returns each count associated with the one or more other buckets dynamically associated with the specific bucket based on a total number of counts in the specific bucket. ### Claim 16 (depends on 12) The system of claim 12, wherein the operations further comprise assigning each count to a respective bucket based on an output of a second DPRF. ### Claim 17 (depends on 11) The system of claim 11, wherein accessing the count table to obtain the count of unique emails within the corpus of encrypted emails that include the keyword comprises downloading at least a portion of the count table from the untrusted storage device. ### Claim 18 (depends on 11) The system of claim 11, wherein the operations further comprise, for each unique keyword of a new encrypted email uploaded by the user into the corpus of encrypted emails stored on the untrusted storage device; determining whether to add a new keyword to the count table based on a probability, the new keyword not currently present in the count table, when the data processing hardware determines to add the new keyword: adding the new keyword and a new keyword count to the count table, generating a unique keyword hash based on the private cryptographic key, the corresponding unique keyword, and the new keyword count; generating a hash pair comprising the unique keyword hash and an encrypted email identifier associated with the new encrypted email uploaded by the user; and sending the hash pair to the untrusted storage device. ### Claim 19 (depends on 18) The system of claim 18, wherein the operations further comprise, when the data processing hardware determines to not add the new keyword: generating a unique keyword hash based on the private cryptographic key, the corresponding unique keyword, and a random keyword count; generating a hash pair comprising the unique keyword hash and an encrypted email identifier associated with the new encrypted email uploaded by the user; and sending the hash pair to the untrusted storage device. ### Claim 20 (depends on 18) The system of claim 18, wherein the probability is one in fifty that the new keyword is to be added to the count table.