# US 11,909,861 B2 · Privately querying a database with private set membership using succinct filters

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,909,861 B2
- Document ID: US11909861B2
- Status: Granted
- Kind: B2
- Application number: 18/189,187
- Filed: 2023-03-23
- Published: 2023-07-20
- Granted: 2024-02-20
- Earliest claimed: 2021-09-23
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Kevin Yeo; Joon Young Seo; Sarvar Patel
- Web page: https://patentgrep.com/patent/US11909861B2

## CPC

- H04L 9/0662: {with particular pseudorandom sequence generator}
- H04L 63/0421: {Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer}
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- H04L 9/008: {involving homomorphic encryption}
- H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 63/0442: {wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption (cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30)}
- H04L 67/146: Markers for unambiguous identification of a particular session, e.g. session cookie or URL-encoding
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method includes obtaining, from a server, a filter including a set of encrypted identifiers each encrypted with a server key controlled by the server. The method includes obtaining a request that requests determination of whether a query identifier is a member of a set of identifiers corresponding to the set of encrypted identifiers. The method also includes transmitting an encryption request to the server that requests the server to encrypt the query identifier. The method includes receiving, from the server, an encrypted query identifier including the query identifier encrypted by the server key and determining, using the filter, whether the encrypted query identifier is not a member of the set of encrypted identifiers. When the encrypted query identifier is not a member of the set of encrypted identifiers, the method includes reporting that the query identifier is not a member of the set of identifiers.

## Claims

### Claim 1

A computer-implemented method when executed by data processing hardware causes the data processing hardware to perform operations comprising:
obtaining, from a server, a probabilistic data structure representing a set of encrypted identifiers, each encrypted identifier of the set of encrypted identifiers representing an identifier of a set of identifiers encrypted with a server key controlled by the server;
obtaining a request to determine that a query identifier is a member of the set of identifiers;
transmitting an encryption request to the server, the encryption request requesting the server to encrypt the query identifier with the server key;
receiving, from the server, an encrypted query identifier comprising the query identifier encrypted by the server key;
determining, using the probabilistic data structure that uses a succinct filter, that the encrypted query identifier is not a member of the set of encrypted identifiers; and
in response to determining that the encrypted query identifier is not a member of the set of encrypted identifiers, generating a notification that the query identifier is not a member of the set of identifiers.

### Claim 2 (depends on 1)

The method of claim 1, wherein the probabilistic data structure comprises a cuckoo filter.

### Claim 3 (depends on 1)

The method of claim 1, wherein the probabilistic data structure comprises a bloom filter.

### Claim 4 (depends on 1)

The method of claim 1, wherein the operations further comprise:
obtaining a second request to determine that a second query identifier is a member of the set of identifiers;
transmitting a second encryption request to the server, the second encryption request requesting the server to encrypt the second query identifier with the server key;
receiving, from the server, a second encrypted query identifier comprising the second query identifier encrypted by the server key;
determining, using the probabilistic data structure, that the second encrypted query identifier may be member of the set of encrypted identifiers; and
in response to determining that the second encrypted query identifier may be a member of the set of encrypted identifiers, generating a second notification that the second query identifier may be a member of the set of identifiers.

### Claim 5 (depends on 4)

The method of claim 4, wherein the operations further comprise:
determining, using a cryptographic protocol based on ring learning with errors, that the second encrypted query identifier is a member of the set of encrypted identifiers; and
generating a third notification that the second query identifier is a member of the set of identifiers.

### Claim 6 (depends on 4)

The method of claim 4, wherein the operations further comprise:
determining, using a cryptographic protocol based on ring learning with errors, that the second encrypted query identifier is not a member of the set of encrypted identifiers; and
generating a third notification that the second query identifier is not a member of the set of identifiers.

### Claim 7 (depends on 1)

The method of claim 1, wherein the probabilistic data structure comprises a plurality of portions, each portion of the plurality of portions comprising a respective subset of encrypted identifiers.

### Claim 8 (depends on 7)

The method of claim 7, wherein the operations further comprise:
receiving, from the server, an update to one of the plurality of portions; and
replacing the one of the plurality of portions with the updated portion.

### Claim 9 (depends on 8)

The method of claim 8, wherein the operations further comprise, prior to receiving the update to the one of the plurality of portions, requesting the update from the server.

### Claim 10 (depends on 1)

The method of claim 1, wherein:
the encryption request comprises an oblivious pseudorandom function; and
the oblivious pseudorandom function conceals an identity of the query identifier from the server.

### Claim 11

A system comprising:
data processing hardware; 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:
causes the data processing hardware to perform operations comprising:
obtaining, from a server, a probabilistic data structure representing a set of encrypted identifiers, each encrypted identifier of the set of encrypted identifiers representing an identifier of a set of identifiers encrypted with a server key controlled by the server;
obtaining a request to determine that a query identifier is a member of the set of identifiers;
transmitting an encryption request to the server, the encryption request requesting the server to encrypt the query identifier with the server key;
receiving, from the server, an encrypted query identifier comprising the query identifier encrypted by the server key;
determining, using the probabilistic data structure that uses a succinct filter, that the encrypted query identifier is not a member of the set of encrypted identifiers; and
in response to determining that the encrypted query identifier is not a member of the set of encrypted identifiers, generating a notification that the query identifier is not a member of the set of identifiers.

### Claim 12 (depends on 11)

The system of claim 11, wherein the probabilistic data structure comprises a cuckoo filter.

### Claim 13 (depends on 11)

The system of claim 11, wherein the probabilistic data structure comprises a bloom filter.

### Claim 14 (depends on 11)

The system of claim 11, wherein the operations further comprise:
obtaining a second request to determine that a second query identifier is a member of the set of identifiers;
transmitting a second encryption request to the server, the second encryption request requesting the server to encrypt the second query identifier with the server key;
receiving, from the server, a second encrypted query identifier comprising the second query identifier encrypted by the server key;
determining, using the probabilistic data structure, that the second encrypted query identifier may be member of the set of encrypted identifiers; and
in response to determining that the second encrypted query identifier may be a member of the set of encrypted identifiers, generating a second notification that the second query identifier may be a member of the set of identifiers.

### Claim 15 (depends on 14)

The system of claim 14, wherein the operations further comprise:
determining, using a cryptographic protocol based on ring learning with errors, that the second encrypted query identifier is a member of the set of encrypted identifiers; and
generating a third notification that the second query identifier is a member of the set of identifiers.

### Claim 16 (depends on 14)

The system of claim 14, wherein the operations further comprise:
determining, using a cryptographic protocol based on ring learning with errors, that the second encrypted query identifier is not a member of the set of encrypted identifiers; and
generating a third notification that the second query identifier is not a member of the set of identifiers.

### Claim 17 (depends on 11)

The system of claim 11, wherein the probabilistic data structure comprises a plurality of portions, each portion of the plurality of portions comprising a respective subset of encrypted identifiers.

### Claim 18 (depends on 17)

The system of claim 17, wherein the operations further comprise:
receiving, from the server, an update to one of the plurality of portions; and
replacing the one of the plurality of portions with the updated portion.

### Claim 19 (depends on 18)

The system of claim 18, wherein the operations further comprise, prior to receiving the update to the one of the plurality of portions, requesting the update from the server.

### Claim 20 (depends on 11)

The system of claim 11, wherein:
the encryption request comprises an oblivious pseudorandom function; and
the oblivious pseudorandom function conceals an identity of the query identifier from the server.