US 2022/0092047 A1 · Encrypted Search with No Zero-Day Leakage

Abstract

A method for providing encrypted search includes receiving, at a user device associated with a user, a search query for a keyword that appears in one or more encrypted documents stored on an untrusted storage device and accessing a count table to obtain a count of documents 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 documents. The method also includes evaluating a first portion of the DPRF and delegating a remaining second portion of the DPRF to the untrusted storage device which causes the untrusted storage device to evaluate the DPRF and access an encrypted search index associated with the documents. The untrusted storage device determines one or more encrypted documents associated with DPRF and returns, to the user device, an identifier for each encrypted document associated with the DPRF.

Claims20

Dependent claims

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.

3 more elements

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 hardware cause 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.

6 more elements

Dependencies are inferred from the claim text.

Encrypted Search with No Zero-Day Leakage

Life of this patent

Encrypted Search with No Zero-Day Leakage

Life of this patent

Abstract

Claims20